4183: Chinese Restaurant

# Chinese Restaurant ### 内存 1024MB ### 时间 2S ## 题目描述 编号为$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}$ ## 输出格式 输出所求答案。 ## 输入输出样例 ### 输入样例1 ``` 4 1 2 0 3 ``` ### 输出样例1 ``` 4 ``` ### 输入样例2 ``` 3 0 1 2 ``` ### 输出样例2 ``` 3 ``` ### 输入样例3 ``` 10 3 9 6 1 7 2 8 0 5 4 ``` ### 输出样例3 ``` 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$ - 所有输入均为整数。 ## 题目来源 ABC268C