Problem D
Tax the Rich
Your city is deciding whether to raise taxes or lower them for the richest residents. Rich people are defined as those earning an income equal to or above the mean income, while poor people are defined as those earning an income below the mean income (mean = average). The city has decided to have an in-person public vote to determine which direction taxes on rich people will go (either up or down).
The city will raise taxes on rich people if more than half of all the people attending the meeting are poor (because there are a lot of low income earners to support). But the city will lower taxes on the rich if at least half of the people at the meeting are rich (since there are lots of rich people, they can each pay a little bit less to support the poor individuals).
As each person arrives at the meeting, they announce their income. If at that instant in time the majority of the people (more than $1/2$ of the people) in the room are poor, then a spontaneous round of applause will occur (the rich people, who are in the minority, are going to pay more — YAY!). However, if at the instant when the person arriving announces their income at least half of the people in the room are rich, then there is silence in the room.
Your task is to determine how many times the room erupts in applause.
Input
The first line of input contains an integer, $N$ $(1 \leq N \leq 500\, 000)$, the number of people who will attend the meeting. This is followed by a single line containing $N$ space-separated integer values, $a_1, a_2, \ldots , a_ N$, representing the incomes of the meeting attendees in the order they arrive $(1 \leq a_ i \leq 10\, 000)$.
Output
Output a single integer, the total number of times that the room erupts in applause.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 1 5 12 |
1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 1 11 6 |
0 |
