题目描述

这次小新遇到了一个困扰他很久的问题。如果解决不了，他会一直吃得好睡得好，所以他很着急，于是提前来结训赛问问大家。

给定一个长度为 $n$ 的整数数组：

你可以执行以下操作任意次（包括 $0$ 次）：

对所有 $1 \le i \le n$，同时令

操作全部结束后，请求出：数组中出现次数最多的那个整数，其出现次数是多少（即最大频率）。

记号说明

注意

该操作是对整个数组同时进行的：每一步都会让所有元素一起变成 $\lvert a_i - 2 \rvert$，不能只挑选某个下标单独修改。

目标

在所有可能的操作次数中，最大化某个整数在数组中出现的次数，输出这个最大次数。

输入格式

• 第一行一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示数组 $a$ 的长度；
• 第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示数组 $a$，相邻两个整数之间用一个空格隔开。

输出格式

对于每个测试用例，在执行操作任意次数后，输出表示 a 中任何整数的最大可能频率的单个整数。

样例

2
1 3

2

4
1 1 1 2

3

3
6 7 8

2

5
1 10 100 1000 100000

3

样例解释

对于第一个样例：我们可以执行一次操作以获得 a=[|1−2|,|3−2|]=[1,1]，这意味着 a 中任何整数的最大可能频率是 2