408680: GYM103261 G 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 = 1$$$, $$$p_2 = 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 $$$20 k \le n$$$ holds.

The first line contains a single integer $$$n$$$ ($$$40 \le n \le 10^5$$$) — the length of the permutation.

The second line contains $$$n$$$ distinct integers $$$p_1$$$, $$$p_2$$$, ..., $$$p_n$$$ ($$$1 \le p_i \le n$$$) — the resulting permutation. It is guaranteed that this permutation was generated using the algorithm described above for some $$$k$$$ such that $$$20 k \le 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

The line breaks in the example are added for clarity and do not exist in real tests.