Let's first solve the problem considering the array as a string with lowercase latin letters. Then the greatest value at any position will be at most 25. At every position we can keep a mask of 25 bits, where the bit corresponding to the value of that position will be on and all other bits will be off. For example, if there is a value 5 in the i’th position, then the mask for the i’th position will have the 5th bit as on and all other bits as off. Now the problem is converted to "How many subarrays [L,R] are there where the XOR of all masks of positions in range [L,R] is 0". This can be done by keeping the prefix XOR and for any position, we need to find the prefix XOR of the current prefix and add to the answer the number of times this XOR value occurred earlier.
The original problem can be solved in the same way, but we cannot keep a mask of 2 * 10^6 bits. Instead, we'll keep the hash of a mask of 2 * 10^6 bits (can be the hash of a string of length 2 * 10^6 with 0’s and 1’s in every position). While calculating the prefix XOR hash, we just need to flip the position in the current hash corresponding to the current value and add to the answer the number of times this hash occurred earlier.
