logo small logo dark logo small logo
Kirish
Musobaqa Masalalar Urinishlar Natijalar Ishtirokchilar
A 10 B 10 C 10 D 10 E 10 F 10 G 10 H 10
Muallif: Shoyim Obloqulov
Vaqt: 2000 ms Xotira: 256 mb
15

Sarvar va Sehrli Massiv

Sarvar massivlarni yaxshi ko'radi. Bir kuni uning o'qituvchisi unga $n$ ta musbat butun sondan iborat $a$ massivini sovg'a qildi. Sarvar bir xil bo'lmagan sonlardan iborat massivni yoqtirmaydi, shuning uchun u massivni sehrli amal yordamida o'zgartirmoqchi.

Sarvar quyidagi uch qadamli amalni istagancha (nol marta ham) bajarishi mumkin:

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

Sarvar massivdagi barcha elementlar bir xil bo'lguncha amalni bajaraveradi. Sarvar shu oxirgi qiymat imkon qadar katta bo'lishini xohlaydi.

$^\dagger$ Median - $m$ ta elementdan iborat $b$ massivini o'sish tartibida saralagandan keyin $\lfloor (m+1)/2 \rfloor$ o'rindagi element. Masalan, $[3, 1, 4, 1, 5]$ massivining medianasi $3$ ga, $[5, 25, 20, 24]$ massivining medianasi esa $20$ ga teng.

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

Telegram
Yechim yuborish uchun tizimga kiring yoki ro'yxatdan o'ting.