Masala B
Smurflar zinasi
Smurflar bayram kuni umumiy rasmga tushishmoqchi. Ular chapdan o'ngga bir qator bo'lib turishadi.
Rasm chiroyli chiqishi uchun har bir keyingi smurf oldingisidan qat'iy balandroq bo'lishi kerak.
\(i\)-smurfning hozirgi bo'yi \(a_i\). Bir amalda istalgan bitta smurfning bo'yini \(1\) birlikka oshirish mumkin. Bo'yini kamaytirish mumkin emas.
Eng kam nechta amal yordamida smurflar qatorini qat'iy o'suvchi qilish mumkinligini toping.
Kiruvchi ma'lumotlar:
Birinchi qatorda bitta butun son \(t\) beriladi — testlar soni.
Har bir test quyidagi ko'rinishda beriladi:
Birinchi qatorda bitta butun son \(n\) beriladi — smurflar soni.
Ikkinchi qatorda \(n\) ta butun son \(a_1,a_2,\ldots,a_n\) beriladi — smurflarning hozirgi bo'ylari.
Cheklovlar:
\[
1 \le t \le 1000
\]
\[
1 \le n \le 2 \cdot 10^5
\]
\[
0 \le a_i \le 10^9
\]
\[
\sum n \le 2 \cdot 10^5
\]
Chiquvchi ma'lumotlar:
Har bir test uchun alohida qatorda smurflar qatorini qat'iy o'suvchi qilish uchun kerak bo'ladigan eng kam amallar sonini chiqaring.
Misollar
| # | input.txt | output.txt |
|---|---|---|
| 1 |
4 5 1 2 3 4 5 3 2 2 2 4 5 4 3 2 1 100 |
0 3 12 0 |
Izoh:
Birinchi testda bo'ylar allaqachon qat'iy o'suvchi.
Ikkinchi testda \([2,2,2]\) qatorini \([2,3,4]\) qilish mumkin. Buning uchun \(0+1+2=3\) amal kerak.
Uchinchi testda \([5,4,3,2]\) qatorini \([5,6,7,8]\) qilish optimal. Jami \(0+2+4+6=12\) amal kerak.
To'rtinchi testda faqat bitta smurf bor, shuning uchun javob \(0\).
Telegram kanalimizga obuna bo'ling