32170번 - 나무 키우기

문제

현제는 일렬로 심어져 있는 $N$개의 나무를 키운다. 초기 각 나무의 높이는 왼쪽에서부터 각각 $A_1,ドル $A_2,ドル $\cdots,ドル $A_N$이다.

현제는 첫 번째 날부터 매일 가장 높이가 작은 나무를 하나 골라 물을 줘서 나무의 높이를 2ドル$배로 만든다. 만약 높이가 가장 작은 나무가 2ドル$개 이상이라면, 가장 왼쪽에 있는 나무에 물을 준다.

이때 아래의 쿼리를 수행하는 프로그램을 작성하여라.

• $X$ $K$: $X$번째 날까지 물을 주고 난 후, $K$번째로 작은 나무의 높이를 10ドル^9+7$로 나눈 나머지를 구한다.

입력

첫 번째 줄에 나무의 수 $N$이 주어진다. (1ドル\le N\le 300,000円$)

다음 줄에 나무의 높이 $A_1,ドル $A_2,ドル $\cdots,ドル $A_N$이 공백을 사이에 두고 주어진다. (1ドル\le A_i\le 300,000円$)

다음 줄에 쿼리의 수 $Q$가 주어진다. (1ドル\le Q\le 300,000円$)

그 후 $Q$개의 줄에 쿼리의 정보 $X,ドル $K$가 공백을 사이에 두고 주어진다. (1ドル\le X\le 10^9$; 1ドル\le K\le N$)

모든 입력은 정수이다.

출력

$Q$개의 줄에 쿼리의 정답을 차례대로 한 줄에 하나씩 출력한다.

제한

힌트