Two Largest Values

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Find the values of the two largest elements of a sequence, including duplicate values from distinct positions. Output them in nonincreasing order; 7,2,7 yields 7 7. Process the stream using two variables.

Input

The first line contains n (2<=n<=100000). The next line contains n integers in [-10^9,10^9].

Output

Print the largest and second-largest element values, separated by one space.

Subtasks

• Subtask 1 (20%): $n\le5,|a_i|\le10$.
• Subtask 2 (30%): $n\le500,|a_i|\le10^4$.
• Subtask 3 (50%): $n\le100000,|a_i|\le10^9$.

Examples

Example 1

Input:

5
7 2 7 -1 3

Output:

7 7

Explanation:

The two sevens occupy different positions and are both selected.

Example 2

Input:

4
-8 -2 -10 -3

Output:

-2 -3

Explanation:

For negative inputs, -2 is larger than -3; zero is not a valid initial maximum.