#include "sequence.h"
#include <bits/stdc++.h>

using namespace std;

bool is_inter(pair<int, int> sg1, pair<int, int> sg2) {
    if (sg1.second < sg2.first || sg2.second < sg1.first) return false;
    return true;
}

struct node {
    int sm, minbal, maxbal;
};

node operator+(node a, node b) {
    int nsm = a.sm + b.sm, nminbal = min(a.minbal, a.sm + b.minbal), nmaxbal = max(a.maxbal, a.sm + b.maxbal);
    return {nsm, nminbal, nmaxbal};
}

struct segtree {
    int n;
    vector<int> a;
    vector<node> t;
    segtree() = default;
    segtree(int n_) {
        n = n_;
        a.assign(n, -1);
        t.resize(4 * n);
        build(1, 0, n);
    }

    void build(int v, int tl, int tr) {
        if (tl + 1 == tr) {
            t[v] = {a[tl], min(a[tl], 0), max(a[tl], 0)};
            return;
        }
        int tm = (tl + tr) / 2;
        build(v * 2, tl, tm); build(v * 2 + 1, tm, tr);
        t[v] = t[v * 2] + t[v * 2 + 1];
    }

    void upd(int v, int tl, int tr, int p, int vl) {
        if (tl + 1 == tr) {
            t[v] = {vl, min(0, vl), max(0, vl)};
            return;
        }
        int tm = (tl + tr) / 2;
        if (p < tm) upd(v * 2, tl, tm, p, vl);
        else upd(v * 2 + 1, tm, tr, p, vl);
        t[v] = t[v * 2] + t[v * 2 + 1];
    }

    node get(int v, int tl, int tr, int l, int r) {
        if (tl >= r || tr <= l) return {0, 1000000000, -1000000000};
        if (l <= tl && tr <= r) return t[v];
        int tm = (tl + tr) / 2;
        return get(v * 2, tl, tm, l, r) + get(v * 2 + 1, tm, tr, l, r);
    }
};

struct fenwick {
    int n;
    vector<int> t;
    fenwick() = default;
    fenwick(int n_) {
        n = n_;
        t.assign(n + 1, 0);
    }
 
    void upd(int p, int vl) {
        for (; p <= n; p = (p | (p + 1))) t[p] += vl;
    }
 
    int get(int p) {
        int sm = 0;
        for (; p > 0; p = (p & (p + 1)) - 1) sm += t[p];
        return sm;
    }
};

struct segtree2 {
    int n; 
    vector<int> t;
    segtree2() = default;
    segtree2(int n_) {
        n = n_;
        t.assign(4 * n, -1e9);
    }

    void upd(int v, int tl, int tr, int p, int vl) {
        if (tl + 1 == tr) {
            t[v] = vl;
            return;
        }
        int tm = (tl + tr) / 2;
        if (p < tm) upd(v * 2, tl, tm, p, vl);
        else upd(v * 2 + 1, tm, tr, p, vl);
        t[v] = max(t[v * 2], t[v * 2 + 1]);
    }

    int spusk(int v, int tl, int tr, int l, int r, int val) {
        if (tr <= l || tl >= r) return -1;
        if (l <= tl && tr <= r) {
            if (t[v] < val) return -1;
            if (tl + 1 == tr) return tl;
        }
        int tm = (tl + tr) / 2;
        int rsl = spusk(v * 2, tl, tm, l, r, val);
        if (rsl != -1) return rsl;
        return spusk(v * 2 + 1, tm, tr, l, r, val);
    }
};

int sequence(int N, vector<int> A) {
    vector<vector<int>> pos(N + 1);
    for (int i = 0; i < N; i++) pos[A[i]].push_back(i);
    segtree sg(N);
    fenwick fw(N + 3);
    vector<pair<int, int>> left(N), right(N);
    int tot = -N;
    for (int i = 1; i <= N; i++) fw.upd(i, -1);
    for (int val = 1; val <= N; val++) {
        for (int p : pos[val]) {
            sg.upd(1, 0, N, p, 1);
            fw.upd(p + 1, 2);
        }
        tot += 2 * pos[val].size();
        for (int p : pos[val]) {
            if (p == 0) {
                left[p] = {0, 0};
            } else {
                node rs = sg.get(1, 0, N, 0, p);
                left[p] = {rs.minbal, rs.maxbal};
            }

            if (p == N - 1) {
                right[p] = {tot, tot};
            } else {
                int ls = fw.get(p + 1);
                node rs = sg.get(1, 0, N, p + 1, N);
                right[p] = {ls + rs.minbal, ls + rs.maxbal};
            }
        }
    }
    
    int ans = 1;
    for (int val = 1; val <= N; val++) {
        if (pos[val].empty()) continue;
        segtree2 sg2(pos[val].size());
        for (int i = 0; i < pos[val].size(); i++) sg2.upd(1, 0, pos[val].size(), i, left[pos[val][i]].second - 2 * i + 2);
        for (int i = 1; i < pos[val].size(); i++) {
            int L = -1, R = i;
            while (R - L > 1) {
                int M = (L + R) / 2;
                if (right[i].second - left[pos[val][M]].first < 0) L = M;
                else R = M;
            }
            if (R < i) {
                int result = sg2.spusk(1, 0, pos[val].size(), R, i, right[i].first - 2 * i);
                ans = max(ans, i - result + 1);
            }
            
        }
    }
    return ans;
}