#113Easy

Most frequent number

Time: 1 s · Memory: 256 MB

Maps and sets

Statement

You are given an array of $n$ numbers. Find the number that occurs most often and how many times it occurs. If there are several such numbers, print the smallest of them.

Input format

The first line contains $n$ ( $1 \le n \le 10^5$ ). The second line contains $n$ integers ( $|a_i| \le 10^9$ ).

Output format

A single line with two numbers: the most frequent number and its count.

Examples

Input

6
3 1 2 2 2 1

Output

2 3

Input

4
5 1 5 1

Output

1 2

Note

First count all numbers with a dictionary, then walk over it to find the largest counter. On a tie choose the smaller number: in the second example both $1$ and $5$ occur twice — the answer is 1 2.