Everyone Else’s Pick

A toy lab is testing a very simple classifier: to label any toy, it just copies whatever label most other toys got. It doesn’t look at the toy itself - only at “everyone else’s choice”.

Your job is to evaluate this classifier. For each toy in a list, pretend we’re labeling it by taking the majority label among the other N−1 toys (i.e., ignore the current toy’s own label). If multiple labels are tied for most frequent, pick the alphabetically smallest one. Count how many toys the classifier would label correctly (i.e., its predicted label matches the toy’s true label), and print that number.

The first line of the input contains a single integer n - the number of toys (n ≥ 2).

The second line contains n space-separated labels (each label is a word without spaces), listed in order.

For each position i (1-based), predict the label for the toy i by taking the majority label among the other n-1 labels. In case of a tie, choose the alphabetically smallest label. Then compare this prediction to the true label at i. The program should print a single integer — the total number of correct predictions.

Input

Output

5
car doll car car robot

3

4
train doll robot doll

2

4
ball ball ball ball

4

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue