30207번 - 식당지원 차출

문제

병영 식당 주변 부대 병사가 병영 식당에 가서 식당 업무를 보조하는 일을 식당지원이라고 한다. 식당지원 담당은 누가 언제 식당지원을 할지 정하는 업무를 맡고 있다.

초기에 식당지원 담당은 매일 무작위로 3ドル$명의 병사를 차출해서 식당으로 보내고 있었다. 매일 식당지원을 할 병사를 차출하는 것이 귀찮아진 식당지원 담당은 좀 더 편하고 체계적인 차출을 위해 식당지원 차출 프로그램을 만들었다.

식당지원 차출 프로그램은 매일 아침 차출을 진행하며, 차출일 기준으로 식당지원을 적게 한 병사부터 차출한다. 즉, 식당지원 차출 프로그램 가동 이전에 무작위로 차출된 횟수와 식당지원 차출 프로그램 가동 시작일부터 차출일 직전까지 식당지원 차출 프로그램에 의해 차출된 횟수의 합이 가장 작은 병사 3ドル$명을 선택해서 차출한다. 두 병사의 식당지원 횟수가 같은 경우에는 군번이 작은 병사를 우선해서 차출한다.

이제 식당지원 차출이 무작위로 이루어지지 않는다는 사실을 알게 된 부대의 병사들은 차출 결과를 미리 알고 싶은 나머지 식당지원 담당에게 전화를 걸어 식당지원 차출 프로그램 가동 $d$일차까지 식당지원 차출 프로그램이 자신을 몇 번이나 차출할지 물어보기 시작했다! 식당지원 차출 프로그램의 가동 일수와 병사의 군번이 주어졌을 때 식당지원 차출 프로그램이 해당 병사를 차출한 횟수를 구해주자.

입력

첫 번째 줄에 병사의 수 $N$이 정수로 주어진다. $(3 \le N \le 10,000円)$

두 번째 줄에 군번 1ドル$번인 병사부터 $N$번인 병사까지 각 병사가 식당지원 차출 프로그램 가동 이전에 무작위 차출된 횟수 $a_1, a_2, \cdots, a_N$이 공백으로 구분되어 정수로 주어진다. $(1 \le a_i \le 30)$

세 번째 줄에 전화 문의의 개수 $Q$가 정수로 주어진다. $(1 \le Q \le 100,000円)$

네 번째 줄부터 $Q$줄에 걸쳐 확인하고자 하는 식당지원 차출 프로그램 가동 일수 $d_i$ 와 군번 $x_i$가 공백으로 구분되어 정수로 주어진다. $(1 \le d_i \le 10^9;$ 1ドル \le x_i \le N)$

출력

전화 문의가 들어온 순서대로 $Q$줄에 걸쳐 각 전화 문의에 대한 답을 정수 하나로 출력한다.

제한

힌트