#include <bits/stdc++.h>
#include <unistd.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define MOD 1000000007LL
#define F first
#define S second
#define ll long long
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b)
{
if(a == 0LL)
return b;
return gcd(b, a%b);
}
const int N = 500005;
int A[N], fst[N], lst[N], prev1[N], dp[N], id[N];
map<int, int> M[N];
struct Node{
int mn_fst, mx_lst, xorsum, mn_ind;
void merge(Node& left, Node& right)
{
mn_fst = min(left.mn_fst, right.mn_fst);
mx_lst = max(left.mx_lst, right.mx_lst);
xorsum = left.xorsum^right.xorsum;
mn_ind = min(left.mn_ind, right.mn_ind);
return;
}
void assign(int a, int b, int c, int d)
{
mn_fst = a;
mx_lst = b;
xorsum = c;
mn_ind = d;
return;
}
}tree[N<<2];
Node query(int node, int l, int r, int a, int b)
{
if(l == a && r == b)
return tree[node];
int mid = (l+r)>>1;
int left = node<<1;
int right = left + 1;
if(b<=mid)
return query(left, l, mid, a, b);
else if(a>mid)
return query(right, mid+1, r, a, b);
Node ans;
Node L, R;
L = query(left, l, mid, a, mid);
R = query(right, mid+1, r, mid+1, b);
ans.merge(L, R);
return ans;
}
void update(int node, int l, int r, int ind, Node val)
{
if(l == r)
{
tree[node] = val;
return;
}
int mid = (l+r)>>1;
int left = node<<1;
int right = left + 1;
if(ind<=mid)
update(left, l, mid, ind, val);
else
update(right, mid+1, r, ind, val);
tree[node].merge(tree[left], tree[right]);
return;
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);
// freopen("in6.in", "r", stdin);
// freopen("out6.out", "w", stdout);
// clock_t clk;
// clk = clock();
int n, l, r;
scanf("%d", &n);
// cin >> n;
for(int i = 0; i<N; i++)
{
fst[i] = n+1;
lst[i] = 0;
M[i].clear();
}
for(int i = 1; i<=n; i++)
{
scanf("%d", &A[i]);
// cin >> A[i];
fst[A[i]] = min(fst[A[i]], i);
prev1[i] = lst[A[i]];
lst[A[i]] = i;
}
Node temp, now;
id[0] = 1;
for(int i = 1; i<=n; i++)
{
dp[i] = dp[i-1];
if(prev1[i])
{
temp.assign(fst[A[i]], lst[A[i]], 0, MOD);
update(1, 1, n, prev1[i], temp);
}
temp.assign(fst[A[i]], lst[A[i]], A[i], MOD);
update(1, 1, n, i, temp);
if(lst[A[i]] == i) // Necessary Condition for Valid Subarray
{
l = fst[A[i]];
r = lst[A[i]];
now = query(1, 1, n, l, r);
while(now.mx_lst == i)
{
if(now.mn_fst == l)
break;
// l = min(now.mn_fst, now.mn_ind);
l = now.mn_fst;
now = query(1, 1, n, l, r);
}
// l = min(now.mn_fst, now.mn_ind);
l = now.mn_fst;
temp.assign(fst[A[i]], lst[A[i]], A[i], l);
update(1, 1, n, i, temp);
if(now.mx_lst == i) // Valid Subarray
{
id[i] = id[l-1];
now = query(1, 1, n, id[i], i);
if(M[id[i]][now.xorsum] != 0)
dp[i] = max(dp[i], dp[M[id[i]][now.xorsum]] + 1);
else if(now.xorsum == 0)
dp[i] = max(dp[i], dp[id[i]-1] + 1);
M[id[i]][now.xorsum] = i;
}
else
id[i] = i+1;
}
else
id[i] = i+1;
}
// cout << dp[n] << "\n";
printf("%d\n", dp[n]);
// clk = clock() - clk;
// cout << "Time: " << ((double)clk)/CLOCKS_PER_SEC << "\n";
// printf("Time: %lf\n", ((double)clk)/CLOCKS_PER_SEC);
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNpbmNsdWRlIDx1bmlzdGQuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKIAojZGVmaW5lIG1wIG1ha2VfcGFpcgojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIE1PRCAxMDAwMDAwMDA3TEwKI2RlZmluZSBGIGZpcnN0CiNkZWZpbmUgUyBzZWNvbmQKI2RlZmluZSBsbCBsb25nIGxvbmcKIAp0eXBlZGVmIHBhaXI8aW50LCBpbnQ+IHBpaTsKdHlwZWRlZiBwYWlyPGxsLCBsbD4gcGxsOwogCmxsIGdjZChsbCBhLCBsbCBiKQp7CiAgICBpZihhID09IDBMTCkKICAgICAgICByZXR1cm4gYjsKICAgIHJldHVybiBnY2QoYiwgYSViKTsKfQogCmNvbnN0IGludCBOID0gNTAwMDA1OwppbnQgQVtOXSwgZnN0W05dLCBsc3RbTl0sIHByZXYxW05dLCBkcFtOXSwgaWRbTl07CiAKbWFwPGludCwgaW50PiBNW05dOwogCnN0cnVjdCBOb2RlewogICAgaW50IG1uX2ZzdCwgbXhfbHN0LCB4b3JzdW0sIG1uX2luZDsKIAogICAgdm9pZCBtZXJnZShOb2RlJiBsZWZ0LCBOb2RlJiByaWdodCkKICAgIHsKICAgICAgICBtbl9mc3QgPSBtaW4obGVmdC5tbl9mc3QsIHJpZ2h0Lm1uX2ZzdCk7CiAgICAgICAgbXhfbHN0ID0gbWF4KGxlZnQubXhfbHN0LCByaWdodC5teF9sc3QpOwogICAgICAgIHhvcnN1bSA9IGxlZnQueG9yc3VtXnJpZ2h0LnhvcnN1bTsKICAgICAgICBtbl9pbmQgPSBtaW4obGVmdC5tbl9pbmQsIHJpZ2h0Lm1uX2luZCk7CiAKICAgICAgICByZXR1cm47CiAgICB9CiAKICAgIHZvaWQgYXNzaWduKGludCBhLCBpbnQgYiwgaW50IGMsIGludCBkKQogICAgewogICAgICAgIG1uX2ZzdCA9IGE7CiAgICAgICAgbXhfbHN0ID0gYjsKICAgICAgICB4b3JzdW0gPSBjOwogICAgICAgIG1uX2luZCA9IGQ7CiAKICAgICAgICByZXR1cm47CiAgICB9CiAKfXRyZWVbTjw8Ml07CiAKTm9kZSBxdWVyeShpbnQgbm9kZSwgaW50IGwsIGludCByLCBpbnQgYSwgaW50IGIpCnsKICAgIGlmKGwgPT0gYSAmJiByID09IGIpCiAgICAgICAgcmV0dXJuIHRyZWVbbm9kZV07CiAKICAgIGludCBtaWQgPSAobCtyKT4+MTsKICAgIGludCBsZWZ0ID0gbm9kZTw8MTsKICAgIGludCByaWdodCA9IGxlZnQgKyAxOwogCiAgICBpZihiPD1taWQpCiAgICAgICAgcmV0dXJuIHF1ZXJ5KGxlZnQsIGwsIG1pZCwgYSwgYik7CiAgICBlbHNlIGlmKGE+bWlkKQogICAgICAgIHJldHVybiBxdWVyeShyaWdodCwgbWlkKzEsIHIsIGEsIGIpOwogCiAgICBOb2RlIGFuczsKICAgIE5vZGUgTCwgUjsKICAgIEwgPSBxdWVyeShsZWZ0LCBsLCBtaWQsIGEsIG1pZCk7CiAgICBSID0gcXVlcnkocmlnaHQsIG1pZCsxLCByLCBtaWQrMSwgYik7CiAgICBhbnMubWVyZ2UoTCwgUik7CiAKICAgIHJldHVybiBhbnM7Cn0KIAp2b2lkIHVwZGF0ZShpbnQgbm9kZSwgaW50IGwsIGludCByLCBpbnQgaW5kLCBOb2RlIHZhbCkKewogICAgaWYobCA9PSByKQogICAgewogICAgICAgIHRyZWVbbm9kZV0gPSB2YWw7CiAgICAgICAgcmV0dXJuOwogICAgfQogCiAgICBpbnQgbWlkID0gKGwrcik+PjE7CiAgICBpbnQgbGVmdCA9IG5vZGU8PDE7CiAgICBpbnQgcmlnaHQgPSBsZWZ0ICsgMTsKIAogICAgaWYoaW5kPD1taWQpCiAgICAgICAgdXBkYXRlKGxlZnQsIGwsIG1pZCwgaW5kLCB2YWwpOwogICAgZWxzZQogICAgICAgIHVwZGF0ZShyaWdodCwgbWlkKzEsIHIsIGluZCwgdmFsKTsKIAogICAgdHJlZVtub2RlXS5tZXJnZSh0cmVlW2xlZnRdLCB0cmVlW3JpZ2h0XSk7CiAKICAgIHJldHVybjsKfQogCmludCBtYWluKCkKewogICAgLy8gaW9zOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogICAgLy8gY2luLnRpZSgwKTsKICAgIAogICAgLy8gZnJlb3BlbigiaW42LmluIiwgInIiLCBzdGRpbik7CiAgICAvLyBmcmVvcGVuKCJvdXQ2Lm91dCIsICJ3Iiwgc3Rkb3V0KTsKIAogICAgLy8gY2xvY2tfdCBjbGs7CiAgICAvLyBjbGsgPSBjbG9jaygpOwogICAgCiAgICBpbnQgbiwgbCwgcjsKICAgIHNjYW5mKCIlZCIsICZuKTsKICAgIC8vIGNpbiA+PiBuOwogCiAgICBmb3IoaW50IGkgPSAwOyBpPE47IGkrKykKICAgIHsKICAgICAgICBmc3RbaV0gPSBuKzE7CiAgICAgICAgbHN0W2ldID0gMDsKICAgICAgICBNW2ldLmNsZWFyKCk7CiAgICB9CiAKICAgIGZvcihpbnQgaSA9IDE7IGk8PW47IGkrKykKICAgIHsKICAgICAgICBzY2FuZigiJWQiLCAmQVtpXSk7CiAgICAgICAgLy8gY2luID4+IEFbaV07CiAgICAgICAgZnN0W0FbaV1dID0gbWluKGZzdFtBW2ldXSwgaSk7CiAgICAgICAgcHJldjFbaV0gPSBsc3RbQVtpXV07CiAgICAgICAgbHN0W0FbaV1dID0gaTsKICAgIH0KIAogICAgTm9kZSB0ZW1wLCBub3c7CiAgICBpZFswXSA9IDE7CiAKICAgIGZvcihpbnQgaSA9IDE7IGk8PW47IGkrKykKICAgIHsKICAgICAgICBkcFtpXSA9IGRwW2ktMV07CiAKICAgICAgICBpZihwcmV2MVtpXSkKICAgICAgICB7CiAgICAgICAgICAgIHRlbXAuYXNzaWduKGZzdFtBW2ldXSwgbHN0W0FbaV1dLCAwLCBNT0QpOwogICAgICAgICAgICB1cGRhdGUoMSwgMSwgbiwgcHJldjFbaV0sIHRlbXApOwogICAgICAgIH0gICAKIAogICAgICAgIHRlbXAuYXNzaWduKGZzdFtBW2ldXSwgbHN0W0FbaV1dLCBBW2ldLCBNT0QpOwogICAgICAgIHVwZGF0ZSgxLCAxLCBuLCBpLCB0ZW1wKTsKIAogICAgICAgIGlmKGxzdFtBW2ldXSA9PSBpKSAvLyBOZWNlc3NhcnkgQ29uZGl0aW9uIGZvciBWYWxpZCBTdWJhcnJheQogICAgICAgIHsKICAgICAgICAgICAgbCA9IGZzdFtBW2ldXTsKICAgICAgICAgICAgciA9IGxzdFtBW2ldXTsKIAogICAgICAgICAgICBub3cgPSBxdWVyeSgxLCAxLCBuLCBsLCByKTsKIAogICAgICAgICAgICB3aGlsZShub3cubXhfbHN0ID09IGkpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGlmKG5vdy5tbl9mc3QgPT0gbCkKICAgICAgICAgICAgICAgICAgICBicmVhazsKIAogICAgICAgICAgICAgICAgLy8gbCA9IG1pbihub3cubW5fZnN0LCBub3cubW5faW5kKTsKIAogICAgICAgICAgICAgICAgbCA9IG5vdy5tbl9mc3Q7CiAKICAgICAgICAgICAgICAgIG5vdyA9IHF1ZXJ5KDEsIDEsIG4sIGwsIHIpOwogICAgICAgICAgICB9CiAKICAgICAgICAgICAgLy8gbCA9IG1pbihub3cubW5fZnN0LCBub3cubW5faW5kKTsKIAogICAgICAgICAgICBsID0gbm93Lm1uX2ZzdDsKIAogICAgICAgICAgICB0ZW1wLmFzc2lnbihmc3RbQVtpXV0sIGxzdFtBW2ldXSwgQVtpXSwgbCk7CiAgICAgICAgICAgIHVwZGF0ZSgxLCAxLCBuLCBpLCB0ZW1wKTsKIAogICAgICAgICAgICBpZihub3cubXhfbHN0ID09IGkpIC8vIFZhbGlkIFN1YmFycmF5CiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGlkW2ldID0gaWRbbC0xXTsKICAgICAgICAgICAgICAgIG5vdyA9IHF1ZXJ5KDEsIDEsIG4sIGlkW2ldLCBpKTsKIAogICAgICAgICAgICAgICAgaWYoTVtpZFtpXV1bbm93LnhvcnN1bV0gIT0gMCkKICAgICAgICAgICAgICAgICAgICBkcFtpXSA9IG1heChkcFtpXSwgZHBbTVtpZFtpXV1bbm93LnhvcnN1bV1dICsgMSk7CiAgICAgICAgICAgICAgICBlbHNlIGlmKG5vdy54b3JzdW0gPT0gMCkKICAgICAgICAgICAgICAgICAgICBkcFtpXSA9IG1heChkcFtpXSwgZHBbaWRbaV0tMV0gKyAxKTsKIAogICAgICAgICAgICAgICAgTVtpZFtpXV1bbm93LnhvcnN1bV0gPSBpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgIGlkW2ldID0gaSsxOwogICAgICAgIH0KICAgICAgICBlbHNlCiAgICAgICAgICAgIGlkW2ldID0gaSsxOwogICAgfQogICAgCiAgICAvLyBjb3V0IDw8IGRwW25dIDw8ICJcbiI7CiAgICBwcmludGYoIiVkXG4iLCBkcFtuXSk7CiAKICAgIC8vIGNsayA9IGNsb2NrKCkgLSBjbGs7CiAgICAvLyBjb3V0IDw8ICJUaW1lOiAiIDw8ICgoZG91YmxlKWNsaykvQ0xPQ0tTX1BFUl9TRUMgPDwgIlxuIjsKICAgIC8vIHByaW50ZigiVGltZTogJWxmXG4iLCAoKGRvdWJsZSljbGspL0NMT0NLU19QRVJfU0VDKTsKIAogICAgcmV0dXJuIDA7Cn0g