Most Frequent Word

MediumStringsHashingFrequency-CountCounting5 hidden tests

You are given n lowercase words. Report the word that occurs the most times. If several words tie for the highest count, report the lexicographically smallest of them.

Input format

Line 1: an integer n, the number of words. Line 2: n space-separated lowercase words.

Output format

One line: the most frequent word (lexicographically smallest on ties).

Constraints

1 <= n <= 100000
1 <= length of each word <= 50

Examples

Example 1

Input

5
apple banana apple cherry banana

Expected

apple

Explanation

'apple' and 'banana' each appear twice; 'apple' is lexicographically smaller, so it wins.

Example 2

Input

3
pear pear kiwi

Expected

pear

Explanation

'pear' appears twice and 'kiwi' once, so 'pear' is the most frequent.

Ready to solve this?

Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.

Sign in to solve →