题目描述

编号为$0$到$N-1$的$N$个人围坐在一个转盘周围，按逆时针顺序均匀分布。编号为 $p_{i}$ 的盘子放在第 $i$ 个人面前的桌子上。

你可以执行以下操作 0 次或多次：

• 将转盘逆时针旋转 $\frac{1}{N}$ 圈。结果是，原本在第 $i$ 个人面前的盘子现在会在第 $(i+1) \bmod N$ 个人面前。

操作结束后，如果盘子i刚好在第$(N-1) \bmod N$个人，或者第$i$个人，或者第$(i+1)\bmod N$个人前面，第$i$个人就会开心。请计算最多可能有多少人开心。

对于一个整数 $a$ 和一个正整数 $b$，$a \mod b$ 表示 $a$ 除以 $b$ 后的余数。具体来说，它是一个介于 $0$ 和 $(b-1)$ 之间的整数 $x$，使得 $(a - x)$ 是 $b$ 的倍数。（可以证明这样的 $x$ 是唯一的。）

输入格式

输入从标准输入中给出，格式如下：

$N$

$p_0$ $p_1$ $\cdots$. $p_{N-1}$

输出格式

输出所求答案。

样例

4
1 2 0 3

4

3
0 1 2

3

10
3 9 6 1 7 2 8 0 5 4

5

样例1解释

下图显示了执行一次操作后的桌子状态。

此时有四个人感到高兴：

• 第 0 个人高兴，因为 0 号盘子在第 3 个人（= (0-1) mod 4）面前；
• 第 1 个人高兴，因为 1 号盘子在第 1 个人（= 1）面前；
• 第 2 个人高兴，因为 2 号盘子在第 2 个人（= 2）面前；
• 第 3 个人高兴，因为 3 号盘子在第 0 个人（= (3+1) mod 4）面前。

不可能有 5 个或更多的人感到高兴，所以答案是 4。

数据范围

• $3 \leq N \leq 2 \times 10^5$
• $0 \leq p_i \leq N-1$
• 如果 $i \neq j$，则 $p_i \neq p_j$
• 所有输入均为整数。

来源

• AtCoder ABC268C