나무 키우기

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

현제는 첫 번째 날부터 매일 높이가 가장 작은 나무를 하나 골라 물을 준다. 물을 받은 나무의 높이는 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$)

모든 입력은 정수이다.

각 쿼리의 정답을 입력된 순서대로 한 줄에 하나씩 출력한다.