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.IOException;
import java.io.FilterInputStream;
import java.util.Iterator;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;
import java.io.BufferedInputStream;
import java.io.InputStream;

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

class Palindrome {

    public void solve(int testNumber, InputUtil in, PrintWriter out) {
        int n = in.nextInt();
        PalindromeChecker chk1 = new PalindromeChecker(n, 1_000_007);
        PalindromeChecker chk2 = new PalindromeChecker(n, 1_000_009);
        for (int i = 0; i < n; i++) {
            int x = in.nextInt();
            chk1.mark(x);
            chk2.mark(x);
            if (!chk1.isPalindrome(x) || !chk2.isPalindrome(x)) {
                out.println("YES");
                return;
            }
        }
        out.println("NO");
    }

    public class PalindromeChecker {
        public BinaryIndexTree fwdSum;
        public BinaryIndexTree revSum;
        public int[] pow;
        public int length;
        public int mod;

        public PalindromeChecker(int length, int mod) {
            this.fwdSum = new BinaryIndexTree(length);
            this.revSum = new BinaryIndexTree(length);
            this.pow = new int[length + 1];
            this.length = length;
            this.mod = mod;

            pow[0] = 1;
            for (int i = 1; i <= length; i++) {
                pow[i] = (pow[i - 1] << 1) % mod;
            }
        }

        public void mark(int idx) {
            fwdSum.update(idx, pow[idx]);
            revSum.update(idx, pow[length - idx + 1]);
        }

        public boolean isPalindrome(int idx) {
            int range = Math.min(length - idx, idx - 1);
            return fwdHash(idx - range, idx + range) == revHash(idx - range, idx + range);
        }

        public long fwdHash(int l, int r) {
            return (((fwdSum.query(r) - fwdSum.query(l - 1)) % mod) * pow[length - r] % mod);
        }

        public long revHash(int l, int r) {
            return (((revSum.query(r) - revSum.query(l - 1)) % mod) * pow[l - 1] % mod);
        }
    }
}

class InputUtil {

    JoltyScanner in;

    public InputUtil(InputStream istream) {
        in = new JoltyScanner(istream);
    }

    public String next() {
        return in.nextOrNull();
    }

    public int nextInt() {
        String s = next();
        if (s == null) {
            throw new NoSuchElementException("Attempted to read integer that is not there.");
        }
        return Integer.parseInt(s);
    }

}

class BinaryIndexTree {

    int n;
    long[] tree;

    public BinaryIndexTree(int n) {
        this.n = n;
        tree = new long[n + 1];
    }
    public BinaryIndexTree(int[] arr) {
        this.n = arr.length;
        tree = new long[n];
        for (int i = 0; i < n; i++) {
            update(i + 1, arr[i]);
        }
    }
    public void update(int x, long v) {
        while (x <= n) {
            tree[x] += v;
            x += (x & -x);
        }
    }
    public long query(int x) {
        long res = 0;
        while (x > 0) {
            res += tree[x];
            x -= (x & -x);
        }
        return res;
    }

}

class JoltyScanner {
    public static final int BUFFER_SIZE = 1 << 16;
	public static final char NULL_CHAR = (char) -1;

    BufferedInputStream in;
	StringBuilder str = new StringBuilder();
	byte[] buffer = new byte[BUFFER_SIZE];
	boolean EOF_FLAG = false;

    char c = NULL_CHAR;
	int bufferIdx = 0;
    int size = 0;

	public JoltyScanner(InputStream in) {
		this.in = new BufferedInputStream(in, BUFFER_SIZE);
	}

    public String next() {
		checkEOF();
		for (c = c == NULL_CHAR ? nextChar() : c; Character.isWhitespace(c); checkEOF()) {
			c = nextChar();
		}
		str.setLength(0);
		for (; !EOF_FLAG && !Character.isWhitespace(c); c = nextChar()) {
			str.append(c);
		}
		return str.toString();
	}

	public String nextOrNull() {
		try {
			return next();
		} catch (EndOfFileException e) {
			return null;
		}
	}

    public char nextChar() {
		if (EOF_FLAG) {
			return NULL_CHAR;
		}
		while (bufferIdx == size) {
			try {
				size = in.read(buffer);
				if (size == -1) {
					throw new Exception();
				}
			} catch (Exception e) {
				EOF_FLAG = true;
				return NULL_CHAR;
			}
			if (size == -1) {
				size = BUFFER_SIZE;
			}
			bufferIdx = 0;
		}
		return (char) buffer[bufferIdx++];
	}

    public void checkEOF() {
		if (EOF_FLAG) {
			throw new EndOfFileException();
		}
	}

	public class EndOfFileException extends RuntimeException {
	}
}

