Sum of Distinct Numbers in an Interval

Problem Description

You are given $n$ numbers $a_1, a_2, \dots, a_n$.

There are $q$ queries. Each query gives an interval $[l, r]$; compute the sum of the distinct numbers in that interval, i.e. if the same number appears multiple times it is counted only once.

Input Format

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 2 \times 10^5$).

The next line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$).

The following $q$ lines each contain two integers $l$ and $r$ ($1 \le l \le r \le n$).

Output Format

For each query, output one line containing the answer.

Sample Input

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

Sample Output

6
5
5
2
6

Constraints

$1 \le n, q \le 2 \times 10^5$, $1 \le a_i \le n$, $1 \le l \le r \le n$.