반복

$N$ 개의 정수로 이루어진 수열 $A$가 주어진다. 이 수열에 다음 작업을 반복적으로 수행할 것이다:

• 가장 오른쪽 값을 기준으로 하여 그보다 작거나 같은 값은 왼쪽으로, 그보다 큰 값은 오른쪽으로 모은다.

작업 과정에서 기준의 왼쪽에 배치되는 값들의 상대적인 순서는 바뀌지 않는다. 기준의 오른쪽도 마찬가지이다.

이 작업을 몇 번 수행하고 나면 그 이후에는 수열이 더이상 바뀌지 않는지 제시하라. 단, 한 번의 작업을 했을 때 원래 수열과 동일한 수열이 남으면 답은 $0$이다.

입력 형식

첫 줄에 $N$이 주어진다. ($1 \le N \le 200\,000$)

그다음 줄에 $N$ 개의 정수 $A_1, \cdots, A_N$이 공백으로 구분되어 주어진다. ($1 \le A_{i} \le 1\,000\,000\,000$)

출력 형식

첫 줄에 답을 출력한다. 만약, 수열이 더이상 바뀌지 않는 순간이 없다면 $-1$을 출력한다.

예제 1

6
4 3 5 2 1 1

2

예제 2

4
100 200 300 400

0

예제 설명

예제 1에서, 한 번 작업을 수행하고 나면 수열은 $1, 1, 4, 3, 5, 2$로 바뀐다. 여기서 첫 $1$은 원래 수열에서 다섯 번째에 있던 값이며, 두 번째 $1$은 원래 수열에서 여섯 번째에 있던 값이다. 원래 수열의 제일 오른쪽에 있던 $1$보다 큰 값들은 모두 두 번째 $1$의 오른쪽에 있으며, 자신들 간의 상대적 순서는 바뀌지 않았음에 유의하라. 두 번째 작업을 하고 나면 수열은 $1, 1, 2, 4, 3, 5$로 바뀐다. 세 번째 작업을 수행해도 수열이 바뀌지 않으므로, 이 경우의 답은 $2$이다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설