Trong một phòng thí nghiệm dữ liệu, các nhà nghiên cứu đang phân tích một dãy số ~a_1, a_2, \dots, a_N~. Với mỗi đoạn con liên tiếp của dãy (tức là một dãy ~a_l, a_{l+1}, \dots, a_r~), ta có thể sắp xếp các phần tử của đoạn đó theo thứ tự không giảm. Phần tử nằm chính giữa của dãy sau khi sắp xếp được gọi là median của đoạn.

Cụ thể, nếu đoạn có độ dài ~m = r-l+1~, thì median được định nghĩa là phần tử ở vị trí ~\lfloor m/2 \rfloor+1~ trong dãy sau khi sắp xếp.

Ví dụ: median của ~[1, 3, 2]~ là ~2~; median của ~[1, 4, 2, 3]~ là ~3~.

Xét tất cả các đoạn con liên tiếp của dãy ~a~. Với mỗi đoạn, ta tính median của đoạn đó. Hãy tìm median của tất cả các giá trị median này.

Nói cách khác:

• Với mỗi đoạn con của dãy, tính median của đoạn đó.

• Tạo thành một dãy mới gồm tất cả các giá trị median vừa tính.

• In ra median của dãy mới.

Input

• Dòng đầu tiên chứa số nguyên ~N~.

• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \dots, a_N~.

Output

In ra một số nguyên duy nhất - median của tất cả các median của các đoạn con.

Scoring

Trong tất cả các test:

• ~1 \le N \le 2 \cdot 10^5~;

• ~1 \le a_i \le 10^9~.

Sample Input 1

3
1 2 3

Sample Output 1

2

Sample Input 2

4
4 1 2 4

Sample Output 2

4

Notes

Với ví dụ thứ nhất, các median của mọi đoạn con lần lượt là ~[1, 2, 3, 2, 3, 2]~. Sau khi sắp xếp, ta được ~[1, 2, 2, 2, 3, 3]~, nên median của dãy này là ~2~.

Đây là ví dụ thứ hai của đề bài. Kết quả cuối cùng bằng ~4~.