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.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Locale;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Solution implements Runnable {

    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok = new StringTokenizer("");

    public static void main(String[] args) {
        new Thread(null, new Solution(), "", 256 * (1L << 20)).start();
    }

    public void run() {
        try {
            long t1 = System.currentTimeMillis();
            if (System.getProperty("ONLINE_JUDGE") != null) {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                in = new BufferedReader(new FileReader("input.txt"));
                out = new PrintWriter("output.txt");
            }
            Locale.setDefault(Locale.US);
            solve();
            in.close();
            out.close();
            long t2 = System.currentTimeMillis();
            System.err.println("Time = " + (t2 - t1));
        } catch (Throwable t) {
            t.printStackTrace(System.err);
            System.exit(-1);
        }
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }

    int readInt() throws IOException {
        return Integer.parseInt(readString());
    }

    long readLong() throws IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }
    
    boolean readBoolean() throws IOException {
        return Boolean.parseBoolean(readString());
    }

    // solution
    void solve() throws IOException {
        int n = readInt();
        int[] nums = new int[n];
        int[] p = new int[5555555];
        for(int i =0;i<n;i++){
            nums[i]=readInt();
            p[nums[i]]=i;
        }
        int limit = 100;
        for(int i =0; i < n-1; i++){
            for(int j = i+2;j<Math.min(n,i+limit);j++){
                int temp = nums[i]+nums[j];
                if(temp%2==0){
                    temp = temp/2;
                    if(p[temp]>i&&p[temp]<j){
                        out.println("YES");
                        return;
                    }
                }
            }
        }
        for(int i =0; i < n-1; i++){
            for(int j = i+1;j<Math.min(n,i+limit);j++){
                int temp = 2*nums[j]-nums[i];
                if(temp>0 && p[temp]>0 && p[temp]>j){
                    out.println("YES");
                    return;
                }
            }
        }
        
        for(int i =0; i < n-1; i++){
            for(int j = i+1;j<Math.min(n,i+limit);j++){
                int temp = 2*nums[i]-nums[j];
                if(temp>0 && p[temp]>0 && p[temp]<i){
                    out.println("YES");
                    return;
                }
            }
        }
        out.println("NO");
    }
    
}