Lets define G(x, {A_{1}, A_{2}, A_{3}, ..., A_{x}}) as a game played by 2 players in which we have x piles of stones with ith pile having A_{i} stones. Player 1 moves first. The players move alternatively. In a move a player can select a single non empty pile of stones and remove any number ( > 0 ) of stones from it. When a player cannot make a move, the player loses.

Adarsh and Saharsh are playing a modification of this game. There are N piles of stones lined up and ith pile has A_{i} number of stones. Saharsh needs to divide the N piles into disjoint contiguous segments. It is possible for a pile to not belong in a segment at all. The segments need to be selected in such a way such that, if ith pile is in a segment, then all the j's such that A_{i} = A_{j}, are also in the segment. Now they play games on these segments considering only the 'distinct sized piles' in the segment with Adarsh as Player 1 and Saharsh as Player 2.

Consider A = {1, 1, 2, 3, 3, 2}.

A possible division is {1, 1} and {2, 3, 3, 2}. 

For the segment {1, 1}, game G(1, {1}) would be played. For the segment {2, 3, 3, 2}, game G(2, {2, 3}) would be played.
      
G(1, {1}) would be won by Player 1
G(2, {2, 3}) would be won by Player 1
      
So number of games that Player 2 wins would be 0.

Another possible division is {1, 1, 2, 3, 3, 2}. 

For the segment {1, 1, 2, 3, 3, 2}, game G(3, {1, 2, 3}) would be played. 
G(3, {1, 2, 3}) would be won by Player 2
So number of games that Player 2 wins would be 1.

What is the maximum possible games that Saharsh can win?

------ Input Format: ------ 
 
The first line contains an integer N, the number of piles.

Next line contains N space separated integers where ith integer denotes number of stones in the ith pile, A_{i}.

------ Output Format: ------ 

For each test case, output the corresponding answer.

------ Constraints: ------ 

$1≤ N ≤500000$
$1≤ A_{i} ≤500000$

------ Sample Input: ------ 

6

1 1 2 3 3 2

------ Sample Output: ------ 

1

------ Explanation: ------ 

Given in the problem statement.

Source: codechef | Difficulty: VERY_HARD
Tags: Dynamic programming


Solutions:
import sys
import numpy as np
MAX = 1000005
a = []
x = []
l = np.zeros(MAX)
r = np.zeros(MAX)
dp = np.zeros(MAX)
last = []
n = int(sys.stdin.readline())
h = sys.stdin.readline().split()
for i in range(1, n + 1):
	p = int(h[i - 1])
	if l[p] == 0:
		l[p] = i
	r[p] = i
for i in range(1, 500001):
	if l[i] and r[i]:
		a.append((l[i], r[i], i))
a.sort()
a.append((n + 7, n + 7, i))
xx = a[0][0]
yy = a[0][1]
ii = a[0][2]
x.append(0)
for i in range(1, len(a)):
	if a[i][0] < yy:
		ii ^= a[i][2]
		if a[i][1] > yy:
			yy = a[i][1]
	else:
		x.append(ii)
		xx = a[i][0]
		yy = a[i][1]
		ii = a[i][2]
n = len(x)
cxor = x[0]
for i in range(MAX):
	last.append(-1)
last[0] = 0
for i in range(1, n):
	cxor ^= x[i]
	if last[cxor] != -1:
		dp[i] = max(dp[i - 1], 1 + dp[last[cxor]])
	else:
		dp[i] = dp[i - 1]
	last[cxor] = i
print(int(dp[n - 1]))