description: Recently, Petya learned about a new game "Slay the Dragon". As the name suggests, the player will have to fight with dragons. To defeat a dragon, you have to kill it and defend your castle. To do this, the player has a squad of n heroes, the strength of the i-th hero is equal to a_i.
  
  According to the rules of the game, exactly one hero should go kill the dragon, all the others will defend the castle. If the dragon's defense is equal to x, then you have to send a hero with a strength of at least x to kill it. If the dragon's attack power is y, then the total strength of the heroes defending the castle should be at least y.
  
  The player can increase the strength of any hero by 1 for one gold coin. This operation can be done any number of times.
  
  There are m dragons in the game, the i-th of them has defense equal to x_i and attack power equal to y_i. Petya was wondering what is the minimum number of coins he needs to spend to defeat the i-th dragon.
  
  Note that the task is solved independently for each dragon (improvements are not saved).
  
  Input
  
  The first line contains a single integer n (2 ≤ n ≤ 2 ⋅ 10^5) — number of heroes.
  
  The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^{12}), where a_i is the strength of the i-th hero.
  
  The third line contains a single integer m (1 ≤ m ≤ 2 ⋅ 10^5) — the number of dragons.
  
  The next m lines contain two integers each, x_i and y_i (1 ≤ x_i ≤ 10^{12}; 1 ≤ y_i ≤ 10^{18}) — defense and attack power of the i-th dragon.
  
  Output
  
  Print m lines, i-th of which contains a single integer — the minimum number of coins that should be spent to defeat the i-th dragon.
  
  Example
  
  Input
  
  
  4
  3 6 2 3
  5
  3 12
  7 9
  4 14
  1 10
  8 7
  
  
  Output
  
  
  1
  2
  4
  0
  2
  
  Note
  
  To defeat the first dragon, you can increase the strength of the third hero by 1, then the strength of the heroes will be equal to [3, 6, 3, 3]. To kill the dragon, you can choose the first hero.
  
  To defeat the second dragon, you can increase the forces of the second and third heroes by 1, then the strength of the heroes will be equal to [3, 7, 3, 3]. To kill the dragon, you can choose a second hero.
  
  To defeat the third dragon, you can increase the strength of all the heroes by 1, then the strength of the heroes will be equal to [4, 7, 3, 4]. To kill the dragon, you can choose a fourth hero.
  
  To defeat the fourth dragon, you don't need to improve the heroes and choose a third hero to kill the dragon.
  
  To defeat the fifth dragon, you can increase the strength of the second hero by 2, then the strength of the heroes will be equal to [3, 8, 2, 3]. To kill the dragon, you can choose a second hero.
