다리

건축가 Marijonas는 산이 일직선으로 늘어선 지역의 교통을 개선하려고 한다. 이 지역은 크기가 $N$인 배열 $A$로 표현되며, $k$번째 산의 높이는 $A[k]$이다.

Marijonas는 두 산 사이에 다리를 놓으려고 한다. 어느 두 산 사이에 놓을지는 아직 정하지 않았지만, $L_i$번째 산과 $R_i$번째 산 사이에 다리를 놓을 때의 건설 비용을 알고 싶어 한다.

건설 비용은 다음과 같이 계산한다.

• 다리의 높이 $M_i$는 양 끝 산 높이의 평균을 내림한 값이다. $M_i = \left\lfloor \frac{A[L_i] + A[R_i]}{2} \right\rfloor$
• 다리는 $L_i \le k_i \le R_i$를 만족하는 모든 산 $k_i$ 위를 지난다.
• 산의 높이 $A[k_i]$가 $M_i$ 이하이면 받침대를 세워야 하며, 이때 비용은 $M_i - A[k_i]$이다.
• 산의 높이 $A[k_i]$가 $M_i$보다 크면 터널을 파야 하며, 이때 비용은 $1$이다.

Marijonas는 다리 하나의 비용은 쉽게 계산할 수 있지만, $Q$쌍의 산 각각에 대한 비용을 알고 싶어 한다. 각 질의에 대한 다리 건설 비용을 구하라.

첫째 줄에 배열의 크기 $N$이 주어진다. 둘째 줄에는 공백으로 구분된 정수 $A[1], A[2], \dots, A[N]$이 주어진다. 셋째 줄에는 질의의 수 $Q$가 주어진다. 이후 $Q$개의 줄에 공백으로 구분된 두 정수 $L_i$와 $R_i$가 한 줄에 하나씩 주어진다.

$Q$개의 줄에 걸쳐 각 질의의 답을 입력 순서대로 한 줄에 하나씩 출력한다. 각 답은 $L_i$번째 산과 $R_i$번째 산 사이에 다리를 놓을 때의 건설 비용이다.

• $1 \le N, Q \le 100\,000$
• $1 \le L_i \le R_i \le N$ ($1 \le i \le Q$)
• $1 \le A[i] \le 10\,000$ ($1 \le i \le N$)