codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.