Petr 以其经常打乱既定排名的不同寻常的比赛而闻名。他的每场比赛都有一个正整数参数 $k$：即“不寻常度”。

为了预测一场有 $n$ 名参赛者的比赛结果，我们可以使用以下算法：取一个长度为 $n$ 的恒等排列：$p_1 = 1, p_2 = 2, \dots, p_n = n$，然后从左到右依次对所有长度为 $k$ 的段进行洗牌。

换句话说，我们执行 $(n - k + 1)$ 次操作，其中在第 $i$ 次操作中，我们将元素 $p_i, p_{i+1}, \dots, p_{i+k-1}$ 以随机顺序进行排列，使得这些元素的所有排列等概率出现。

给定最终的排列 $p$，你能恢复这场 Petr 比赛的不寻常度参数 $k$ 吗？为了简化问题，我们只提供满足 $20k \le n$ 的测试数据。

输入格式

第一行包含一个整数 $n$ ($40 \le n \le 10^5$)，表示排列的长度。

第二行包含 $n$ 个不同的整数 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$)，表示最终的排列。保证该排列是由上述算法针对某个满足 $20k \le n$ 的 $k$ 生成的。

输出格式

输出一个整数，即这场 Petr 比赛的不寻常度参数 $k$。

样例

样例输入 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

说明

样例中的换行符是为了清晰起见而添加的，在实际测试中并不存在。