Masala #PWOT2QLH8Z
Quid mutatio
Garri Potterda N ta sondan iborat massiv mavjud. Garri Potter o’zining sehrli tayoqchasi yordamida massivga quyidagi shaklda o‘zgartirish kirita oladi. Garri Potter ixtiyoriy x sonini hamda massivning ixtiyoriy \(1(1 < k)\) -elementini tanlaydi hamda sehrli tayoqchasini silkitib «Quid mutatio» deb aytgan holda massivning k-elementiga tekkizadi, va natijada massivning k-elementi va undan keyingi barcha elementlari ai soni \(2x − a_i\) soniga o‘zgaradi. Yanada aniqroq, barcha \(k ≤ i ≤ n\) uchun \(a_i := 2x − a_i\) ro‘y beradi.
Garri Potter shu amal yordamida massiv elementlarini kamaymaslik tartibiga keltirmoqchi hamda hosil bo’ladigan massivning eng katta qiymati imkon qadar kichikroq bo‘lishini istaydi. Garri Potter o’z istagiga erishganida massivning eng katta qiymati necha bo‘lishini hamda shu natijaga erishish uchun Garri Potter eng kamida necha marotaba sehrli tayoqcha kuchidan foydalanishini aniqlang.
Kirish faylining dastlabki satrida bitta butun son,\( N(1 ≤ N ≤ 10^5)\) soni kiritiladi. Ikkinchi satrda N ta butun son, \(a(−10^9 ≤ a_i ≤ 10^9)\) massiv elementlari kiritiladi.
Chiqish faylining yagona satrida ikkita butun son, Garri Potter o’z istagiga erishganida massivning eng katta qiymati necha bo’lishini hamda shu natijaga erishish uchun Garri Potter eng kamida necha marotaba sehrli tayoqcha kuchidan foydalanishini chop eting.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 1 3 2 |
2 1 |
| 2 |
5 0 -9 3 2 1 |
3 3 |
1-testda 1 ta amalda, Garri Poter k = 2 va x = 2 ni tanlab massivini [1,1,2] qilishi mumkin. Shunda u 1 ta amalda massivini o‘suvchi qiladi va eng katta elementni 2 ga teng qiladi.
Telegram kanalimizga obuna bo'ling