Description

Children are having lunch at the table. There are $n$ portions of food, and the children take these $n$ portions one by one in order from $1$ to $n$.

When a child takes a portion, if the number of portions he has already taken before this moment (excluding the current portion) is greater than the total number of portions taken by all other children, then his mom will remind him to mind his manners. Note that even if he is reminded, he will still take this portion. In other words, the reminder does not affect the child's behavior.

Given which child takes each of the $n$ portions, determine the total number of reminders given by the moms.

Input Format

The first line contains an integer $n$, the number of portions.

Lines $2$ to $n + 1$: each line contains a string. The string on the $(i + 1)$-th line, $s_i$, is the name of the child who takes the $i$-th portion.

Output Format

Output a single integer: the answer.

4
mirko
stanko
stanko
stanko

1

17
a
b
b
a
a
a
c
a
b
b
c
b
b
b
b
b
b

4

Hint

Sample 1 Explanation

When the $3$rd portion is taken, stanko has previously taken $1$ portion (excluding the current one), and the others have also taken $1$ portion in total, so stanko’s mom does not remind him.

When the $4$th portion is taken, stanko has already taken $2$ portions, while the others have taken $1$ portion in total, so his mom reminds him.

Constraints

For all test cases, it is guaranteed that:

• $1 \leq n \leq 100$.
• $1 \leq |s_i| \leq 20$, and $s_i$ contains only lowercase English letters. $|s_i|$ denotes the length of the string.

Note

Problem translated from COCI2006-2007 CONTEST #6 T1 PRASE.

Translated by ChatGPT 5