Second Most Frequent Element

Given a list of integers, find and print the second most frequent element. If there is a tie for the second most frequent element, output any one of them. If the list has fewer than two distinct values, print None.

For example, if the input list is [4, 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5], the most frequent element is 4 and the second most frequent element can be either 3 or 5.

Mathematically, let (f(x)) denote the frequency of element (x). The task is to find an element (y) such that (f(y)) is the second highest frequency among all elements.

inputFormat

Input is read from standard input (stdin).

The first line contains a single integer (n) (where (0 \le n \le 10^5)) indicating the number of elements in the list. The second line contains (n) space-separated integers.

outputFormat

Output the second most frequent element to standard output (stdout). If no valid second most frequent element exists, output 'None'.## sample

15
4 1 2 2 3 3 3 4 4 4 4 5 5 5 5

3