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.*;
import java.lang.*;
import static java.lang.Math.*;
import java.lang.reflect.*;
import java.math.BigInteger;
import static java.math.BigInteger.*;
import java.security.CodeSource;
import java.security.KeyStore;
import java.util.*;
import static java.util.Arrays.*;
import java.util.jar.JarEntry;
import java.util.jar.JarFile;
import java.util.logging.Level;
import java.util.logging.Logger;

// https://netbeans.org/kb/73/java/editor-codereference_ru.html#display
public class Main {
    //<editor-fold defaultstate="collapsed" desc="Your Fold Super Code">

    private void run() {
        Locale.setDefault(Locale.US);
        boolean oj = true;
        try {
            oj = System.getProperty("MYLOCAL") == null;
        } catch (Exception e) {
        }

        if (oj) {
            sc = new FastScanner(new InputStreamReader(System.in));
            out = new PrintWriter(new OutputStreamWriter(System.out));
        } else {
            try {
                sc = new FastScanner(new FileReader("input.txt"));
                out = new PrintWriter(new FileWriter("output.txt"));
            } catch (IOException e) {
                MLE();
            }
        }
        solve();
        //if( oj )
        err.println("Time: " + (System.currentTimeMillis() - timeBegin) / 1e3);
        out.flush();
    }

    private void show(int[] arr) {
        for (int v : arr) {
            err.print(" " + v);
        }
        err.println();
    }

    private boolean eq(String a, String b) {
        for (int i = 0; i < a.length(); ++i) {
            if (a.charAt(i) == '.') {
                continue;
            }
            if (b.charAt(i) == '.') {
                continue;
            }
            if (a.charAt(i) != b.charAt(i)) {
                return false;
            }
        }
        return true;
    }

    class FastScanner {

        BufferedReader br;
        StringTokenizer st;

        FastScanner(InputStreamReader reader) {
            br = new BufferedReader(reader);
            st = new StringTokenizer("");
        }

        String next() {
            while (!st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException ex) {
                    Main.MLE();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }

    public static void MLE() {
        int[][] arr = new int[1024 * 1024][];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new int[1024 * 1024];
        }
    }

    public static void main(String[] args) {
        new Main().run();
    }

    long timeBegin = System.currentTimeMillis();
    FastScanner sc;
    PrintWriter out;
    PrintStream err = System.err;

    // </editor-fold>
    void solve() {
//        Hasher h = new Hasher(9);
//        
//        h.set( 2 );
//        err.println( h.getHash(2, 3) );
//        err.println( h.getRevHash(5, 6));
//        
//        h.set( 6 );
//        err.println( h.getHash(2, 3) );
//        err.println( h.getRevHash(5, 6));
        
        int n;
        Hasher hash;
        
        n = sc.nextInt();
        hash = new Hasher(n);
        for (int iter = 1; iter <= n; iter++) {
            int x = sc.nextInt();
            int l = min( x-1, n-x );
            if( l != 0 ){
                if( hash.getHash(x-l, x-1) != hash.getRevHash(x+1, x+l) ){
                    out.println( "YES" );
                    return;
                }
            }
            hash.set(x);
        }
        out.println( "NO" );
    }

}

class Hasher {

    int n;
    long[] pow, tree0, tree1;
    final long base = 31357;//valueOf(31341).nextProbablePrime().longValue();
//    {System.err.println(base);}

    public Hasher(int _n) {
        n = _n;
        pow = new long[_n + 1];
        pow[0] = 1;
        for (int i = 1; i < pow.length; i++) {
            pow[i] = pow[i - 1] * base;
        }
        tree0 = new long[n+1];
        tree1 = new long[n+1];
    }
    
    public void set( int pos ) {
        long add0 = pow[pos];
        long add1 = pow[n-pos+1];
        for( int i = pos; i <= n; i = (i+1) | i  ){
            tree0[i] += add0;
            tree1[i] += add1;
        }
    }

    long sum(int r, long[] tree) {
        long sum = 0;
        for (int i = r; 0 <= i; i = (i & (i + 1)) - 1) {
            sum += tree[i];
        }
        return sum;
    }

    public long getHash(int l, int r) {
        try {
            return (sum(r, tree0) - sum(l - 1, tree0)) * pow[pow.length - 1 - r];
        } catch (Exception e) {
            return 0;
        }
    }

    public long getRevHash(int l, int r) {
        return (sum(r, tree1) - sum(l - 1, tree1)) * pow[pow.length - 1 - (n-l+1)];
    }
}
