Busy Beaver 與 Busy Revaeb 之間長達一個世紀的競爭至今仍在持續。這一次，他們決定在一場雙人遊戲中互相挑戰。

圖 1：遊戲過程示意圖，展示了兩名玩家如何從數列中選擇相鄰數字並替換為一個新數字。

有一個包含 $N$ 個正整數的數列 $a_1, \dots, a_N$。Busy Beaver 與 Busy Revaeb 輪流進行遊戲，規則如下：

• Busy Beaver 選擇數列中兩個相鄰的數字，將它們刪除，並寫下這兩個被刪除數字中較大的一個。
• Busy Revaeb 進行同樣的操作，但寫下的是這兩個被刪除數字中較小的一個。

由 Busy Beaver 先手。當數列中只剩下一個數字 $X$ 時，遊戲結束。Busy Beaver 希望最大化 $X$；Busy Revaeb 希望最小化 $X$。若雙方皆採取最佳策略，求 $X$ 的值。

輸入格式

第一行包含一個整數 $N$ ($1 \leq N \leq 2 \cdot 10^5$)，代表陣列中的元素個數。

第二行包含 $N$ 個以空白分隔的整數 $a_1, \dots, a_N$ ($1 \le a_i \le 10^9$)。

輸出格式

輸出一個整數，代表若雙方皆採取最佳策略，陣列中最後剩下的唯一元素的值。

子任務

• ($15$ 分) $N \leq 3$。
• ($25$ 分) $1 \leq a_i \leq 2$。
• ($60$ 分) 無額外限制。

範例

輸入格式 1

3
2 1 4

輸出格式 1

2

說明

最後的值不可能是 $4$，因為如果 Busy Beaver 試圖透過在第一輪不選擇 $4$ 來保留它，Busy Revaeb 可以在下一輪取走 $4$，使最後剩下的值變為 $1$ 或 $2$。最後的值也不可能是 $1$，因為 Busy Revaeb 本可以在第一輪就取走 $1$，確保最後的值大於 $1$。

Busy Beaver 可以確保最後的值至少為 $2$，而 Busy Revaeb 可以確保最後的值至多為 $2$。因此，在最佳策略下，最後的值將會是 $2$。

輸入格式 2

4
1 1 1 2

輸出格式 2

1

說明

最後的值不是 $1$ 就是 $2$。如果 Busy Revaeb 的策略是儘快取走 $2$，那麼他可以保證在輪到他操作後（第 $2$ 回合），數列中只剩下 $1$ —— 無論 Busy Beaver 在第 $1$ 回合如何移動。因此，當雙方皆採取最佳策略時，最後的值將會是 $1$。

備註

本題為 Min-Max Game。