You are given a permutation of numbers from 1 to n. Determine whether there's a pair of integers a, b (1 ≤ a, b ≤ n; a ≠ b) such that the element <image> (note, that it is usual division, not integer one) is between a and b in this permutation.

Input

First line consists of a single integer n (1 ≤ n ≤ 300000) — the size of permutation.

Second line contains n integers — the permutation itself.

Output

Print "YES", if such a pair exists, "NO" otherwise (in both cases without quotes, the answer is case insensitive).

Examples

Input

4
1 3 4 2


Output

NO


Input

5
1 5 2 4 3


Output

YES

Note

In the second example 2 is between 1 and 3. Additionally 4 is between 3 and 5.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author AlexFetisov
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskF_MEMSQL solver = new TaskF_MEMSQL();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskF_MEMSQL {
        public static final int BUBEN = 50;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int[] a = new int[n];
            int[] pos = new int[n];
            for (int i = 0; i < n; ++i) {
                a[i] = in.nextInt() - 1;
                pos[a[i]] = i;
            }
            for (int i = 1; i < n; ++i) {
                for (int j = -BUBEN; j <= BUBEN; ++j) {
                    if (i + j >= 0 && i + j < n) {
                        int x = a[i];
                        int y = a[i + j];
                        if ((x + y) % 2 == 0) {
                            int d = (x + y) / 2;
                            if (pos[d] > pos[x] && pos[d] < pos[y]) {
                                out.println("YES");
                                return;
                            }
                            if (pos[d] > pos[y] && pos[d] < pos[x]) {
                                out.println("YES");
                                return;
                            }
                        }

                        // 2x = y + ? =? ? = 2x - y
                        int d = 2 * x - y;
                        if (d >= 0 && d < n && d != x && d != y) {
                            if (pos[d] < pos[x] && pos[x] < pos[y]) {
                                out.println("YES");
                                return;
                            }
                            if (pos[y] < pos[x] && pos[x] < pos[d]) {
                                out.println("YES");
                                return;
                            }
                        }

                        d = 2 * y - x;
                        if (d >= 0 && d < n && d != x && d != y) {
                            if (pos[d] < pos[y] && pos[y] < pos[x]) {
                                out.println("YES");
                                return;
                            }
                            if (pos[x] < pos[y] && pos[y] < pos[d]) {
                                out.println("YES");
                                return;
                            }
                        }
                    }
                }
            }
            out.println("NO");
        }

    }

    static class InputReader {
        private BufferedReader reader;
        private StringTokenizer stt;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
        }

        public String nextLine() {
            try {
                return reader.readLine();
            } catch (IOException e) {
                return null;
            }
        }

        public String nextString() {
            while (stt == null || !stt.hasMoreTokens()) {
                stt = new StringTokenizer(nextLine());
            }
            return stt.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(nextString());
        }

    }
}

