烏龜和小豬正在玩一個與數列相關的遊戲。他們被給予一個數列 \( a_1, a_2, \dots, a_n \)，並由烏龜先開始。烏龜和小豬輪流進行回合（所以烏龜先行動，然後是小豬，接著再輪到烏龜，依此類推）。
遊戲規則如下:
設當前數列的長度為 \( m \)。如果 \( m = 1 \)，遊戲結束。
如果遊戲未結束且輪到烏龜行動，烏龜必須選擇一個整數 \( i \)（滿足 \( 1 \leq i \leq m-1 \)），將 \( a_i \) 設為 \( \min(a_i, a_{i+1}) \)，然後移除 \( a_{i} \)。
如果遊戲未結束且輪到小豬行動，小豬必須選擇一個整數 \( i \)（滿足 \( 1 \leq i \leq m-1 \)），將 \( a_i \) 設為 \( \max(a_i, a_{i+1}) \)，然後移除 \( a_{i} \)。
烏龜的目標是最大化最終剩下的 \( a_1 \) 的值，而小豬的目標是最小化最終 \( a_1 \) 的值。請計算在雙方都採取最優策略的情況下，最終 \( a_1 \) 的值。
每個測試包含多組測試資料。
第一行包含一個整數 \( t \)（\( 1 \leq t \leq 10^4 \)）— 測試資料的數量。
每組測試資料的第一行包含一個整數 \( n \)（\( 2 \leq n \leq 10^5 \)）— 數列的長度。
每組測試資料的第二行包含 \( n \) 個整數 \( a_1, a_2, \dots, a_n \)（\( 1 \leq a_i \leq 10^5 \)）— 數列的元素。
保證所有測試資料中 \( n \) 的總和不超過 \( 10^5 \)。
對每組測試資料，輸出一個整數，表示在雙方都採取最優策略的情況下，最終 \( a_1 \) 的值。
2 3 1 3 2 4 4 2 5 1
2 4
要壓I/O?
範例說明
第一個測試案例:
烏龜選擇 \( i = 2 \)，將 \( a_2 = \max(3, 2) = 3 \)，並移除 \( a_2 \)。數列變為 \([1, 2]\)。
小豬選擇 \( i = 1 \)，將 \( a_1 = \min(1, 2) = 1 \)，並移除 \( a_1 \)。數列變為 \([2]\)。
最終 \( a_1 = 2 \)。
第二個測試案例:
經過雙方的最佳策略選擇後，最終 \( a_1 = 4 \)。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||