{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eYoda, the Grand Master of the Jedi Order, hit on the idea to hold a tournament among younglings. He has not chosen the date yet, but he has already decided on the format of the tournament.\u003c/p\u003e\u003cp\u003eThere are \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e younglings studying in the Jedi Temple. Yoda can feel the Force inside younglings, moreover, he can represent the amount of the Force inside \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th youngling as the number \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ef\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eTherefore, the format of the tournament is the following. At first, Yoda makes the children stand in a row in order of non-increasing \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ef\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e. Then, the first youngling in the row competes against all the others united together. The combat is based on lightsaber battle and is very spectacular. However, Yoda knows that the result doesn\u0027t depend on anything but the Force inside competitors. The youngling wins if his amount of Force is not less than the total amount of the Force inside all his opponents. In that case, he is considered one of the winners. Otherwise, he loses. Anyway, after that he is removed from the row, and the tournament continues. Again, the strongest (first in the row) youngling competes against all the others standing in the row in the same format, if he wins, he is also considered one of the winners. After that he is removed and the tournament continues in the same format until there is only one child in the row. He becomes one of the winners automatically and the tournament finishes.\u003c/p\u003e\u003cp\u003eYoda wants to know the total number of winners. However, as the tournament is postponed again and again, the amount of the Force inside the younglings changes from time to time. Help Yoda to compute the total number of winners after each change.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of input contains a single integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e, the number of younglings in the Jedi Temple (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 100 000\u003c/span\u003e).\u003c/p\u003e\u003cp\u003eThe second line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ef\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ef\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003ef\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e the amount of the Force inside the younglings (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ef\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e12\u003c/sup\u003e\u003c/span\u003e).\u003c/p\u003e\u003cp\u003eThe third line of the input contains a single integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/span\u003e, the number of changes in the Force amounts of students (\u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003eM\u003c/i\u003e ≤ 50 000\u003c/span\u003e).\u003c/p\u003e\u003cp\u003eThe next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/span\u003e lines contain information about the changes. The \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th of these lines describes the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th change and contains two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ef\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/sub\u003e\u003csup class\u003d\"upper-index\"\u003e\u003c/sup\u003e * \u003c/span\u003e, which mean that the amount of the Force inside the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e-th youngling becomes equal to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ef\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/sub\u003e\u003csup class\u003d\"upper-index\"\u003e\u003c/sup\u003e * \u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ek\u003c/i\u003e ≤ \u003ci\u003eN\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ef\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/sub\u003e\u003csup class\u003d\"upper-index\"\u003e\u003c/sup\u003e * ≤ 10\u003csup class\u003d\"upper-index\"\u003e12\u003c/sup\u003e\u003c/span\u003e).\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eM\u003c/i\u003e + 1\u003c/span\u003e lines, each of them containing a single integer.\u003c/p\u003e\u003cp\u003eOn the first line, print the number of winners if the tournament was held before all the changes. On line \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ei\u003c/i\u003e + 1)\u003c/span\u003e for all \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e \u0026gt; 0\u003c/span\u003e, print the number of winners if the tournament was held after the first \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e changes.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n2 1 3\n3\n1 3\n2 7\n3 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n2\n3\n2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e7\n2 14 14 15 5 2 5\n5\n5 2\n4 12\n5 4\n3 10\n7 9\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n3\n3\n3\n3\n4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}