Trung vị của một dãy số ~X = (x_1, x_2, ..., x_N)~ được xác định như sau:

• Xét dãy ~Y = (y_1, y_2, ..., y_N)~ là kết quả của việc sắp xếp dãy ~X~ theo thứ tự không giảm;
• Nếu ~N = 2k~, trung vị của dãy ~X~ là ~y_k~; nếu ~N = 2k + 1~, trung vị của dãy ~X~ là ~y_{k+1}~.

Chẳng hạn, trung vị của dãy ~X = (3, 1, 2, 4)~ là 2, trung vị của dãy ~(1, 3, 2, 3, 5)~ là 3.

Huy có một dãy số ~A = (a_1, a_2, ..., a_N)~. Huy muốn biến đổi dãy số về dạng dãy hằng (dãy có tất cả các phần tử bằng nhau) bằng cách sử dụng một số lần phép biến đổi:

• Chọn hai chỉ số ~l~ và ~r~ (~1 \le l < r \le N~), gọi ~x~ là trung vị của đoạn con ~(a_l, a_{l+1}, ..., a_r)~;
• Gán tất cả các phần tử ~a_l, a_{l+1}, ..., a_r~ thành ~x~.

Chẳng hạn, nếu ~A = (1, 3, 5, 2, 4)~, thực hiện biến đổi với ~l = 3~ và ~r = 4~ thì dãy trở thành ~A = (1, 3, 2, 2, 4)~.

Hãy giúp Huy xác định giá trị lớn nhất của phần tử dãy hằng có thể nhận được từ dãy ~A~.

Input

• Dòng 1: số nguyên ~N~ (~2 \le N \le 10^5~).
• Dòng 2: ~N~ số nguyên ~a_1, a_2, ..., a_N~ (~1 \le a_i \le 10^9~ với mọi ~i = 1, 2, ..., N~).

Output

Dòng 1: số nguyên là kết quả.

Sample Input 1

5
1 2 3 4 5

Sample Output 1

4

Giải thích: Có thể thực hiện 3 phép biến đổi sau:

• ~(l, r) = (4, 5)~ thì dãy mới ~A = [1, 2, 3, 4, 4]~
• ~(l, r) = (3, 5)~ thì dãy mới ~A = [1, 2, 4, 4, 4]~
• ~(l, r) = (1, 5)~ thì dãy mới ~A = [4, 4, 4, 4, 4]~

Subtasks

1. 30% điểm dành cho các test có ~2 \le N \le 10^2; 1 \le a_i \le 10^5 \forall i~;
2. 30% điểm khác dành cho các test có ~10^2 < N \le 10^3; 1 \le a_i \le 10^6 \forall i~;
3. 40% điểm còn lại không có ràng buộc bổ sung.