시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 4 4 3 100.000%

문제

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.

예제 입력 1

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


예제 출력 1

2