Permutation

#include "bits/stdc++.h"

/*
 * Author: Matheus Monteiro
 */

using namespace std;
#define fastio std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);

const int mod = 1000000007; //10^9 + 7
const int n = 300010;
int prime = 1238473;
vector<int> pot;
vector<int> h1;
vector<int> h2;

inline int normalize(long long x) {
    x = x % mod;
    if(x < 0) x += mod;
    return x;
}

inline int add(int a, int b) {
    return normalize(normalize(a) + normalize(b));
}

inline int prod(int a, int b) {
    return normalize(normalize(a) * 1ll * normalize(b));
}

inline int sub(int a, int b) {
    return normalize(normalize(a) - normalize(b));
}

inline int expMod(int x, int e) {
    int ans = 1;
    while(e > 0) {
        if(e & 1LL) ans = prod(ans, x), e--;
        else x = prod(x, x), e /= 2;
    }
    return normalize(ans);
}

inline int inv(int x) {
    return expMod(x, mod - 2);
}

inline int qry(int p) {
    int h_val = 0;
    while(p) h_val = add(h1[p], h_val), p -= p & (-p);
    return h_val;
}

inline void upd(int p, int val) {
    val = prod(val, pot[p - 1]);
    while(p <= n) h1[p] = add(h1[p], val), p += p & (-p);
}

inline int hashVal(int l, int r) {
    return prod(sub(qry(r), qry(l - 1)), inv(pot[l - 1]));
}

inline int qryRev(int p) {
    int h_val = 0;
    while(p <= n) h_val = add(h2[p], h_val), p += p & (-p);
    return h_val;
}

inline void updRev(int p, int val) {
    val = prod(val, pot[n - p]);
    while(p) h2[p] = add(h2[p], val), p -= p & (-p);
}

inline int hashValRev(int l, int r) {
    return prod(sub(qryRev(l), qryRev(r + 1)), inv(pot[n - r]));
}

void solve() {
    h1.resize(n + 1);
    h2.resize(n + 1);

    int m;
    bool flag = false;
    cin >> m;

    for(int i = 1; i <= n; ++i) {
        upd(i, 2);
        updRev(i, 2);
    }

    for(int i = 1; i <= m; ++i) {
        int x;
        cin >> x;

        upd(x, -1);
        updRev(x, -1);

        int k = min(x, m - x);

        if(hashVal(x - k + 1, x + k - 1) != hashValRev(x - k + 1, x + k - 1)) {
            flag = true;
            break;
        }
    }

    if(flag) cout << "YES\n";
    else cout << "NO\n";
}

int32_t main() {
    fastio;

    pot.resize(n + 1);
    pot[0] = 1;
    for(int i = 1; i <= n; ++i) {
        pot[i] = prod(pot[i - 1], prime);
    }

    solve();

    return 0;
}