配点 : $300$ 点

問題文

長さ $N$ の整数列 $a_1,a_2,...,a_N$ が与えられます。

各 $1 \leq i \leq N$ に対し、$a_i$ に $1$ 足すか、$1$ 引くか、なにもしないかの三つの操作からどれか一つを選んで行います。

この操作の後、ある整数 $X$ を選んで、$a_i=X$ となる $i$ の個数を数えます。

うまく操作を行い、$X$ を選ぶことで、この個数を最大化してください。

制約

• $1 \leq N \leq 10^5$
• $0 \leq a_i<10^5 (1 \leq i \leq N)$
• $a_i$ は整数

入力

入力は以下の形式で標準入力から与えられる。

$N$

$a_1$ $a_2$ .. $a_N$

出力

うまく操作を行い、$X$ を選んだ時の $a_i=X$ なる $i$ の個数の最大値を出力せよ。

7
3 1 4 1 5 9 2

4

例えば操作後の数列を $2,2,3,2,6,9,2$ とすることができて、$X=2$ とすると $4$ を得ることができ、これが最大です。

10
0 1 2 3 4 5 6 7 8 9

3

1
99999

1