Petr's Algorithm
Time limit1sMemory limit512 MB
Given a permutation produced by randomly shuffling every length-k window left to right, recover k. The input guarantees 20k is at most n.
- Level
Medium7 of 10
- Topics
- Probability, Math, Implementation, Brute force
- Solved
- No attempts yet
Problem
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 the 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 the elements pi, pi+1, ..., pi+k-1 in random order so that all permutations of these elements are equally likely.
Given the resulting permutation p, can you recover the unusualness parameter k of this particular contest? To make things easier, we will only give you tests such that 20k ≤ n holds.
Input
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.
Output
Print a single integer: the unusualness parameter k of this contest.