18494번 - Petr’s Algorithm 다국어

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: p₁ = 1, p₂ = 2, . . . , p_n = 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 p_i, p_i+1, . . . , p_i+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 ≤ 10⁵) — the length of the permutation.

The second line contains n distinct integers p₁, p₂, . . . , p_n (1 ≤ p_i ≤ 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.