After the end of the war, Collea was left in a state of political turmoil. Having been forced to install a democratic government, and with the rise of extremist attitudes throughout the country, the current Collean government is anxious about the coming national election. There are ~N~ political parties in Collea, which are conveniently numbered from ~1~ to ~N~, and current polls show that if the election was to be held today, the ~i~th political party would earn ~v_i~ votes. In order for a new government to form, some of the political parties must form a majority coalition where the sum of the votes of the parties in the coalition must be strictly greater than half of the total votes. In the ~D~ following days, some political parties had their expected number of votes changed. Specifically, on the ~i~th day, the ~a_i~th party's expected number of votes changed to ~b_i~. Help Collea find the minimum number of parties required such that they form a majority coalition for each day.
~1 \le N \le 300\,000~
~0 \le D \le 300\,000~
~0 \le b_i,v_i \le 10^9~
~1 \le a_i \le N~
It is guaranteed that the total number of votes will always be positive.
Subtask 1 [10%]
~1 \le N,D \le 2000~
Subtask 2 [90%]
No additional constraints.
The first line contains two integers, ~N~ and ~D~.
The second line contains ~N~ integers, ~v_1,v_2,\dots,v_N~.
~D~ lines follow, the ~i~th of which contains the integers ~a_i~ and ~b_i~.
On the first line, output one integer, the minimum possible number of parties in a majority coalition before the ~D~ days.
Output ~D~ more lines, the ~i~th of which containing one integer, the minimum possible number of parties in a majority coalition after the ~i~th day.
5 3 3 1 5 2 2 2 3 5 3 4 5
2 2 3 2