Miyako came to the flea kingdom with a ukulele. She became good friends with local flea residents and played beautiful music for them every day.

In return, the fleas made a bigger ukulele for her: it has n strings, and each string has (10^{18} + 1) frets numerated from 0 to 10^{18}. The fleas use the array s_1, s_2, …, s_n to describe the ukulele's tuning, that is, the pitch of the j-th fret on the i-th string is the integer s_i + j.

Miyako is about to leave the kingdom, but the fleas hope that Miyako will answer some last questions for them.

Each question is in the form of: "How many different pitches are there, if we consider frets between l and r (inclusive) on all strings?"

Miyako is about to visit the cricket kingdom and has no time to answer all the questions. Please help her with this task!

Formally, you are given a matrix with n rows and (10^{18}+1) columns, where the cell in the i-th row and j-th column (0 ≤ j ≤ 10^{18}) contains the integer s_i + j. You are to answer q queries, in the k-th query you have to answer the number of distinct integers in the matrix from the l_k-th to the r_k-th columns, inclusive.

Input

The first line contains an integer n (1 ≤ n ≤ 100 000) — the number of strings.

The second line contains n integers s_1, s_2, …, s_n (0 ≤ s_i ≤ 10^{18}) — the tuning of the ukulele.

The third line contains an integer q (1 ≤ q ≤ 100 000) — the number of questions.

The k-th among the following q lines contains two integers l_k，r_k (0 ≤ l_k ≤ r_k ≤ 10^{18}) — a question from the fleas.

Output

Output one number for each question, separated by spaces — the number of different pitches.

Examples

Input

6
3 1 4 1 5 9
3
7 7
0 2
8 17


Output

5 10 18


Input

2
1 500000000000000000
2
1000000000000000000 1000000000000000000
0 1000000000000000000


Output

2 1500000000000000000

Note

For the first example, the pitches on the 6 strings are as follows.

$$$ \begin{matrix} Fret & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & … \\\ s_1: & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & ... \\\ s_2: & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & ... \\\ s_3: & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & ... \\\ s_4: & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & ... \\\ s_5: & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & ... \\\ s_6: & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & ... \end{matrix} $$$

There are 5 different pitches on fret 7 — 8, 10, 11, 12, 16.

There are 10 different pitches on frets 0, 1, 2 — 1, 2, 3, 4, 5, 6, 7, 9, 10, 11.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
  std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int n;
  cin >> n;
  std::vector<long long> a(n + 1);
  for (int i = 1; i <= n; i++) cin >> a[i];
  sort(a.begin(), a.end());
  std::vector<long long> v(n + 1);
  for (int i = 2; i <= n; i++) v[i] = a[i] - a[i - 1];
  sort(v.begin() + 2, v.begin() + n + 1);
  std::vector<long long> sum(n + 1);
  for (int i = 2; i <= n; i++) sum[i] = sum[i - 1] + v[i];
  int q;
  cin >> q;
  while (q--) {
    long long l, r;
    cin >> l >> r;
    r = r - l + 1;
    int prefix = lower_bound(v.begin(), v.begin() + n + 1, r) - v.begin();
    long long ans = r + sum[prefix - 1] + (n - prefix + 1) * r;
    cout << ans << endl;
  }
  return 0;
}
