Sumex

길이 $n$의 수열 $a\_1,\dots , a\_n$과 서로 독립적인 $q$개의 질의가 주어진다. 각 질의에서는 두 정수 $l$과 $r$이 주어진다. 수열 $a\_l , a\_{l+1}, \dots , a\_r$을 고려한다. $l \le i \le j \le r$을 만족하는 모든 $a\_i , a\_{i+1}, \dots , a\_j$ 형태의 부분 수열에 대해 최소 배제 원소의 합을 구하라.

수열의 최소 배제 원소는 수열에 나타나지 않는 가장 작은 음이 아닌 정수이다. 예를 들어 수열 0, 1, 4, 2의 최소 배제 원소는 3이고, 수열 1, 2, 3, 4의 최소 배제 원소는 0이다.

첫 줄에 정수 $n$과 $q$가 주어진다. 둘째 줄에는 초기 수열을 나타내는 정수 $n$개 $a\_1, a\_2, \dots , a\_n$이 주어진다. 이어지는 $q$개의 줄에는 각각 질의를 나타내는 두 정수 $l$과 $r$이 주어진다.

$q$개 질의의 답을 입력 순서대로 한 줄에 하나씩 출력한다.

• $1 \le n, q \le 2 \times 10^5$
• $0 \le a\_i \le n$
• $1 \le l \le r \le n$

샘플의 세 질의에 대한 답은 순서대로 $3$, $7$, $39$이다. 각 질의마다 질의 범위 안의 모든 부분 수열에 대한 최소 배제 원소가 나열되어 있다.