Vladik was bored on his way home and decided to play the following game. He took _n_ cards and put them in a row in front of himself. Every card has a positive integer number not exceeding 8 written on it. He decided to find the longest subsequence of cards which satisfies the following conditions:
* the number of occurrences of each number from 1 to 8 in the subsequence doesn't differ by more then 1 from the number of occurrences of any other number. Formally, if there are _c__k_ cards with number _k_ on them in the subsequence, than for all pairs of integers the condition |_c__i_ - _c__j_| ≤ 1 must hold.
* if there is at least one card with number _x_ on it in the subsequence, then all cards with number _x_ in this subsequence must form a continuous segment in it (**but not necessarily a continuous segment in the original sequence**). For example, the subsequence \[1, 1, 2, 2\] satisfies this condition while the subsequence \[1, 2, 2, 1\] doesn't. Note that \[1, 1, 2, 2\] doesn't satisfy the first condition.
Please help Vladik to find the length of the longest subsequence that satisfies both conditions.
## Input
The first line contains single integer _n_ (1 ≤ _n_ ≤ 1000) — the number of cards in Vladik's sequence.
The second line contains the sequence of _n_ positive integers not exceeding 8 — the description of Vladik's sequence.
## Output
Print single integer — the length of the longest subsequence of Vladik's sequence that satisfies both conditions.
[samples]
## Note
In the first sample all the numbers written on the cards are equal, so you can't take more than one card, otherwise you'll violate the first condition.
Vladik 在回家的路上感到无聊，决定玩以下游戏。他拿了 #cf_span[n] 张卡片，并将它们排成一排放在自己面前。每张卡片上写有一个不超过 #cf_span[8] 的正整数。他希望找到一个最长的子序列，满足以下条件：
请帮助 Vladik 找出满足两个条件的最长子序列的长度。
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 1000]) —— Vladik 序列中卡片的数量。
第二行包含 #cf_span[n] 个不超过 #cf_span[8] 的正整数序列 —— Vladik 序列的描述。
请输出一个整数 —— 满足两个条件的 Vladik 序列的最长子序列的长度。
在第一个样例中，所有卡片上的数字都相等，因此你不能取超过一张卡片，否则将违反第一个条件。
## Input
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 1000]) —— Vladik 序列中卡片的数量。第二行包含 #cf_span[n] 个不超过 #cf_span[8] 的正整数序列 —— Vladik 序列的描述。
## Output
请输出一个整数 —— 满足两个条件的 Vladik 序列的最长子序列的长度。
[samples]
## Note
在第一个样例中，所有卡片上的数字都相等，因此你不能取超过一张卡片，否则将违反第一个条件。
**Definitions:**
Let $ a = (a_1, a_2, \dots, a_n) $ be a sequence of $ n $ positive integers, where $ 1 \leq n \leq 1000 $ and $ 1 \leq a_i \leq 8 $ for all $ i $.
Let $ S $ be a subsequence of $ a $, i.e., a sequence $ S = (a_{i_1}, a_{i_2}, \dots, a_{i_k}) $ with $ 1 \leq i_1 < i_2 < \dots < i_k \leq n $.
**Constraints:**
1. All elements in $ S $ are distinct.
2. For every pair of consecutive elements in $ S $, say $ (x, y) $, if $ x $ appears at position $ i $ and $ y $ at position $ j $ in the original sequence $ a $, then $ i < j $ (i.e., $ S $ is a subsequence in order).
**Objective:**
Maximize the length $ |S| $ of such a subsequence $ S $.
---
**Formal Statement:**
Find the maximum length $ k $ of a subsequence $ S = (s_1, s_2, \dots, s_k) $ of $ a $ such that:
- $ s_i \ne s_j $ for all $ i \ne j $, and
- $ s_1, s_2, \dots, s_k $ appear in $ a $ in increasing order of indices.
---
**Note:** Since values are bounded by 8, the maximum possible length of such a subsequence is at most 8.