AT_abc268_c [ABC268C] Chinese Restaurant

题目描述

题意

有 $N$ 个人从 $0$ 开始编号， 按逆时针顺序间隔均匀地坐在转盘周围。 在开始时， 第 $p_{i}$ 盘菜在第 $i$ 个人的前面。

现在， 你可以进行以下操作 $0$ 次或多次。

• 将转盘逆时针旋转 $\frac{1}{N}$ 圈。也就是说， 旋转前在第 $i$ 号人面前的盘子现在在 $(i+1)\bmod N$ 号人面前了。

当你结束操作后，如果第 $i$ 盘菜在第 $(i-1)\bmod N$ 个人、第 $i$ 个人或第 $(i+1)\bmod N$ 个人面前，第 $i$ 个人就会感到高兴。

请求出你最多能使多少人感到高兴。

输入格式

使用标准输入以以下格式读入：

N
p0 ... pN-1

输出格式

直接输出答案

样例解释1

下图是一次操作后的桌面

这里有四个人感到快乐：

• 第 $0$ 个人感到快乐，因为第 $0$ 盘菜在第 $3\ (=(0 - 1) \bmod 4)$ 个人面前；
• 第 $1$ 个人感到快乐，因为第 $1$ 盘菜在第 $1$ 个人面前
• 第 $2$ 个人感到快乐，因为第 $2$ 盘菜在第 $2$ 个人面前
• 第 $3$ 个人感到快乐，因为第 $3$ 盘菜在第 $0\ (=(3+1)\bmod 4)$ 个人面前

很显然不能有五个或更多的人感到快乐了，所以答案是 $4$ .

输入输出样例 #1

输入 #1

4
1 2 0 3

输出 #1

4

输入输出样例 #2

输入 #2

3
0 1 2

输出 #2

3

输入输出样例 #3

输入 #3

10
3 9 6 1 7 2 8 0 5 4

输出 #3

5

说明/提示

• $3 \leq N \leq 2 × 10^{5}$
• $0 \leq p_{i} \leq N - 1$
• 当 $i \ne j$ 时 $p_{i}\ne p_{j}$
• 所有输入都是整数