Туристическое агентство

В одном большом городе очень много достопримечательностей и в него регулярно приезжают толпы туристов. Но просто приезжать в город неинтересно, и туристы любят осматривать достопримечательности. Все туристы --- занятые люди и осматривать две достопримечательности одного и того же типа не собираются. Например, никто не пойдёт в два музея, ведь, чтобы сказать, что ты был в музее, достаточно сходить только в один.

Все $n$ достопримечательностей расположены вдоль главной улицы города. Каждая достопримечальность имеет свой тип --- музей, театр, памятник$\ldots$ Каждый приезжающий турист заказывает в турагенстве экскурсию. Экскурсия представляет из себя проезд по каким-то достопримечательностям, стоящим подряд. Так как туристы живут в разных частях города, то не всем им удобно добираться до главной улицы. Поэтому, для $i$-го туриста есть границы $[l_i; r_i]$ --- отрезок, в который должны попасть начало и конец экскурсии, ведь ему надо не только приехать на неё, ну и уехать потом домой.

Каждый турист хочет осмотреть как можно больше достопримечательностей, но при этом он не будет смотреть более одной достопримечательности одного типа. Помогите турагенству подобрать каждому туристу подходящую ему экскурсию.

В первой строке входного файла задано число $n$ ($1 \le n \le 100,000$) --- количество достопримечательностей в городе. Во второй строке заданы $n$ целых чисел $t_i$ ($1 \le t_i \le 10^9$) --- типы достопримечательностей. В третьей строке задано число $m$ ($1 \le m \le 100,000$) --- количество туристов. Далее, в $m$ строках заданы описания туристов в формате $l_i r_i$ ($1 \le l_i \le r_i \le n$), где $l_i, r_i$ --- отрезок, в который должны попасть начало и конец экскурсии для $i$-го туриста.

В выходной файл для каждого туриста выведите количество осмотренных им достопримечательностей.