1975C.md (2594B)
1 Source: https://codeforces.com/problemset/problem/1975/C 2 3 C. Chamo and Mocha's Array 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Mocha likes arrays, so before her departure, Chamo gave her an array $a$ consisting of $n$ positive integers as a gift. 22 23 Mocha doesn't like arrays containing different numbers, so Mocha decides to use magic to change the array. Mocha can perform the following three-step operation some (possibly, zero) times: 24 25 1. Choose indices $l$ and $r$ ($1 \leq l \lt r \leq n$) 26 2. Let $x$ be the median$^\dagger$ of the subarray $[a_l, a_{l+1},\ldots, a_r]$ 27 3. Set all values $a_l, a_{l+1},\ldots, a_r$ to $x$ 28 29 Suppose $a=[1,2,3,4,5]$ initially: 30 31 * If Mocha chooses $(l,r)=(3,4)$ in the first operation, then $x=3$, the array will be changed into $a=[1,2,3,3,5]$. 32 * If Mocha chooses $(l,r)=(1,3)$ in the first operation, then $x=2$, the array will be changed into $a=[2,2,2,4,5]$. 33 34 Mocha will perform the operation until the array contains only the same number. Mocha wants to know what is the maximum possible value of this number. 35 36 $^\dagger$ The median in an array $b$ of length $m$ is an element that occupies position number $\lfloor \frac{m+1}{2} \rfloor$ after we sort the elements in non-decreasing order. For example, the median of $[3,1,4,1,5]$ is $3$ and the median of $[5,25,20,24]$ is $20$. 37 38 Input 39 40 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\leq t\leq 500$). The description of the test cases follows. 41 42 The first line of each test case contains a single integer $n$ ($2\leq n\leq 10^5$) — the length of the array $a$. 43 44 The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\leq a_i \leq 10^9$) — the elements of the array $a$. 45 46 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. 47 48 Output 49 50 For each test case, output the maximum value of the number. 51 52 Example 53 54 Input 55 56 ``` 57 2 58 59 2 60 61 1 2 62 63 5 64 65 1 2 3 4 5 66 ``` 67 68 Output 69 70 ``` 71 1 72 4 73 ``` 74 75 Note 76 77 In the first test case, $a=[1,2]$. Mocha can only choose the interval $(l,r)=(1,2)$. The array will be changed to $a=[1,1]$. Therefore, the answer is $1$. 78 79 In the second test case, Mocha can perform the following operations: 80 81 * Choose the interval $(l,r)=(4,5)$, then $a=[1,2,3,4,4]$. 82 * Choose the interval $(l,r)=(3,5)$, then $a=[1,2,4,4,4]$. 83 * Choose the interval $(l,r)=(1,5)$, then $a=[4,4,4,4,4]$. 84 85 The array contains only the same number, which is $4$. It can be proven that the maximum value of the final number cannot be greater than $4$.