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.
    import java.util.*;
    import java.io.*;
    import java.math.*;
     
    public class Main {
        static PrintWriter out;
        static Reader in;
        public static void main(String[] args) throws IOException {
            //out = new PrintWriter(new File("out.txt"));
            //PrintWriter out = new PrintWriter(System.out);
            //in = new Reader(new FileInputStream("in.txt"));
            //Reader in = new Reader();
            input_output();
            Main solver = new Main();
            solver.solve();
            out.flush();
            out.close();
     
        }
     
        static long INF = (long)1e16;
        static int maxn = (int)1e6+1000;
        static int mod=(int)1e9+7 ;
        static int n, m, q, k, t;
     
        static int[][][] next;

        void solve() throws IOException{
            n = in.nextInt();

            int[] arr = new int[n];
            int[] vis = new int[9];
            for (int i = 0; i < n; i++) {
                arr[i] = in.nextInt();
                vis[arr[i]] = 1;
            }

            next = new int[n+1][9][201];
            for (int i = 0; i <= n; i++)
                for (int j = 1; j <= 8; j++)
                    for (int k = 1; k <= 200; k++)
                        next[i][j][k] = -1;

            next[n][arr[n-1]][1] = n;

            for (int i = n-1; i > 0; i--) {
                for (int j = 1; j <= 8; j++) {
                    if (arr[i-1] == j) {
                        for (int k = 200; k >= 2; k--)
                            next[i][j][k] = next[i+1][j][k-1];
                        next[i][j][1] = i;
                    } else {
                        for (int k = 200; k >= 1; k--)
                            next[i][j][k] = next[i+1][j][k];
                    }
                }
            }

            ans = 0;
            for (int i = 1; i <= 8; i++) ans += vis[i];


            int lo = 1, hi = 199, mid;
            flag = false;
            
            while (lo <= hi) {
                mid = (lo+hi)/2;

                if (check(arr, mid)) {
                    lo = mid+1;
                } else hi = mid-1;
            }

            out.println(ans);
        }
     
        //<>

        static boolean flag;
        static int ans;

        static boolean check(int[] arr, int mid) {
            int pwr = 256;
            boolean res = false;
            int[][] dp = new int[n+1][pwr];

            for (int i = 0; i <= n; i++)
                for (int j = 0; j < pwr; j++)
                    dp[i][j] = -1;
            dp[0][0] = 0;

            int tmp;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < pwr; j++) {
                    if (dp[i][j] == -1) continue;

                    for (int k = 0; k < 8; k++) {
                        if ((j&(1<<k)) != 0) continue;
                        tmp = next[i+1][k+1][mid];
                        if (tmp != -1) dp[tmp][j|(1<<k)] = Math.max(dp[tmp][j|(1<<k)], dp[i][j]+mid);
                        tmp = next[i+1][k+1][mid+1];
                        if (tmp != -1) dp[tmp][j|(1<<k)] = Math.max(dp[tmp][j|(1<<k)], dp[i][j]+mid+1);
                    }
                }
                if (dp[i][pwr-1] != -1) {
                    res = true;
                    ans = Math.max(ans, dp[i][pwr-1]);
                }
            }
            if(dp[n][pwr-1] != -1) {
                res = true;
                ans = Math.max(ans, dp[n][pwr-1]);
            }

            return res;
        }

        static class Reader {
     
            private InputStream mIs;
            private byte[] buf = new byte[1024];
            private int curChar;
            private int numChars;
        
            public Reader() {
                this(System.in);
            }
        
            public Reader(InputStream is) {
                mIs = is;
            }
        
            public int read() {
                if (numChars == -1) {
                    throw new InputMismatchException();
        
            }
                if (curChar >= numChars) {
                    curChar = 0;
                    try {
                        numChars = mIs.read(buf);
                    } catch (IOException e) {
                        throw new InputMismatchException();
                    }
                    if (numChars <= 0) {
                        return -1;
                    }
                }
                return buf[curChar++];
            }
        
            public String nextLine() {
                int c = read();
                while (isSpaceChar(c)) {
                    c = read();
                }
                StringBuilder res = new StringBuilder();
                do {
                    res.appendCodePoint(c);
                    c = read();
                } while (!isEndOfLine(c));
                return res.toString();
            }
        
            public String next() {
                int c = read();
                while (isSpaceChar(c)) {
                    c = read();
                }
                StringBuilder res = new StringBuilder();
                do {
                    res.appendCodePoint(c);
                    c = read();
                } while (!isSpaceChar(c));
                return res.toString();
            }
        
            double nextDouble()
            {
                return Double.parseDouble(next());
            }
        
            public long nextLong() {
                int c = read();
                while (isSpaceChar(c)) {
                    c = read();
                }
                int sgn = 1;
                if (c == '-') {
                    sgn = -1;
                    c = read();
                }
                long res = 0;
                do {
                    if (c < '0' || c > '9') {
                        throw new InputMismatchException();
                    }
                    res *= 10;
                    res += c - '0';
                    c = read();
                } while (!isSpaceChar(c));
                return res * sgn;
            }
        
            public int nextInt() {
                int c = read();
                while (isSpaceChar(c)) {
                    c = read();
                }
                int sgn = 1;
                if (c == '-') {
                    sgn = -1;
                    c = read();
                }
                int res = 0;
                do {
                    if (c < '0' || c > '9') {
                        throw new InputMismatchException();
                    }
                    res *= 10;
                    res += c - '0';
                    c = read();
                } while (!isSpaceChar(c));
                return res * sgn;
            }
        
            public boolean isSpaceChar(int c) {
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
            }
        
            public boolean isEndOfLine(int c) {
                return c == '\n' || c == '\r' || c == -1;
            }
     
        }
        static void input_output() throws IOException {
            File f = new File("in.txt");
            if(f.exists() && !f.isDirectory()) { 
                in = new Reader(new FileInputStream("in.txt"));
            } else in = new Reader();
            f = new File("out.txt");
            if(f.exists() && !f.isDirectory()) {
                out = new PrintWriter(new File("out.txt"));
            } else out = new PrintWriter(System.out);
        }
    }