마음대로 움직이기

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

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

Huynh은 현재 수직선의 원점으로부터 $P$미터 오른쪽에 서 있다. 이후 Huynh은 $T$초간 매 초 1번씩, 오른쪽으로 1미터 움직이거나 왼쪽으로 1미터씩 움직이려 한다. 단, 장애물이 있는 위치로는 이동할 수 없다. $T$초 뒤, Huynh이 있을 수 있는 위치의 가짓수를 구하여라.

서로 다른 $T, P$ 값들에 대한 질문이 여럿 주어졌을 때, 모든 질문을 해결하라.

첫번째 줄에, 수직선에 있는 장애물의 개수 $K$가 주어진다.

두번째 줄에, 수직선에 있는 각 장애물의 위치 $A_1, \cdots, A_K$가 공백을 사이에 두고 주어진다.

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

이후 $Q$개의 줄에, 각 질문에서의 $T$와 $P$의 값이 공백을 사이에 두고 주어진다.

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

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