Sarvar va Sehrli Massiv
$l$ va $r$indekslarini tanlaydi $(1 \le l < r \le n)$$x$ ni $[a_l, a_{l+1}, \dots, a_r]$qism-massivning medianasi$^\dagger$ sifatida aniqlanadi $a_l, a_{l+1}, \dots, a_r$ qiymatlarining barchasi $x$ga tenglashtiriladi
Kiruvchi ma'lumotlar
Birinchi qatorda test-holatlari soni $t$ beriladi $(1 \le t \le 500)$.
Har bir test-holat uchun: birinchi qatorda $n$ $(2 \le n \le 10^5)$ — massiv uzunligi; ikkinchi qatorda $n$ ta butun son $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 10^9)$. Barcha test-holatlardagi $n$ ning yig'indisi $10^5$ dan oshmaydi.
Chiquvchi ma'lumotlar
Har bir test-holat uchun bitta son chiqaring — massivning oxirgi holati uchun erishish mumkin bo'lgan maksimal qiymat.
Misollar
| # | Input TXT | Output TXT |
|---|---|---|
| 1 |
2 2 1 2 5 1 2 3 4 5 |
1 4 |
Izoh
1-test: $a = [1, 2]$. Sarvar faqat $(l, r) = (1, 2)$ ni tanlashi mumkin. Massiv $[1, 1]$ ga o'zgaradi. Javob: $1$.
2-test: $a = [1, 2, 3, 4, 5]$. Bir mumkin bo'lgan amallar ketma-ketligi: $(4, 5) \to [1, 2, 3, 4, 4]$; keyin $(3, 5) \to [1, 2, 4, 4, 4]$; keyin $(1, 5) \to [4, 4, 4, 4, 4]$. Javob: $4$. Bundan katta qiymatga erishib bo'lmaydi.
3-test: $a = [5, 5, 5, 5, 5, 5]$. Barcha elementlar allaqachon teng. Javob: $5$.