//qoj6528
#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 10;
int n, a[N];
basic_string<int> pos[N];

struct node{
    int A, B, lmn, lmx;
    int mnA, mxB;
} t[N*4];

void upd(node &x, node &y, node &z){
    x.A = y.A + z.A;
    x.B = y.B + z.B;
    x.lmn = min(z.lmn, z.A + y.lmn);
    x.lmx = max(z.lmx, z.A + y.lmx);
    x.mnA = min(z.mnA, z.A + y.mnA);
    x.mxB = max(z.mxB, z.B + y.mxB);
}
void add(int p, int l, int r, int x, int op, int v){
    if(x < 1 || x > n){
        return;
    }
    if(l == r){
        if(op == 1){
            t[p].A = t[p].mnA = v;
            t[p].lmn = min(0, v);
            t[p].lmx = max(0, v);
        } else {
            t[p].B = t[p].mxB = v;
        }
    } else {
        int mid = l + r >> 1;
        if(x <= mid){
            add(p<<1, l, mid, x, op, v);
        } else {
            add(p<<1|1, mid+1, r, x, op, v);
        }
        upd(t[p], t[p<<1], t[p<<1|1]);
    }
}
node qry(int p, int l, int r, int ql, int qr){
    if(qr < ql){
        return {0, 0, 0, 0};
    }
    if(ql <= l && r <= qr){
        return t[p];
    } else {
        int mid = l + r >> 1;
        if(qr <= mid){
            return qry(p<<1, l, mid, ql, qr);
        } else if(mid < ql){
            return qry(p<<1|1, mid+1, r, ql, qr);
        } else {
            node x;
            node y = qry(p<<1, l, mid, ql, qr);;
            node z = qry(p<<1|1, mid+1, r, ql, qr);
            upd(x, y, z);
            return x;
        }
    }
}
int qcnt(int l, int r){
    if(l > r){
        return 0;
    }
    node tmp = qry(1, 1, n, l, r);
    return (tmp.A - tmp.B) / 2;
}
int qmna(int p, int l, int r, int v){
    if(l == r){
        return t[p].mnA <= v ? l : -1;
    } else {
        int mid = l + r >> 1;
        if(t[p<<1|1].mnA <= v){
            return qmna(p<<1|1, mid+1, r, v);
        } else {
            return qmna(p<<1, l, mid, v-t[p<<1|1].A);
        }
    }
}
int qmxb(int p, int l, int r, int v){
    if(l == r){
        return t[p].mxB >= v ? l : -1;
    } else {
        int mid = l + r >> 1;
        if(t[p<<1|1].mxB >= v){
            return qmxb(p<<1|1, mid+1, r, v);
        } else {
            return qmxb(p<<1, l, mid, v-t[p<<1|1].B);
        }
    }
}

int sequence(int nN, std:: vector<int> A){
    n = nN;
    int nw = 1, sumr = n, suml = n;
    for(int i = 1; i <= n; ++ i){
        pos[i].push_back(0);
    }
    for(int i = 1; i <= n; ++ i){
        a[i] = A[i-1];
        pos[a[i]].push_back(i);
        add(1, 1, n, i, 1, 1);
        add(1, 1, n, i, 2, 1);
    }
    for(int i = 1; i <= n; ++ i){
        pos[i].push_back(n + 1);
    }
    for(int i = 1; i <= n; ++ i){
        int len = pos[i].size() - 2;
        for(int j = 1; j <= len; ++ j){
            add(1, 1, n, pos[i][j], 2, -1);
            suml -= 2;
        }
        for(int j = 1; j <= len; ++ j){
            int ans = 0;
            int l = pos[i][j], le = pos[i][j-1] + 1;
            node tmp = qry(1, 1, n, le, l-1);
            int kmn = -tmp.lmx, kmx = -tmp.lmn;
            tmp = qry(1, 1, n, 1, l-1);
            int sr = sumr - tmp.A, sl = suml - tmp.B;
            if(sl <= kmx && kmx <= sr){
                ans = qcnt(l, n);
            } else if(sl <= kmn && kmn <= sr){
                ans = qcnt(l, n);
            } else if(sr < kmn){
                ans = qcnt(l, qmna(1, 1, n, sr - kmn));
            } else if(kmx < sl){
                ans = qcnt(l, qmxb(1, 1, n, sl - kmx));
            } else {
                ans = qcnt(l, n);
            }
            nw = max(nw, ans);
        }
        for(int j = 1; j <= len; ++ j){
            add(1, 1, n, pos[i][j], 1, -1);
            sumr -= 2;
        }
    }
    return nw;
}

#ifndef ONLINE_JUDGE
int main(){
    freopen("1.in", "r" ,stdin);
    freopen("1.out", "w", stdout);
    int n;
    vector<int> v;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i){
        int p;
        scanf("%d", &p);
        v.push_back(p);
    }
    printf("%d\n", sequence(n, v));
    return 0;
}
#endif