Cuộc đối đầu kéo dài hàng thế kỷ giữa Busy Beaver và Busy Revaeb vẫn tiếp diễn cho đến tận ngày nay. Lần này, họ quyết định thách đấu lẫn nhau trong một trò chơi hai người.

Cho một dãy gồm $N$ số nguyên dương $a_1, \dots, a_N$. Busy Beaver và Busy Revaeb chơi một trò chơi theo lượt như sau:

• Busy Beaver chọn hai số liền kề trong dãy, xóa chúng đi và viết vào đó số lớn hơn trong hai số vừa bị xóa.
• Busy Revaeb thực hiện tương tự, nhưng viết vào đó số nhỏ hơn trong hai số vừa bị xóa.

Busy Beaver đi trước. Trò chơi kết thúc khi chỉ còn lại một số $X$ duy nhất trong dãy. Busy Beaver muốn tối đa hóa $X$; Busy Revaeb muốn tối thiểu hóa nó. Hãy tìm giá trị của $X$ nếu cả hai người chơi đều chơi tối ưu.

Dữ liệu vào

Dòng đầu tiên chứa $N$ ($1 \leq N \leq 2 \cdot 10^5$), số lượng phần tử trong mảng.

Dòng thứ hai chứa $N$ số nguyên cách nhau bởi dấu cách $a_1, \dots, a_N$ ($1 \le a_i \le 10^9$).

Dữ liệu ra

In ra một số nguyên duy nhất -- giá trị của phần tử còn lại duy nhất trong mảng nếu cả hai người chơi đều chơi tối ưu.

Ví dụ

Giải thích mẫu 1

Giá trị cuối cùng không thể là $4$, bởi vì nếu Busy Beaver cố gắng giữ lại $4$ bằng cách không chọn nó trong lượt đầu tiên, Busy Revaeb có thể lấy số $4$ ở lượt tiếp theo, khiến giá trị cuối cùng còn lại là $1$ hoặc $2$. Giá trị cuối cùng cũng không thể là $1$ vì Busy Revaeb có thể đã lấy số $1$ ở lượt $1$, đảm bảo giá trị cuối cùng lớn hơn $1$.

Busy Beaver có thể đảm bảo giá trị cuối cùng ít nhất là $2$, và Busy Revaeb có thể đảm bảo giá trị cuối cùng nhiều nhất là $2$. Do đó, giá trị cuối cùng sẽ là $2$ khi chơi tối ưu.

Giải thích mẫu 2

Giá trị cuối cùng là $1$ hoặc $2$. Nếu chiến thuật của Busy Revaeb là lấy số $2$ ngay khi có thể, thì anh ta có thể đảm bảo rằng sau lượt của mình (lượt $2$), dãy chỉ còn lại các số $1$ — bất kể Busy Beaver di chuyển như thế nào ở lượt $1$. Do đó, khi cả hai chơi tối ưu, giá trị cuối cùng sẽ là $1$.

Nhiệm vụ con

• ($15$ điểm) $N \leq 3$.
• ($25$ điểm) $1 \leq a_i \leq 2$.
• ($60$ điểm) Không có ràng buộc bổ sung.