胖头鱼在苦恼“沉鱼落雁”是什么好吃的东西，这很显然是因为他成语没背够。
于是他决定开始背成语。胖头鱼身为鱼界大佬，背成语的姿势自然也和常人不一：
他会先将所有要背的成语一字排开，比较难背的成语会重复出现，最多重复 $3$ 次 (也就是出现次数可能为 $1$, $2$ 或 $3$)。这样就得到了一个可能有重复元素的成语序列，然后他会将这个序列打乱顺序，并按打乱后的顺序背下去。为了均匀的背所有成语，提高背成语的效率，相同成语在打乱后的序列中出现位置的最小间隔自然是越大越好。 (编号为 $a$ 和 $b$ ($a<b$) 的两个位置的间隔定义为 $b-a-1$)
现在胖头鱼把打乱前的成语序列给你，你需要帮他打乱顺序，使得相同成语的最小间隔最大。
你不需要输出确切的方案，仅求出最小间隔的最大值即可。
特别地，当每种成语都只出现一次时，把最小间隔的最大值视为$n$。
第一行一个整数 $n$ ($1 \le n \le 10^5$)，表示成语序列长度为 $n$。同一个成语最在序列中最多出现 $3$ 次。
接下来 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) 表示一个成语序列，每个正整数都代表一个成语，两个成语不同当且仅当值不同。
输出一个整数，表示最小间隔的最大值。
9 5 4 3 1 3 1 1 5 5
2
5 1 2 3 4 5
5
Comet OJ