Odd Distinct Segments Query

Professor Pang is given a fixed sequence \(a_1, \ldots, a_n\) and \(m\) queries. Each query is specified by two integers \(l\) and \(r\) satisfying \(1 \le l \le r \le n\). For each query, you should count the number of pairs of integers \((i, j)\) such that \(l \le i \le j \le r\) and the number of distinct integers in the subarray \(a_i, \ldots, a_j\) is odd.

inputFormat

The first line contains two integers \(n\) and \(m\), representing the number of elements in the sequence and the number of queries respectively. The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\). Each of the following \(m\) lines contains two integers \(l\) and \(r\), describing a query.

outputFormat

For each query, output one integer on a new line: the number of pairs \((i, j)\) with \(l \le i \le j \le r\) where the subarray \(a_i, \ldots, a_j\) contains an odd number of distinct integers.

sample

5 3
1 2 1 3 2
1 3
2 5
1 5

3
7
10