Phần tử áp đảo

Points: 3 (partial)

Time limit: 1.0s

Memory limit: 977M

Author:

Problem type

Allowed languages

Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, ~~GAS32~~, GO, Haskell, Itercal, Java, kotlin, ~~LEAN~~, LISP, LUA, MONOVB, ~~Nasm~~, ~~OCAML~~, Pascal, Perl, php, PIKE, ~~prolog~~, Pypy, Python, ~~Ruby 2~~, RUST, Scala, SCM, SED, ~~SWIFT~~, TCL, ~~TUR~~, ~~V8JS~~, VB, ZIG

Cho dãy số nguyên $a_{1}, a_{2}, . . ., a_{N}$ có $N$ phần tử, bạn hãy tìm phần tử áp đảo là phần tử có tần suất xuất hiện nhiều hơn $\frac{N}{2}$

Input

Dòng đầu là số phần tử N $(1 < N \leq 10^{6})$

Dòng tiếp theo là $N$ số nguyên mỗi số có giá trị tuyệt đối không vượt quá $10^{9}$

Output

Một số nguyên duy nhất là giá trị của phần tử áp đáo, nếu dãy không có phần tử áp đảo in ra thông báo "khong co phan tu ap dao"

Example 1

Input

Copy

8
1 9 0 0 1 5 0 0

Output

Copy

khong co phan tu ap dao

Example 2

Input

Copy

9
-3 4 -5 4 6 4 4 1 4