408081: GYM102979 I Integer Array Shuffle
Description
Given an integer array $$$A$$$ of size $$$N$$$, the shuffle operation is defined as follows.
- Initially, you create an empty integer array $$$B$$$.
- Then, while $$$A$$$ is not empty, you remove either the leftmost or rightmost element of $$$A$$$, and append the value to the right in $$$B$$$.
- If $$$A$$$ is empty, replace $$$A$$$ with $$$B$$$ and stop.
If the shuffle operation is performed as shown in the picture above, the value of the array $$$A$$$ is changed as follows:
$$$$$$(34,\, 19,\, 5,\, 36,\, 4,\, 25,\, 12,\, 9) \to (9,\, 34,\, 19,\, 12,\, 25,\, 4,\, 5,\, 36)\text{.}$$$$$$
Let $$$A_i$$$ be the $$$i$$$-th element of array $$$A$$$. When the condition "if $$$1 \le i < j \le N$$$, then $$$A_i \le A_j$$$" is established, it is said that array $$$A$$$ increases monotonically.
Write a program that, given an integer array $$$A$$$ of size $$$N$$$, calculates the minimum number of shuffle operations required to make the array $$$A$$$ monotonically increasing.
InputThe first line of input contains one integer $$$N$$$, the number of elements in array $$$A$$$ ($$$1 \le N \le 3 \cdot 10^5$$$).
The second line contains $$$N$$$ integers $$$A_1, \ldots, A_N$$$: the initial values of elements of array $$$A$$$ ($$$1 \le A_i \le 10^9$$$).
OutputOutput the minimum number of shuffle operations required to make the array $$$A$$$ monotonically increasing.
ExamplesInput3 2 2 5Output
0Input
6 1 5 8 10 3 2Output
1