#49Easy

Maximum and minimum

Time: 1 s · Memory: 256 MB

Loops

Statement

You are given $n$ integers. Find the largest and the smallest of them.

Input format

The first line contains $n$ ( $1 \le n \le 10^5$ ). The second line contains $n$ integers ( $|a_i| \le 10^9$ ).

Output format

A single line with two numbers: first the largest, then the smallest.

Examples

Input

6
4 2 9 12 1 3

Output

12 1

Input

3
-5 -2 -9

Output

-2 -9

Note

No array is needed: read the numbers one by one and update the current maximum and minimum.

Do not start from $0$ : if all numbers are negative (the second example), the maximum would stay $0$ . Use the first number read as the starting value for both.

Maximum and minimum

Time: 1 s · Memory: 256 MB

Loops

Statement

You are given $n$ integers. Find the largest and the smallest of them.

Input format

The first line contains $n$ ( $1 \le n \le 10^5$ ). The second line contains $n$ integers ( $|a_i| \le 10^9$ ).

Output format

A single line with two numbers: first the largest, then the smallest.

Examples

Input

6
4 2 9 12 1 3

Output

12 1

Input

3
-5 -2 -9

Output

-2 -9

Note

No array is needed: read the numbers one by one and update the current maximum and minimum.

Do not start from $0$ : if all numbers are negative (the second example), the maximum would stay $0$ . Use the first number read as the starting value for both.