Lunch Warnings

Interview

Time limit1sMemory limit128 MB

Summary

Given a sequence of children taking food, count how many times a child's total pieces so far exceed all other children's combined total before their next pick.

Level: Easy3 of 10
Topics: Hash map, Simulation
Solved: No attempts yet

Problem

Several children are having lunch at a table. On each turn, one child takes one piece of food from the table.

Some children are impatient and may keep taking food before the others get a fair chance. Just before a child takes a new piece, if that child has already taken more pieces than all other children combined, the mother warns that child.

Given the order in which pieces are taken, count how many warnings the mother gives.

Input

The first line contains an integer N, the number of pieces taken. N is between 1 and 100, inclusive.

Each of the next N lines contains the name of the child who takes one piece. Each name consists only of lowercase English letters and has length at most 20.

Output

Output the number of warnings on a single line.

Examples2

Example 1
Input
```
4
mirko
stanko
stanko
stanko
```
Expected output
```
1
```
Example 2
Input
```
17
a
b
b
a
a
a
c
a
b
b
c
b
b
b
b
b
b
```
Expected output
```
4
```