asked in interviews by 1 company

Time Limit: 2 sec
Memory Limit: 128000 kB

Problem Statement

Given an integer array of size n. Print the three most occurring element. print them in order of their number of occurrence. If the number of occurrence is same then print the smaller number before.

Input

First line contains n.
Next line contains n space separated integers.

Constraints
3 <= n < = 10⁵
1 <= arr[i] <= 10⁵

Output

Output three integers. if there are not enough integers then print -1 for that place.

EXample
Input:
6
1 2 1 2 2 1

Output:
1 2 -1

Explanation:
number of occurrence of 1 = 3
number of occurrence of 2 = 3
so 1 is printed before 2.
there are only 2 elements so we print -1 as third number.

Note: Do comment out solution with explanation. Your welcome ☻