마음대로 움직이기

Huynh은 무한한 길이의 수직선 위에 서 있다. 이 수직선에는 $K$개의 장애물이 있다. $i$번째 장애물은 원점에서 오른쪽으로 $A_i$미터 떨어진 곳에 있다. 모든 장애물의 위치는 서로 다르다.

Huynh은 다음 질문을 해결하려 한다.

Huynh은 현재 원점에서 오른쪽으로 $P$미터 떨어진 곳에 서 있다. 이후 Huynh은 $T$초 동안 매 초 오른쪽으로 1미터 또는 왼쪽으로 1미터 움직이려 한다. 단, 장애물이 있는 위치로는 이동할 수 없다. $T$초 뒤 Huynh이 있을 수 있는 위치의 가짓수를 구하라.

서로 다른 $T$, $P$ 값에 대한 질문이 여러 개 주어진다. 모든 질문에 답하라.

첫째 줄에 장애물의 개수 $K$가 주어진다.

둘째 줄에 장애물의 위치 $A_1, \cdots, A_K$가 공백으로 구분되어 주어진다.

셋째 줄에 질문의 개수 $Q$가 주어진다.

이후 $Q$개의 줄에 각 질문의 $T$와 $P$가 공백으로 구분되어 주어진다.

$Q$개의 줄에 걸쳐 출력한다. $i$번째 줄에는 $i$번째 질문의 답을 출력한다.

• $0 \le K \le 100000$
• $-1000000000 \le A_i \le 1000000000$ ($1 \le i \le K$)
• 장애물의 위치는 오름차순으로 주어지며, 서로 다른 장애물은 최소 3미터의 거리를 두고 있다. ($A_i + 3 \le A_{i+1}$을 모든 $1 \le i \le K-1$에 대해 만족한다)
• $1 \le Q \le 100000$
• $1 \le T \le 1000000000$, $-1000000000 \le P \le 1000000000$
• 위치 $P$에는 장애물이 없다. ($A_i \neq P$를 모든 $1 \le i \le K$에 대해 만족한다)