#include "sequence.h"

#include <iostream>
#include <vector>
#include <algorithm>

typedef long long ll;
typedef double lf;

using namespace std;

const int MAXN = 5e5 + 10;

int n, a[MAXN], ans;
vector <int> ocr[MAXN];

struct Node
{
    int mx, mn;
    int lz;
}tr[MAXN << 2];
inline void Pushup(int cur)
{
    tr[cur].mx = max(tr[cur << 1].mx, tr[cur << 1 | 1].mx);
    tr[cur].mn = min(tr[cur << 1].mn, tr[cur << 1 | 1].mn);
}
inline void Calc(int cur, int k)
{
    tr[cur].mx += k, tr[cur].mn += k, tr[cur].lz += k;
}
inline void Pushdown(int cur)
{
    if (!tr[cur].lz) return;
    Calc(cur << 1, tr[cur].lz), Calc(cur << 1 | 1, tr[cur].lz);
    tr[cur].lz = 0;
}
void Build(int cur, int l, int r)
{
    if (l == r) tr[cur].mx = tr[cur].mn = l;
    else
    {
        int mid = l + r >> 1;
        Build(cur << 1, l, mid), Build(cur << 1 | 1, mid + 1, r);
        Pushup(cur);
    }
}
void Update(int cur, int l, int r, int x, int y, int k)
{
    if (x <= l && r <= y) Calc(cur, k);
    else
    {
        Pushdown(cur);
        int mid = l + r >> 1;
        if (x <= mid) Update(cur << 1, l, mid, x, y, k);
        if (y > mid) Update(cur << 1 | 1, mid + 1, r, x, y, k);
        Pushup(cur);
    }
}
pair <int, int> Query(int cur, int l, int r, int x, int y)
{
    if (x <= l && r <= y) return make_pair(tr[cur].mn, tr[cur].mx);
    Pushdown(cur);
    int mid = l + r >> 1;
    if (y <= mid) return Query(cur << 1, l, mid, x, y);
    if (x > mid) return Query(cur << 1 | 1, mid + 1, r, x, y);
    auto res1 = Query(cur << 1, l, mid, x, y), res2 = Query(cur << 1 | 1, mid + 1, r, x, y);
    return make_pair(min(res1.first, res2.first), max(res1.second, res2.second));
}

pair <int, int> sl[MAXN], sr[MAXN];
int t1, t2;

int sequence(int N, vector <int> A)
{
    n = N;
    for (int i = 1; i <= n; i++) a[i] = A[i - 1], ocr[a[i]].push_back(i);
    Build(1, 0, n);
    for (int i = 1; i <= n; i++)
    {
        if (!ocr[i].size()) continue;
        for (auto x : ocr[i]) Update(1, 0, n, x, n, -1);
        auto beg = Query(1, 0, n, 0, ocr[i][0] - 1);
        sl[t1 = 1] = make_pair(beg.first, 0), sr[t2 = 1] = make_pair(beg.second, 0);
        for (int j = 1; j <= ocr[i].size(); j++)
        {
            auto cur = Query(1, 0, n, ocr[i][j - 1], (j == ocr[i].size() ? n : ocr[i][j] - 1));
            if (cur.second + j >= beg.first && cur.first - j <= beg.second) ans = max(ans, j);
            else if (cur.second < beg.first)
            {
                int crs = lower_bound(sl + 1, sl + t1 + 1, make_pair(cur.second + j, 2e9), greater < pair <int, int> >()) - sl;
                ans = max(ans, j - sl[crs].second);
            }
            else
            {
                int crs = lower_bound(sr + 1, sr + t2 + 1, make_pair(cur.first - j, 0)) - sr;
                ans = max(ans, j - sr[crs].second);
            }
            if (cur.first + j < sl[t1].first) sl[++t1] = make_pair(cur.first + j, j);
            if (cur.second - j > sr[t2].first) sr[++t2] = make_pair(cur.second - j, j);
        }
        for (auto x : ocr[i]) Update(1, 0, n, x, n, -1);
    }
    return ans;
}