Unique Stack and Odd Sum Pairs

You are given a series of operations performed on a stack. Initially, the stack is empty. For each operation, a number is pushed onto the top of the stack. However, the stack must contain only unique numbers. If the number being pushed already exists in the stack, the previous occurrence of that number is removed while the relative order of the other elements remains unchanged, and then the new number is pushed.

After all operations, you need to count the number of adjacent pairs in the stack whose sum is odd. Formally, if the final stack (from bottom to top) is represented as \(a_1, a_2, \ldots, a_k\), you must count the number of indices \(i\) (\(1 \leq i < k\)) such that

[ (a_i + a_{i+1}) \mod 2 = 1 ]

inputFormat

The input begins with an integer \(n\) (\(1 \leq n \leq 10^5\)), representing the number of operations. The following \(n\) integers, each on the same or separate lines, denote the numbers to be pushed onto the stack in the given order.

outputFormat

Output a single integer, which is the total number of adjacent pairs in the final stack whose sum is an odd number.

sample

3
1 2 3

2