서로 다른 수와 쿼리 2

정수 $N$개로 이루어진 배열 $A$가 주어진다. 배열의 첫 번째 원소가 1번이다.

다음 쿼리를 $Q$번 처리하는 프로그램을 작성하시오.

• l r: $A$의 $l$번째 수부터 $r$번째 수까지에서 서로 다른 수가 몇 개인지 세어 출력한다.

각 쿼리의 $l$은 직전 쿼리의 정답으로 정해지므로, 쿼리를 주어진 순서대로 하나씩 처리해야 한다.

첫째 줄에 배열의 크기 $N$ ($1 \le N \le 10^6$)이 주어진다.

둘째 줄에 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다. 각 수는 $10^9$ 이하의 자연수이다.

셋째 줄에 쿼리의 개수 $Q$ ($1 \le Q \le 10^6$)가 주어진다.

넷째 줄부터 $Q$개의 줄에 $i$번 쿼리를 나타내는 두 정수 $x_i$와 $r_i$가 주어진다. 쿼리 번호는 1번부터 시작하고, $i$번 쿼리의 왼쪽 끝은 $l_i = x_i + Q_{i-1}$이다. 여기서 $Q_{i-1}$은 $i-1$번 쿼리의 정답이고 $Q_0 = 0$이다.

모든 $i$에 대해 $1 \le l_i \le r_i \le N$이고 $-(N-1) \le x_i \le N-1$이다.

$Q$개의 줄에 각 쿼리의 정답을 입력에 주어진 순서대로 한 줄에 하나씩 출력한다.