solution: import java.io.OutputStream;
  import java.io.IOException;
  import java.io.InputStream;
  import java.io.PrintWriter;
  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.util.*;
  
  public class Main {
      public static void main(String[] args){
          InputStream inputStream = System.in;
          OutputStream outputStream = System.out;
          InputReader in = new InputReader(inputStream);
          PrintWriter out = new PrintWriter(outputStream);
          solve(in, out);
          out.close();
      }
  
      static String reverse(String s) {
          return (new StringBuilder(s)).reverse().toString();
      }
  
      static void sieveOfEratosthenes(int n, int factors[], ArrayList<Integer> ar) 
      { 
          factors[1]=1;
          int p;
          for(p = 2; p*p <=n; p++) 
          { 
              if(factors[p] == 0) 
              { 
                  ar.add(p);
                  factors[p]=p;
                  for(int i = p*p; i <= n; i += p) 
                      if(factors[i]==0)
                          factors[i] = p; 
              } 
          } 
          for(;p<=n;p++){
              if(factors[p] == 0) 
              { 
                  factors[p] = p;
                  ar.add(p);
              } 
          }
      }
  
      static void sort(int ar[]) {
          int n = ar.length;
          ArrayList<Integer> a = new ArrayList<>();
          for (int i = 0; i < n; i++)
              a.add(ar[i]);
          Collections.sort(a);
          for (int i = 0; i < n; i++)
              ar[i] = a.get(i);
      }
  
      static void sort1(long ar[]) {
          int n = ar.length;
          ArrayList<Long> a = new ArrayList<>();
          for (int i = 0; i < n; i++)
              a.add(ar[i]);
          Collections.sort(a);
          for (int i = 0; i < n; i++)
              ar[i] = a.get(i);
      }
  
      static void sort2(char ar[]) {
          int n = ar.length;
          ArrayList<Character> a = new ArrayList<>();
          for (int i = 0; i < n; i++)
              a.add(ar[i]);
          Collections.sort(a);
          for (int i = 0; i < n; i++)
              ar[i] = a.get(i);
      }
  
      static long ncr(long n, long r, long mod) {
          if (r == 0)
              return 1;
          long val = ncr(n - 1, r - 1, mod);
          val = (n * val) % mod;
          val = (val * modInverse(r, mod)) % mod;
          return val;
      }
  
      static long sum[];
      static long lz[];
      
      static void build(long a[], int v, int tl, int tr) {
          if (tl == tr) {
              sum[v] = a[tl];
              
          } else {
              int tm = (tl + tr) / 2;
              build(a, v*2, tl, tm);
              build(a, v*2+1, tm+1, tr);
              sum[v] = sum[v*2] + sum[v*2+1];
          }
      }
  
      static void push(int v, int tl, int tr){
          if(tl==tr){
              lz[v] = 0;
              return;
          }
          sum[2*v] += lz[v];
          sum[2*v] %= m;
          sum[2*v+1] += lz[v];
          sum[2*v+1] %= m;
          lz[2*v] += lz[v];
          lz[2*v] %= m;
          lz[2*v+1] += lz[v];
          lz[2*v+1] %= m;
          lz[v] = 0;
      }
  
      static void update(int v, int tl, int tr, int l, int r, long val) {
          push(v,tl,tr);
          if(tl>r||tr<l)
              return;
          if(tl>=l&&tr<=r){
              sum[v] += val;
              sum[v] %= m;
              lz[v] += val;
              lz[v] %= m;
              return;
          }
          int tm = ((tl + tr) >> 1);
          update(v*2, tl, tm, l, r, val);
          update(v*2+1, tm+1, tr, l, r, val);
          sum[v] = sum[2*v]+sum[2*v+1];
          sum[v] %= m;
      }
  
      static long get(int v, int tl, int tr, int l, int r) {
          push(v,tl,tr);
          if (tl >= l && tr <= r) {
              return sum[v];
          }
          int tm = ((tl + tr) >> 1);
          if(l>tm){
              return get(2*v+1, tm+1, tr, l, r);
          }
          if(r<tm+1){
              return get(2*v, tl, tm, l, r);
          }
          return (get(2*v, tl, tm, l, r) + get(2*v+1, tm+1, tr, l, r)) % m;
      }
  
      // static int y = 0;
  
      static int parent[];
      static int rank[];
  
      static long m = 0;
  
      static int find_set(int v) {
          if (v == parent[v])
              return v;
          return find_set(parent[v]);
      }
      
      static void make_set(int v) {
          parent[v] = v;
          rank[v] = 0;
      }
      
      static void union_sets(int a, int b) {
          a = find_set(a);
          b = find_set(b);
          if (a != b) {
              if (rank[a] < rank[b]){
                  int tmp = a;
                  a = b;
                  b = tmp;
              }
              parent[b] = a;
              if (rank[a] == rank[b])
                  rank[a]++;
          }
      }
  
      static int parent1[];
      static int rank1[];
  
      static int find_set1(int v) {
          if (v == parent1[v])
              return v;
          return find_set1(parent1[v]);
      }
      
      static void make_set1(int v) {
          parent1[v] = v;
          rank1[v] = 0;
      }
      
      static void union_sets1(int a, int b) {
          a = find_set1(a);
          b = find_set1(b);
          if (a != b) {
              if (rank1[a] < rank1[b]){
                  int tmp = a;
                  a = b;
                  b = tmp;
              }
              parent1[b] = a;
              if (rank1[a] == rank1[b])
                  rank1[a]++;
          }
      }
  
      static int count = 0;
      static int count1 = 0;
  
      public static void solve(InputReader sc, PrintWriter pw){
          int i, j = 0;
          int t = 1; 
          long mod = 998244353;
          // int t = sc.nextInt();
          u: while (t-- > 0) {
              int n = sc.nextInt();
              long a[] = new long[n];
              long sum = 0;
              for(i=0;i<n;i++){
                  a[i] = sc.nextLong();
                  sum += a[i];
              }
              sort1(a);
              int m = sc.nextInt();
              for(i=0;i<m;i++){
                  long x = sc.nextLong();
                  long y = sc.nextLong();
                  int l = 0, r = n-1;
                  int ans = n;
                  while(l<=r){
                      int mid = (l+r)/2;
                      if(a[mid]>=x){
                          ans = mid;
                          r = mid - 1;
                      }
                      else{
                          l = mid + 1;
                      }
                  }
                  l = 0; r = n-1;
                  int ans1 = n;
                  while(l<=r){
                      int mid = (l+r)/2;
                      if(a[mid]<=x){
                          ans1 = mid;
                          l = mid + 1;
                      }
                      else{
                          r = mid - 1;
                      }
                  }
                  long val = Long.MAX_VALUE;
                  if(ans<n){
                      val = Math.min(val,Math.max(0,x-a[ans])+Math.max(0,y-(sum-a[ans])));
                  }
                  if(ans1<n){
                      val = Math.min(val,Math.max(0,x-a[ans1])+Math.max(0,y-(sum-a[ans1])));
                  }
                  pw.println(val);
                  // else if(ans==0){
                  //     pw.println(Math.min(x+Math.max(0,y-sum),y-(sum-a[0])));
                  // }
                  // else{
                  //     long val = x-a[ans-1]+Math.max(0,y-(sum-a[ans-1]));
                  //     if(ans<n&&a[ans]==x){
                  //         val = Math.min(val,Math.max(0,y-(sum-a[ans])));
                  //     }
                  //     val = Math.min(val,x+Math.max(0,y-sum));
                  //     pw.println(val);
                  // }
              }
          }
      }
  
      static void dfs(int curr, ArrayList<Integer> ar[], int dp[]){
          if(dp[curr]>0)
              return;
          int val = 1;
          for(int y:ar[curr]){
              dfs(y, ar, dp);
              val = Math.max(val,dp[y]);
              if(y>curr)
                  val = Math.max(val,dp[y]+1);
          }
          dp[curr] = val;
      }
  
      static boolean find(int curr, ArrayList<Integer> ar[], int vis[], int vis1[]){
          if(vis[curr]==1)
              return true;
          if(vis1[curr]==1)
              return false;
          vis[curr] = 1;
          vis1[curr] = 1;
          boolean flag = false;
          for(int y:ar[curr]){
              flag = flag | find(y,ar,vis,vis1);
          }
          return flag;
      }
  
      static void KMPSearch(char pat[], char txt[], int pres[]){
          int M = pat.length;
          int N = txt.length;
          int lps[] = new int[M];
          int j = 0; 
          computeLPSArray(pat, M, lps);
          int i = 0;
          while (i < N) {
              if (pat[j] == txt[i]) {
                  j++;
                  i++;
              }
              if (j == M) {
                  pres[i-1] = 1;
                  j = lps[j - 1];
              }
              else if (i < N && pat[j] != txt[i]) {
                  if (j != 0)
                      j = lps[j - 1];
                  else
                      i = i + 1;
              }
          }
      }
    
      static void computeLPSArray(char pat[], int M, int lps[])
      {
          int len = 0;
          int i = 1;
          lps[0] = 0; 
          while (i < M) {
              if (pat[i] == pat[len]) {
                  len++;
                  lps[i] = len;
                  i++;
              }
              else 
              {
                  if (len != 0) {
                      len = lps[len - 1];
                  }
                  else
                  {
                      lps[i] = len;
                      i++;
                  }
              }
          }
      }
  
      static long[][] matrixMult(long a[][], long b[][], long mod){
          int n = a.length;
          int m = a[0].length;
          int p = b[0].length;
          long c[][] = new long[n][p];
          for(int i=0;i<n;i++){
              for(int j=0;j<m;j++){
                  for(int k=0;k<p;k++){
                      c[i][k] += a[i][j]*b[j][k];
                      c[i][k] %= mod;
                  }
              }
          }
          return c;
      }
  
      static long[][] exp(long mat[][], long b, long mod){
          if(b==0){
              int n = mat.length;
              long res[][] = new long[n][n];
              for(int i=0;i<n;i++){
                  res[i][i] = 1;
              }
              return res;
          }
          long half[][] = exp(mat, b/2, mod);
          long res[][] = matrixMult(half, half, mod);
          if(b%2==1){
              res = matrixMult(res, mat, mod);
          }
          return res;
      }
  
      static void countPrimeFactors(int num, int a[], HashMap<Integer,Integer> pos){
          for(int i=2;i*i<num;i++){
              if(num%i==0){
                  int y = pos.get(i);
                  while(num%i==0){
                      a[y]++;
                      num/=i;
                  }
              }
          }
          if(num>1){
              int y = pos.get(num);
              a[y]++;
          }
      }
  
      static void assignAnc(ArrayList<Integer> ar[], int depth[], int sz[], int par[][] ,int curr, int parent, int d){
          depth[curr] = d;
          sz[curr] = 1;
          par[curr][0] = parent;
          for(int v:ar[curr]){
              if(parent==v)
                  continue;
              assignAnc(ar, depth, sz, par, v, curr, d+1);
              sz[curr] += sz[v];
          }
      }
  
      static int findLCA(int a, int b, int par[][], int depth[]){
          if(depth[a]>depth[b]){
              a = a^b;
              b = a^b;
              a = a^b;
          }
          int diff = depth[b] - depth[a];
          for(int i=19;i>=0;i--){
              if((diff&(1<<i))>0){
                  b = par[b][i];
              }
          }
          if(a==b)
              return a;
          for(int i=19;i>=0;i--){
              if(par[b][i]!=par[a][i]){
                  b = par[b][i];
                  a = par[a][i];
              }
          }
          return par[a][0];
      }
  
      static void formArrayForBinaryLifting(int n, int par[][]){
          for(int j=1;j<20;j++){
              for(int i=0;i<n;i++){
                  if(par[i][j-1]==-1)
                      continue;
                  par[i][j] = par[par[i][j-1]][j-1];
              }
          }
      }
  
      static long lcm(int a, int b){
          return a*b/gcd(a,b);
      }
  
      static class Pair1 {
          long a;
          long b;
          
          Pair1(long a, long b) {
              this.a = a;
              this.b = b;
          }
      }
  
      static class Pair implements Comparable<Pair> {
          int a;
          int b;
          // int c;
          
          Pair(int a, int b) {
              this.a = a;
              this.b = b;
              // this.c = c;
          }
   
          public int compareTo(Pair p) {
              // if(c!=p.c)
              return a-p.a;
              // return b-p.b;
          }
      }
  
      static class Pair2 implements Comparable<Pair2> {
          int a;
          int b;
          int c;
          
          Pair2(int a, int b, int c) {
              this.a = a;
              this.b = b;
              this.c = c;
          }
   
          public int compareTo(Pair2 p) {
              return a-p.a;
          }
      }
  
      static boolean isPrime(int n) { 
          if (n <= 1) 
              return false; 
          if (n <= 3) 
              return true; 
          if (n % 2 == 0 ||  n % 3 == 0) 
              return false; 
          for (int i = 5; i * i <= n; i = i + 6) 
              if (n % i == 0 || n % (i + 2) == 0) 
                  return false; 
          return true; 
      } 
  
      static long gcd(long a, long b) {
          if (b == 0)
              return a;
          return gcd(b, a % b);
      }
  
      static long fast_pow(long base, long n, long M) {
          if (n == 0)
              return 1;
          if (n == 1)
              return base % M;
          long halfn = fast_pow(base, n / 2, M);
          if (n % 2 == 0)
              return (halfn * halfn) % M;
          else
              return (((halfn * halfn) % M) * base) % M;
      }
  
      static long modInverse(long n, long M) {
          return fast_pow(n, M - 2, M);
      }
  
      static class InputReader {
          public BufferedReader reader;
          public StringTokenizer tokenizer;
  
          public InputReader(InputStream stream) {
              reader = new BufferedReader(new InputStreamReader(stream), 9992768);
              tokenizer = null;
          }
  
          public String next() {
              while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                  try {
                      tokenizer = new StringTokenizer(reader.readLine());
                  } catch (IOException e) {
                      throw new RuntimeException(e);
                  }
              }
              return tokenizer.nextToken();
          }
  
          public int nextInt() {
              return Integer.parseInt(next());
          }
  
          public long nextLong() {
              return Long.parseLong(next());
          }
      }
  }