Sumex

You are given a sequence $a\_1,\dots , a\_n$ and $q$ independent queries. In each query you are given two integers $l$ and $r$. Consider the sequence $a\_l , a\_{l+1}, \dots , a\_r$. Your task is to compute the sum of the minimum excluded element of all sequences of form $a\_i , a\_{i+1}, \dots , a\_j$, for $l \le i \le j \le r$.

The minimum excluded element of a sequence is the smallest non-negative integer that does not appear in the sequence. For example, for the sequence $0$, $1$, $4$, $2$ it is $3$, but for the sequence $1$, $2$, $3$, $4$ it is $0$.

The first line contains the integers $n$ and $q$. The second line contains $n$ integers $a\_1, a\_2, \dots , a\_n$, the initial sequence. Each of the next $q$ lines contains two integers $l$ and $r$, describing one query.

Print the answers to the $q$ queries in order, each on a new line.

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

The answers to the three queries in the sample are $3$, $7$, and $39$. The breakdown for each query lists the minimum excluded element of every subarray inside the query range.