Chim di cư (Migratory Birds)

Nguồn: HackerRank

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $n$ lần quan sát chim. Mỗi lần quan sát được biểu diễn bởi một ID loài $a_i\in\{1,2,3,4,5\}$.

Với mỗi ID $v$, đặt

Hãy tìm ID $v$ có $f_v$ lớn nhất. Nếu có nhiều ID cùng đạt tần suất lớn nhất, chọn ID nhỏ nhất.

Input

• Dòng 1 chứa số nguyên $n$.
• Dòng 2 chứa $n$ số nguyên $a_1,a_2,\ldots,a_n$.

Output

In ID của loài cần tìm.

Subtask

Subtask 1 (20 điểm): $5\le n\le 20$ và $a_i\in\{1,2,3,4,5\}$.

Subtask 2 (30 điểm): $5\le n\le 1000$ và $a_i\in\{1,2,3,4,5\}$.

Subtask 3 (50 điểm): $5\le n\le 200000$ và $a_i\in\{1,2,3,4,5\}$.

Ví dụ

Input

6
1 4 4 4 5 3

Output

4

Giải thích

ID 4 xuất hiện 3 lần, nhiều hơn mọi ID khác.