eolymp
Competitions

Ternary search

Maximum in Unimodal Sequence

Sequence ai is called unimodal if there exists such index p that a1 < a2 < ... < ap and ap > ap+1 > ... > an. Value ap is maximum in this sequence. You must find this value.

Input

First line contains the size of array n (n106). Next line contains n positive integers that represent a unimodal sequence. Numbers in array do not exceed 109.

Output

Print the maximum element is the unimodal sequence.

Time limit 1 second
Memory limit 128 MiB
Input example #1
10
2 4 7 12 18 19 16 11 8 3
Output example #1
19
Input example #2
6
3 5 7 11 15 17
Output example #2
17
Author Michael Medvediev