Most Beautiful Segment

You are given an array of N integers. A segment of the array is a contiguous subarray and its beauty is defined as the sum of the minimum and maximum elements in that segment. Your task is to compute the value of the segment with the highest beauty.

However, note that if the array is empty (N = 0), the beauty is defined to be 0.

Important: In this problem, the solution is expected to simply return the sum of the global minimum and maximum values of the entire array. For example, given the array [1, -3, 5, 1, 9], the answer is -3 + 9 = 6 even though a proper subsegment may yield a higher sum.

You should read input from standard input (stdin) and output the result to standard output (stdout).

Input Format: The first line contains an integer N which represents the number of elements in the array. The second line contains N space-separated integers.

Output Format: Print a single integer — the beauty value as defined above.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

1. The first line contains a single integer N (the number of elements in the array).
2. The second line contains N space-separated integers representing the elements of the array. If N equals 0, the second line may be empty.

outputFormat

The output should be written to standard output (stdout) and consist of a single integer — the sum of the minimum and maximum elements of the array, or 0 if the array is empty.

## sample

5
1 3 5 1 9

10