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$개의 줄에 쿼리의 정답을 차례대로 한 줄에 하나씩 출력한다.