Given an array of n integers, find the value of its maximum element.

Input

The input consists of several test cases.

Each test case is described in two lines. The first line contains n, the size of the array (1 <= n <= 10⁶). The second line contains n integers separated by one or more spaces. Each integer in the array will be between -10⁹ and 10⁹, inclusive.

The last line of the input contains a single 0 and should not be processed.

Output

For each test case, write the maximum element in the array on a single line.

Example

Input:
4
1 2 3 4
2
-1 0
3
-1000000000 0 1000000000
0

Output:
4
0
1000000000