관광 여행사

한 대도시에는 명소가 아주 많고, 관광객이 많이 찾아옵니다. 도시에 가기만 해서는 재미가 없어서 관광객들은 명소를 둘러보기를 좋아합니다. 관광객은 모두 바쁜 사람이라 같은 종류의 명소를 두 곳 보려 하지 않습니다. 예를 들어 박물관에 두 번 갈 사람은 없습니다. 박물관에 다녀왔다고 말하는 데는 한 곳이면 충분하기 때문입니다.

도시의 $n$개 명소는 중심 거리를 따라 일렬로 늘어서 있습니다. 명소마다 종류가 정해져 있습니다. 예를 들어 박물관, 극장, 기념물 등이 있습니다. 관광객은 여행사에 투어를 주문합니다. 투어는 연속으로 늘어선 명소들을 지나가는 것입니다. 관광객들은 도시의 서로 다른 지역에 살기 때문에 모두가 중심 거리까지 편하게 가는 것은 아닙니다. 그래서 $i$번째 관광객에게는 구간 $[l_i, r_i]$이 주어집니다. 투어의 시작점과 끝점은 이 구간 안에 있어야 합니다. 관광객은 투어를 마치고 집으로 돌아가야 하기 때문입니다.

각 관광객은 가능한 한 많은 명소를 보고 싶어 하지만, 같은 종류의 명소는 하나를 넘게 보지 않습니다. 각 관광객에게 알맞은 투어를 찾아 주세요.

첫째 줄에 명소의 개수 $n$ ($1 \le n \le 100,000$)이 주어집니다. 둘째 줄에는 각 명소의 종류 $t_i$ ($1 \le t_i \le 10^9$) $n$개가 주어집니다. 셋째 줄에는 관광객의 수 $m$ ($1 \le m \le 100,000$)이 주어집니다. 이어서 $m$개의 줄에 관광객마다 $l_i$와 $r_i$ ($1 \le l_i \le r_i \le n$)가 주어집니다. 이는 투어의 시작과 끝이 들어가야 하는 구간입니다.

각 관광객이 본 명소의 개수를 한 줄에 하나씩 출력합니다.