Vladik 在回家的路上很无聊,决定玩下面的游戏。他拿了n张牌,在自己面前排成一排。每张卡片上都写有一个不超过8的正整数。他决定找到满足以下条件的最长卡片子序列:
- 子序列中从 1 到 8 的每个数字的出现次数与任何其他数字的出现次数相差不超过 1。形式上,如果子序列中存在数字为 k 的 ck 卡,则对于所有整数对 $$i \in [1,8], j \in [1,8]$$ ,条件 |ci - cj| ≤ 1 必须成立。
- 如果子序列中至少有一张数字为 x 的牌,则该子序列中所有数字为 x 的牌必须在其中形成一个连续的段(但不一定是原始序列中的连续段)。例如,子序列 [1, 1, 2, 2] 满足此条件,而子序列 [1, 2, 2, 1] 则不满足。请注意,[1, 1, 2, 2]不满足第一个条件。
请帮助Vladik找到满足这两个条件的最长子序列的长度。
输入
第一行包含单个整数 n (1 ≤ n ≤ 1000) — Vladik 序列中的牌数。
第二行包含n个不超过8的正整数的序列——Vladik序列的描述。
输出
打印单个整数 - 满足两个条件的 Vladik 序列的最长子序列的长度。
示例
输入 #1
3 1 1 1
输出 #1
1
输入 #2
8 8 7 6 5 4 3 2 1
输出 #2
8
输入 #3
24 1 8 1 2 8 2 3 8 3 4 8 4 5 8 5 6 8 6 7 8 7 8 8 8
输出 #3
17
注意
在第一个示例中,卡片上写的所有数字都是相等的,因此您不能拿多于一张卡片,否则您将违反第一个条件。