中餐馆

题目描述

人 $0$、人 $1$、$\ldots$、人 $(N-1)$ 按逆时针顺序等间距地围坐在转盘周围。餐桌上人 $i$ 面前放着菜 $p_i$。

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

将转盘逆时针转动一圈的 $1/N$。于是，旋转前在人 $i$ 面前的菜，现在位于人 $(i+1) \bmod N$ 面前。

操作全部结束后，如果菜 $i$ 位于人 $(i-1) \bmod N$、人 $i$ 或人 $(i+1) \bmod N$ 面前，则人 $i$ 是高兴的。

求最多能让多少人同时高兴。

什么是 $a \bmod m$？ 对于整数 $a$ 和正整数 $m$，$a \bmod m$ 表示满足 $(a-x)$ 是 $m$ 的倍数的整数 $x$（$0 \le x \le m-1$）。（可以证明这样的 $x$ 是唯一的。）

输入格式

输入按以下格式从标准输入给出：

$N$
$p_0$ $\ldots$ $p_{N-1}$

输出格式

输出答案。

样例

4
1 2 0 3

4

操作一次之后，有 4 个人高兴：

• 人 $0$ 高兴，因为菜 $0$ 位于人 $3\ (=(0-1) \bmod 4)$ 面前；
• 人 $1$ 高兴，因为菜 $1$ 位于人 $1\ (=1)$ 面前；
• 人 $2$ 高兴，因为菜 $2$ 位于人 $2\ (=2)$ 面前；
• 人 $3$ 高兴，因为菜 $3$ 位于人 $0\ (=(3+1) \bmod 4)$ 面前。

不可能让 5 个或更多人高兴，所以答案是 $4$。

3
0 1 2

3

10
3 9 6 1 7 2 8 0 5 4

5

数据范围

• $3 \le N \le 2 \times 10^5$
• $0 \le p_i \le N-1$
• 当 $i \neq j$ 时，$p_i \neq p_j$
• 输入均为整数。