Odd query - MarisaOJ: Marisa Online Judge

Given a sequence of length

n

$n$ as

a_{1}, a_{2}, \dots, a_{n}

$a_1, a_2, \dots, a_n$ . There are a total of

m

$m$ queries, each query specifies

l, r

$l, r$ , and requires finding the number of subarrays

[i, j]

$[i, j]$ within the range

[l, r]

$[l, r]$ such that

l \leq i \leq j \leq r

$l \leq i \leq j \leq r$ and the number of distinct elements in the subarray

[i, j]

$[i, j]$ is odd. ### Input - The first line is an integer

n

$n$ . - The next line contains

n

$n$ integers representing the sequence

a_{1}, a_{2}, \dots, a_{n}

$a_1, a_2, \dots, a_n$ . - The following line contains an integer

m

$m$ . - The next

m

$m$ lines each contain two integers

l

$l$ and

r

$r$ representing a query. ### Output For each query, output a single integer on a new line, which is the result. ### Constraints -

n, m, a_{i} \leq 10^{6}

$n, m, a_i \leq 10^6$ -

1 \leq l \leq r \leq n

$1 \leq l \leq r \leq n$ ### Example #1 #### Input #1

52351552311132524

$5 2 3 5 1 5 5 2 3 1 1 1 3 2 5 2 4$

#### Output #1

21464

$2 1 4 6 4$

### Example #2 #### Input #2

10285110599351068123557173949143725

$10 2 8 5 1 10 5 9 9 3 5 10 6 8 1 2 3 5 5 7 1 7 3 9 4 9 1 4 3 7 2 5$

#### Output #2

4244161612696

$4 2 4 4 16 16 12 6 9 6$

Topic

Data structure

Rating

2000

Solution (0)

Solution