区间不同数之和

题目描述

有$n$个数$a_1, a_2, \dots, a_n$。

有$q$组询问，每次给一个区间$[l, r]$，求区间里不同的数字之和，也就是说同一个数字出现多次只算一次。

输入格式

第一行两个数$n,q (1\leq n, q\leq 2\times 10^5)$。

接下来一行，一共$n$个数$a_1, a_2, \dots, a_n (1\leq a_i\leq n)$。

接下来$q$行，每行两个整数$l, r (1\leq l\leq r \leq n)$。

输出格式

对于每个询问，每行输出一个数表示答案。

样例输入

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

样例输出

6
5
5
2
6