Petr의 알고리즘
시간 제한1초메모리 제한512 MB
길이 k인 모든 구간을 왼쪽에서 오른쪽으로 무작위로 섞어 만든 순열이 주어질 때, 그 k 값을 알아낸다. 입력은 20k가 n 이하임을 보장한다.
문제
Petr은 기존의 순위를 크게 뒤흔드는 독특한 대회를 여는 것으로 유명하다. 그가 여는 각 대회에는 양의 정수 매개변수 k가 있는데, 이것이 그 대회의 독특함이다.
참가자가 n명인 이런 대회의 결과를 예측하려면 다음과 같은 알고리즘을 쓸 수 있다. 길이 n인 항등 순열 p1 = 1, p2 = 2, ..., pn = n을 잡고, 길이 k인 모든 구간을 왼쪽에서 오른쪽으로 차례로 섞는다.
다시 말해 (n - k + 1)번의 연산을 수행하는데, i번째 연산에서는 원소 pi, pi+1, ..., pi+k-1을 무작위 순서로 재배열하며, 이 원소들의 모든 순열이 같은 확률로 나타난다.
결과 순열 p가 주어졌을 때, 이 대회의 독특함 매개변수 k를 알아낼 수 있는가? 문제를 쉽게 하기 위해 20k ≤ n인 테스트만 주어진다.
입력
첫째 줄에는 순열의 길이를 나타내는 정수 n (40 ≤ n ≤ 105)이 주어진다.
둘째 줄에는 n개의 서로 다른 정수 p1, p2, ..., pn (1 ≤ pi ≤ n)이 주어지는데, 이것이 결과 순열이다. 이 순열은 20k ≤ n인 어떤 k에 대해 위에서 설명한 알고리즘으로 생성되었음이 보장된다.
출력
이 대회의 독특함 매개변수 k를 나타내는 정수 하나를 출력한다.