Sereja and Ballons

Sereja has n boxes with balloons. Boxes are numbered with integers from 1 to n. The first box contains a[1] balloons, the second- a[2] balloons and so on. Also Sereja wrote down m pairs of the number (l[1], r[1]), (l[2], r[2]), ..., (l[m], r[m]) on a piece of paper. Now Sereja decided to play and began to burst the balloons in the boxes. At every step Sereja bursts one balloon from some box and wa