beecrowd | 1804 | [P2][Univ]

Mathematicians Needed in Mars

By Leandro Zatesko, UFFS BR Brazil

Timelimit: 1

The VIII Latin-American Algorithms, Graphs and Optimisation Symposium (LAGOS 2015), a conference which gathered mathematicians and computer scientists from worldwide to discuss some computational challenges, was held in Beberibe, CE, and happened in the last week. Wanting the participants to relax a bit, the symposium organisers hired buggies to take the researchers to some touristic places in the region. The buggies left the hotel in a queue, one after the other.

Whoever knows the buggy rides of Ceará knows that the tourist can ask the buggy driver a ride with emotion or without emotion. However, LAGOS excursion faced an extra emotion. Since nowadays in Mars there is a lack of researchers in Graphs, Algorithms and Optimisation, martian aliens started to abduct some buggies, with all people aboard (including the poor driver, who had nothing to do with it). It was very sad for our planet to loose such brilliant minds to Mars, but the tragedy could have been less serious if each buggy driver had been keeping updated the information of how many people in total were in the buggies behind his — this way he would be able to notice the aproximation of the alien probe and to speed the buggy up.

Input

An integer N (1 ≤ N ≤ 105) makes the first line of the input, which represents the number of buggies that have left the hotel. The second line of the input consists of N integers pi (1 ≤ pi ≤ 5, 1 ≤ iN), each one representing the number of people in the buggy i (including the buggyman). Each one of the following lines can consist:

Consider that the identifier i of a buggy does not change. Hence, the third buggy to leave the hotel shall always be identified by the integer 3, even though the buggies 1 and 2 happen to be abducted.

Output

For each line "? i", print a line containing the number of the people of the excursion still remaining behind the buggy i in that moment. But do not be a bugman (don't put bugs in your code)!

Input Sample Output Sample

10
1 2 3 4 5 4 3 2 1 2
a 9
? 10
a 2
a 5
? 6
a 6
? 10

24
8
13