There are a lot of life stories in a fast-food restaurant “Mike Don’t Know”. Of course Mike doesn’t know it, so “Mike Don’t Know” give Mike a chance to let he know.
Life, is just like an organism, it changes every time, everywhere. Sometimes you’ll suddenly get a red arm, car crashes, or just beaten by nothing. Let us use n numbers in a row to denote this organism. Initially they are all zeroes. And gradually, some of them change!
It is said that the number of “Upside-Down” pairs would influence the balance of life. So your job is to help Mike calculate the number of “Upside-Down” pairs whenever the number changes. An “Upside-Down” pair forms when two numbers in the row satisfies the former strictly larger than the latter.
“Are you Kidding?”
“No, I’m Serious. Just do it. OK?”
There are multiple test cases in the input file. For each test case, first line contains an integer n (1 <= n <= 50,000) indicating the number of numbers. The second line contains an integer m (0 <= m <= 50,000) indicating the number of change records. In the each of next m lines, there are two numbers Xi, Di indicating the Xi-th number is changed by Di. (1 <= Xi <= n, |Di| <= 10,000)
n = 0 terminates the input, don’t proceed it.
For each change, output the number of “Upside-Down” pairs after that changes.
9 3 1 +5 3 -5 2 +7 10 1 10 +5 0
8 9 14 0
Migrated from old NTUJ.
Tmt
| No. | Testdata Range | Score |
|---|