Odd Distinct Subintervals

Given a sequence \(a_1, a_2, \dots, a_n\) of length \(n\), and \(m\) queries. Each query is described by two integers \(l\) and \(r\). For each query, you are required to count the number of subintervals \([i,j]\) satisfying \(l \le i \le j \le r\) such that the number of distinct elements in the subinterval is odd.

Formally, for a subinterval \([i,j]\) (with \(l \le i \le j \le r\)), let \(f(i,j)\) denote the number of distinct elements in \(\{a_i, a_{i+1}, \dots, a_j\}\). You need to count the number of pairs \((i, j)\) for which \(f(i,j)\) is an odd number.

inputFormat

The first line contains two integers \(n\) and \(m\) -- the length of the sequence and the number of queries, respectively. The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\). Each of the next \(m\) lines contains two integers \(l\) and \(r\), representing a query.

outputFormat

For each query, output a single integer -- the number of subintervals \([i,j]\) in the range \([l,r]\) which have an odd number of distinct elements. Print each answer on a new line.

sample

3 2
1 2 1
1 3
2 3

3
2