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.

见题面

见题面