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 ck cards with number k on them in the subsequence, than for all pairs of integers <image> the condition |ci - cj| ≤ 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.

Examples

Input

3
1 1 1


Output

1

Input

8
8 7 6 5 4 3 2 1


Output

8

Input

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


Output

17

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.
// practice with rainboy
import java.io.*;
import java.util.*;

public class CF743E extends PrintWriter {
	CF743E() { super(System.out, true); }
	static class Scanner {
		Scanner(InputStream in) { this.in = in; } InputStream in;
		int k, l; byte[] bb = new byte[1 << 15];
		byte getc() {
			if (k >= l) {
				k = 0;
				try { l = in.read(bb); } catch (IOException e) { l = 0; }
				if (l <= 0) return -1;
			}
			return bb[k++];
		}
		int nextInt() {
			byte c = 0; while (c <= 32) c = getc();
			int a = 0;
			while (c > 32) { a = a * 10 + c - '0'; c = getc(); }
			return a;
		}
	}
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF743E o = new CF743E(); o.main(); o.flush();
	}

	int[] aa;
	int n, m;
	int[][][] jj;
	void init() {
		jj = new int[n + 1][8][m];
		for (int a = 0; a < 8; a++)
			for (int h = 0; h < m; h++)
				jj[n][a][h] = n;
		int[] qq = new int[8]; Arrays.fill(qq, n);
		for (int i = n - 1; i >= 0; i--)
			for (int a = 0; a < 8; a++) {
				int j = qq[a];
				if (a == aa[i]) {
					jj[i][a][0] = qq[a] = i;
					jj[i][a][1] = j;
					for (int h = 2; h < m; h++)
						jj[i][a][h] = jj[j][a][h - 1];
				} else {
					jj[i][a][0] = j;
					for (int h = 1; h < m; h++)
						jj[i][a][h] = jj[j][a][h];
				}
			}
	}
	boolean check(int k) {
		int[] dp = new int[1 << 8];
		Arrays.fill(dp, n + 1);
		dp[0] = 0;
		for (int b = 0; b < 1 << 8; b++) {
			int i = dp[b];
			if (i == n + 1)
				continue;
			for (int a = 0; a < 8; a++)
				if ((b & 1 << a) == 0) {
					int b_ = b | 1 << a;
					dp[b_] = Math.min(dp[b_], jj[i][a][k - 1] + 1);
				}
		}
		return dp[(1 << 8) - 1] <= n;
	}
	void main() {
		n = sc.nextInt();
		aa = new int[n];
		for (int i = 0; i < n; i++)
			aa[i] = sc.nextInt() - 1;
		m = n / 8 + 2;
		if (m > 0)
			init();
		int lower = 0, upper = m + 1, k;
		while (upper - lower > 1) {
			k = (lower + upper) / 2;
			if (check(k))
				lower = k;
			else
				upper = k;
		}
		k = lower;
		if (k == 0) {
			int used = 0;
			for (int i = 0; i < n; i++)
				used |= 1 << aa[i];
			int cnt = 0;
			while (used != 0) {
				cnt++;
				used &= used - 1;
			}
			println(cnt);
			return;
		}
		int[][] dp = new int[1 << 8][8];
		for (int b = 0; b < 1 << 8; b++)
			for (int c = 0; c < 8; c++)
				dp[b][c] = n + 1;
		dp[0][0] = 0;
		for (int b = 0; b < 1 << 8; b++)
			for (int c = 0; c < 8; c++) {
				int i = dp[b][c];
				if (i == n + 1)
					continue;
				for (int a = 0; a < 8; a++)
					if ((b & 1 << a) == 0) {
						int b_ = b | 1 << a;
						dp[b_][c] = Math.min(dp[b_][c], jj[i][a][k - 1] + 1);
						if (c + 1 < 8)
							dp[b_][c + 1] = Math.min(dp[b_][c + 1], jj[i][a][k] + 1);
					}
			}
		int b = (1 << 8) - 1, c = 7;
		while (dp[b][c] == n + 1)
			c--;
		println(k * 8 + c);
	}
}
