B'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). The first line contains a single integer n ( 2 <= n <= 2 cdot 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 cdot 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. 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. 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] . '...