题目描述

给定一个长度为 $n$ 的序列 $a_1,a_2,a_3...a_n$，以及 $q$ 次询问，每次询问包含两个参数 $L, R$，请计算出区间 $[L,R]$ 内所有元素去重后的区间和。（即：同一个数字在区间内出现多次，计算区间和时只按一次进行计算）

输入格式

• 第一行：单个整数 $n$，表示序列元素个数；
• 第二行：$n$ 个整数 $a_1,a_2,a_3,\cdots,a_n$；
• 第三行：单个整数 $q$，表示询问次数；
• 接下来$q$行，每行两个整数$L,R$，表示当前询问的区间为$[L,R]$。

输出格式

• 共$q$行，每行一个整数，表示对应询问的答案。

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

6
6
6

数据范围

• $1 \leq n \leq 5\times10^4$
• $1 \leq a_i \leq 10^9$
• $1 \leq q \leq 10^5$
• $1 \leq L \leq R \leq n$