import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
def solve():
n = int(input())
a = list(map(int, input().split()))
m = int(input())
a.sort()
s = sum(a)
for i in range(m):
attack, defence = map(int, input().split())
begin, end = 0, n
while True:
mid = (begin + end) // 2
mm = a[mid]
if end - begin < 2:
break
if mm <= attack:
begin = mid
else:
end = mid
ans = max(defence - (s - a[end]), 0) if end != n else int(10**20)
ans = min(ans, max(attack - a[begin], 0) + max(defence - (s - a[begin]), 0))
sys.stdout.write(f'{ans}\n')
if __name__ == '__main__':
solve()
#include<bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define int long long
#define endl "\n"
#define space " "
#define printArray(a, n) for(int i=0;i<n;i++) cout<<a[i]<<space; cout<<endl;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<char,int> pci;
typedef map<int,int> mii;
typedef vector<int> vi;
const int MOD = 1e9 + 7;
//---------------------------------------------------------------------------------------------------//
static bool cmp(pair<int,int> a, pair<int,int> b)
{
if (a==b)
{
return a.second<b.second;
}
return a.first<b.first;
}int lowerBound(int arr[], int n, int x)
{
int low=0, high=n-1;
int mid=(low+high)/2;
while(high-low>1)
{
mid=(high+low)/2;
if (arr[mid]<x)
{
low=mid+1;
}
else //
{
high=mid;
}
}
if (arr[low]>=x)
{
return low;
}
else if (arr[high]>=x)
{
return high;
}
else
{
return -1;
}
}
void solve()
{
int n;
cin>>n;
int arr[n];
int sumArr=0;
for(int i=0;i<n;i++)
{
cin>>arr[i];
sumArr+=arr[i];
}
int m;
cin>>m;
pii dragon[m];
for(int i=0;i<m;i++)
{
cin>>dragon[i].first;
cin>>dragon[i].second;
}
sort(arr, arr+n);
int sum=sumArr;
for(int i=0;i<m;i++)
{
sumArr=sum;
int k=lowerBound(arr, n, dragon[i].first);
if (k==-1)
{
//not found
int value=arr[n-1];
sumArr=sumArr-value;
int answer=dragon[i].first-value;
// cout<<sumArr<<"HKJ "<<endl;
if (sumArr<dragon[i].second)
{
answer+=dragon[i].second-sumArr;
}
cout<<answer<<""<<endl;
}
else
{
int value = arr[k];
int answer=0;
// if (value<dragon[i].first)
// {
// answer+=dragon[i].first-value;
// }
sumArr=sumArr-value;
if (sumArr<dragon[i].second)
{
answer+=dragon[i].second-sumArr;
}
sumArr=sum;
int answer2=LONG_LONG_MAX;
if(k>0)
{
// value = *(--k);
value=arr[k-1];
answer2=0;
if (value<dragon[i].first)
{
answer2+=dragon[i].first-value;
}
sumArr=sumArr-value;
if (sumArr<dragon[i].second)
{
answer2+=dragon[i].second-sumArr;
}
}
cout<<min(answer, answer2)<<endl;
}
}
}
int32_t main()
{
fastIO;
int t=1;
while(t--)
{
solve();
}
return 0;
}1217. Minimum Cost to Move Chips to The Same Position | 347. Top K Frequent Elements |
1503. Last Moment Before All Ants Fall Out of a Plank | 430. Flatten a Multilevel Doubly Linked List |
1290. Convert Binary Number in a Linked List to Integer | 1525. Number of Good Ways to Split a String |
72. Edit Distance | 563. Binary Tree Tilt |
1306. Jump Game III | 236. Lowest Common Ancestor of a Binary Tree |
790. Domino and Tromino Tiling | 878. Nth Magical Number |
2099. Find Subsequence of Length K With the Largest Sum | 1608A - Find Array |
416. Partition Equal Subset Sum | 1446. Consecutive Characters |
1618A - Polycarp and Sums of Subsequences | 1618B - Missing Bigram |
938. Range Sum of BST | 147. Insertion Sort List |
310. Minimum Height Trees | 2110. Number of Smooth Descent Periods of a Stock |
2109. Adding Spaces to a String | 2108. Find First Palindromic String in the Array |
394. Decode String | 902. Numbers At Most N Given Digit Set |
221. Maximal Square | 1200. Minimum Absolute Difference |
1619B - Squares and Cubes | 1619A - Square String |