Vào thời cổ đại ở Ai Cập có một vị vua Pharaoh muốn xây một kim tự tháp cho riêng mình. Nhưng ông không muốn nó xây dựng theo cách thông thường.

Ông muốn từ một dãy núi có chiều dài ~n~ với vị trí thứ ~i~ có chiều cao ~a_i~ và đào các phần đất trên cùng không cần thiết để được một kim tử tháp.

Ví dụ với các kim tự tháp có chiều cao lần lượt là 1, 2, 3, 4, 5 :

Hỏi kim tử tháp cao nhất mà Pharaoh có thể tạo ra là bao nhiêu.

Input

• Dòng đầu tiên có số nguyên ~N~ ~(1 \leq N \leq 10^5)~ đại diện cho chiều dài dãy núi.
• Dòng tiếp theo gồm ~N~ số nguyên ~a_i~ ~(1 \leq a_i \leq 5 \times 10^4)~ đại diện cho chiều cao tại vị trí thứ ~i~ trên dãy núi.

Output

• Một số nguyên duy nhất là chiều cao lớn nhất có thể của kim tự tháp

Sample Input

16
5 6 5 8 9 10 5 8 9 5 7 9 9 9 6 3

Sample Output

6