J. Уникальные суммы
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны массив чисел a длины n и m запросов. Каждый запрос задаёт отрезок массива, на котором нужно посчитать сумму различных чисел, то есть сумму, в которую каждое число из отрезка входит ровно один раз.

Входные данные

В первой строке содержится целое число n: 1  ≤  n  ≤  105.

Во второй строке содержатся n целых чисел ai, разделённые пробелом: 0  ≤  ai  ≤  109.

В третьей строке содержится целое число m: 1  ≤  m  ≤  106.

Далее следуют m строк с запросами. В каждой строке содержится пара целых чисел Li и Ri, разделённые пробелом: 0  ≤  Li  ≤  Ri  <  n – левая и правая границы отрезка, на котором нужно посчитать сумму различных чисел.

Выходные данные

Выведите m строк, в i-й строке ответ на i-й запрос.

Пример
Входные данные
10
2 10 5 4 10 3 5 10 10 2
11
0 9
1 5
2 4
3 7
3 8
4 7
4 9
5 8
7 7
7 8
8 9
Выходные данные
24
22
19
22
22
18
20
18
10
10
12