- Time limit: 1.00 s
- Memory limit: 512 MB
One iteration of bubblesort scans an array from start to end and swaps adjacent elements if they are in wrong order. Usually only one iteration of bubblesort is not enough to sort an array.
You are given an array a_1, a_2, \dots, a_n which contains each integer from 1 to n exactly once. Your task is to count how many iterations of bubblesort is needed to sort the array in increasing order.
More formally one iteration of bubblesort does n-1 steps. In step i it swaps elements a_i and a_{i+1} if a_i > a_{i+1}.
Input
The first line of input contains one integer, n. The second line contains n integers, a_1, \ldots, a_n.
Output
Output one integer, the number of bubblesort iterations needed to sort the array.
Constraints
- 1 \le n \le 5 \cdot 10^5
Examples
Input:
4 3 1 4 2
Output:
2
After the first iteration the array is 1 3 2 4
. The array is sorted after the second iteration.
Input:
4 4 3 2 1
Output:
3
Input:
3 1 2 3
Output:
0