说明

给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。

输入

第一行一个整数 $n$； 第二行 $n$ 个整数 $a_i$。

输出

一个整数，即数组中第三大的数。

样例

3
3 2 1

1

2
1 2

2

4
2 2 3 1

1

提示

• $1 <= n <= 10^4$
• $-2^{31} <= a_i <= 2^{31}-1$

​进阶：​你能设计一个时间复杂度 $O(n)$ 的解决方案吗？