만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

Prof. Pang의 수열

시간 제한3초메모리 제한1024 MB

요약
각 질의 구간 [l, r]에서 서로 다른 값의 개수가 홀수인 부분 배열 (i, j)의 쌍을 셉니다.
난이도

어려움10점 중 10점

유형
분할 정복, 배열, 해시맵, 동적 계획법
정답자
아직 제출이 없습니다

문제

Prof. Pang은 고정된 수열 a1,…,ana_1, \ldots, a_n과 mm개의 질의를 받는다.

각 질의는 두 정수 ll, rr로 주어지며 1≤l≤r≤n1\le l\le r\le n을 만족한다. 각 질의마다 l≤i≤j≤rl\le i\le j\le r을 만족하는 정수 쌍 (i,j)(i, j) 중에서 ai,…,aja_i, \ldots, a_j에 포함된 서로 다른 정수의 개수가 홀수인 쌍의 수를 구한다.

입력

첫 줄에 정수 nn (1≤n≤5×1051\le n\le 5\times 10^5)이 주어진다.

둘째 줄에 nn개의 정수 a1,…,ana_1, \ldots, a_n (1≤ai≤n1\le a_i\le n)이 공백 한 칸으로 구분되어 주어진다.

다음 줄에 정수 mm (1≤m≤5×1051\le m\le 5\times 10^5)이 주어진다.

이후 mm개의 줄에 각각 두 정수 ll, rr (1≤l≤r≤n1\le l\le r\le n)이 공백 한 칸으로 구분되어 주어진다.

출력

각 질의에 대한 답을 한 줄에 하나씩 출력한다.

예제3

  1. 예제 1

    입력
    5
1 2 3 2 1
5
1 5
2 4
1 3
2 5
4 4
    예상 출력
    10
3
4
6
1

  2. 예제 2

    입력
    5
2 3 5 1 5
5
2 3
1 1
1 3
2 5
2 4
    예상 출력
    2
1
4
6
4

  3. 예제 3

    입력
    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
    예상 출력
    4
2
4
4
16
16
12
6
9
6