시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 43 | 33 | 29 | 78.378% |
Petr is well-known for his unusual contests which shuffle well-established standings a lot. Each of his contests has a positive integer parameter k: its unusualness.
To predict results of such a contest with n participants, we can use the following algorithm: take an identity permutation of length n: p1 = 1, p2 = 2, . . . , pn = n and then sequentially shuffle all segments of length k from left to right.
In other words, we perform (n − k + 1) operations, where on the i-th operation we permute elements pi, pi+1, . . . , pi+k−1 in random order so that all the permutations of these elements are equiprobable.
Given the resulting permutation p, can you recover the unusualness parameter k of this particular Petr’s contest? To make things easier, we will only give you such tests that 20k ≤ n holds.
The first line contains a single integer n (40 ≤ n ≤ 105) — the length of the permutation.
The second line contains n distinct integers p1, p2, . . . , pn (1 ≤ pi ≤ n) — the resulting permutation. It is guaranteed that this permutation was generated using the algorithm described above for some k such that 20k ≤ n.
Print a single integer — the unusualness parameter k of this particular Petr’s contest.
40 2 3 4 1 6 5 8 9 7 11 10 12 14 13 15 17 18 16 19 20 21 23 22 25 26 24 28 27 30 29 32 33 31 35 36 37 38 34 40 39
2