Bạn được cho một dãy \(A = [a_1, a_2, \dots, a_n]\). Xét \(B\) là dãy gồm các trung vị của các đoạn con liên tiếp của \(A\), hãy tính trung vị của \(B\).

Nhắc lại, trung vị của một dãy đã được sắp xếp \(x_1, x_2, \dots, x_k\) là \(x_{\lfloor \frac{k+1}{2} \rfloor}\).

Input

• Dòng đầu tiên chứa một số nguyên dương \(1 \le n \le 10^5\) – số phần tử của dãy \(A\).
• Dòng tiếp theo gồm \(n\) số nguyên dương \(1 \le a_i \le 10^9\).

Output

• Một dòng duy nhất gồm kết quả bài toán.

Example

4
1 2 3 4

2

4
1 1 2 2

1

4
4 3 2 1

2

Subtask

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 1000\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 5000\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 20000\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \le 50000\).
• Subtask \(5\) (\(10\%\) số điểm): \(n \le 10^5\) và các phần tử của dãy \(A\) chỉ có \(2\) giá trị khác nhau.
• Subtask \(6\) (\(10\%\) số điểm): Không có ràng buộc gì thêm.