C. Chamo and Mocha's Array

Mocha likes arrays, so before her departure, Chamo gave her an array 𝑎 consisting of 𝑛 positive integers as a gift.

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:

1. Choose indices l and 𝑟 (1≤𝑙<𝑟≤𝑛)
2. Let 𝑥 be the median of the subarray [𝑎𝑙,𝑎𝑙+1,…,𝑎𝑟]
3. Set all values 𝑎𝑙,𝑎𝑙+1,…,𝑎𝑟 to 𝑥

Suppose 𝑎=[1,2,3,4,5] initially:

• If Mocha chooses (𝑙,𝑟)=(3,4) in the first operation, then 𝑥=3, the array will be changed into 𝑎=[1,2,3,3,5].
• If Mocha chooses (𝑙,𝑟)=(1,3) in the first operation, then 𝑥=2, the array will be changed into 𝑎=[2,2,2,4,5].

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.† The median in an array b of length 𝑚 is an element that occupies position number ⌊𝑚+12⌋ 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.