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ị 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 ~X = (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 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 trên với ~l = 3~ và ~r = 4~ thì dãy trở thành ~A = (1, 3, 2, 2, 4)~.

Yêu cầu

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~.

Dữ liệu đầu vào

Gồm hai dòng:

• 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\ \forall\ i = 1..N)~.

Dữ liệu đầu ra

Gồm một số nguyên kết quả.

Ràng buộc dữ liệu

• 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~;
• 30% điểm khác dành cho các test có ~10^2 \le N \le 10^3;\ 10^5 \le a_{i} \le 10^6\ \forall\ i~;
• 40% điểm còn lại không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

INPUT

5
1 2 3 4 5

OUTPUT

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]~