Alternating Algorithm

문제

In recent years, CPU manufacturers have found it increasingly difficult to keep up with Moore's law of doubling the number of transistors on integrated circuit chips every two years. To address this, manufacturers have instead started creating CPUs with an increasingly higher number of cores. In fact, you just purchased a CPU with a staggering $nn$ number of cores, no less!

Incidentally, you also have an array of $n+1n+1$ integers, $a_0,a_1,\dots ,a_{n}a\_0,\; a\_1,\; \backslash ldots,\; a\_n$, that you need to sort. To make good use of the large number of cores on your CPU, you have devised a parallel sorting algorithm in which there is a dedicated core for comparing each adjacent pair of integers. As long as the array is not sorted in non-decreasing order, the algorithm proceeds in rounds that alternate between:

• Odd rounds (starting with the first): The first core compares $a_{0}a\_0$ and $a_{1}a\_1$, the third core compares $a_{2}a\_2$ and $a_{3}a\_3$, the fifth core compares $a_{4}a\_4$ and $a_{5}a\_5$, and so on. If a pair of compared elements are out of order, the corresponding core will swap their positions. If $nn$ is even, $a_{n}a\_n$ will be left untouched.
• Even rounds: The second core compares $a_{1}a\_1$ and $a_{2}a\_2$, the fourth core compares $a_{3}a\_3$ and $a_{4}a\_4$, the sixth core compares $a_{5}a\_5$ and $a_{6}a\_6$, and so on. If a pair of compared elements are out of order, the corresponding core will swap their positions. If $nn$ is odd, $a_{n}a\_n$ will be left untouched, and $a_{0}a\_0$ will be left untouched no matter what the parity of $nn$ is.

Note that in both types of rounds some cores may be idle.

Before implementing this algorithm, you have decided to do some analysis. In particular, you noticed that the time complexity of the algorithm does not depend on the value of $nn$, but rather it depends on the number of rounds that the algorithm runs. Given the initial contents of the array, determine the number of rounds that the parallel sorting algorithm runs before the array becomes sorted.

입력

The input consists of:

• One line with an integer $nn$ ($1\le n\le 4\cdot {10}^{5}1\; \backslash leq\; n\; \backslash leq\; 4\backslash cdot10^5$), the number of cores and the size of the array.
• One line with $n+1n+1$ integers $a_0,a_1,\dots ,a_{n}a\_0,\; a\_1,\; \backslash ldots,\; a\_n$ ($0\le a_i\le {10}^{9}0\; \backslash leq\; a\_i\; \backslash leq\; 10^9$ for each $ii$), the initial contents of the array.

출력

Output the number of rounds that the parallel sorting algorithm runs before the array becomes sorted in non-decreasing order.

3
8 13 4 10

3

5
13 12 14 10 14 12

3

2
2 2 1

3