Gopal's Grand Gambit: Tracking Montri's Treachery

We're familiar with Krishnanagar, ruled by King Krishnachandra Roy and his council, including the notorious liar Montri, along with other colorful characters like Boiddho, Kobi, Pondit, and Biggani. Gopal Var, known for his cleverness, is a key figure in the court and has never been outsmarted. One famous story recounts how he rescued a person from a monster even after death.

This year, heavy rainfall and thunderstorms during the rainy season have devastated the fields, leaving many struggling to feed themselves and unable to pay taxes. Due to his popularity, people turned to Gopal for help in persuading the king to provide food and relief. Gopal successfully persuaded the king to offer financial aid to the people. In response, the king instructed Montri to create funds for each village, with the amount varying according to the village's condition. Upon hearing this directive, Montri's eyes gleamed with greed. Given Gopal's keen observation skills, nothing escapes his notice.

Upon returning home the same day, Gopal noticed Montri conversing with the thieves Bota and Ghota. Gopal attempted to listen in on their conversation but to avoid raising suspicion, he couldn't hear what they were discussing. Determined to uncover Montri's intentions, Gopal assembled his small team, "Bador Shena," consisting of Gulte, Tapaa, Napla, and Puti. Their mission is to shadow Montri throughout the day and discern his plans. After three days of surveillance, Napla finally disclosed that Montri intended to steal from the village fund.

The king is going to distribute money to villages in stages. Each village starts with a budget, let’s say it’s 100 taka. If the king gives, say, 70 taka at first, then 30 taka will be left for the next payment for that specific village. Let's say there are three villages with budgets of 200 taka, 180 taka, and 300 taka. If the king decides to give the third village 150 taka, the new budgets will be [200, 180, 150]. After each payment, we want to know the highest amount given to any village and for this case, it’s 200. But sometimes, the king forgets and asks for more money than a village has left. In that case, we can't give them more money than the remaining budget allows. So, we'll just give them whatever is left or 0. Then we reset the remaining amount to 0. Now your task is to keep track of the largest amount of money allocated to any village after every order from the king, considering the rules of distribution and adjustments mentioned earlier. This information is crucial as Montri, the king's advisor, plans to steal the largest allocated amount.

Input

The first line contains a single integer N (1 <= N <= 100), which represents the size of the array.

The second line contains N non-negative integers not greater than 100000, representing the initial amounts allocated to each village.

The third line contains a single integer Q (1 <= Q <= 10), indicating the number of queries.

The following Q lines contain a query each, with two integers P and T. Here, P represents the position or index number of the village in the array, and T (0<=T<=100000) represents the amount to be deducted from the current amount in that index.

Output

For every query, print an integer which is the largest amount from the updated array after applying the deduction.

Sample

Input	Output
3 200 180 300 2 3 150 1 50	200 180