Masala #R110G
Qulfli segmentlar
Sizga uzunligi \(n\) bo'lgan massiv berilgan:
\[ a_1,a_2,\ldots,a_n \]
Massivni bir yoki bir nechta bo'sh bo'lmagan ketma-ket segmentlarga bo'lish kerak. Segmentlar massivning barcha elementlarini chapdan o'ngga qamrab oladi, har bir element aynan bitta segmentga kiradi. Segment \([l,r]\) ning kaliti \(K(l,r)\) quyidagicha aniqlanadi:
\[ K(l,r)=\min(a_l,a_{l+1},\ldots,a_r)+\max(a_l,a_{l+1},\ldots,a_r) \]
Bo'linish yaxshi deyiladi, agar hosil bo'lgan segmentlar chapdan o'ngga qaralganda ularning kalitlari kamaymaydigan tartibda bo'lsa. Agar bo'linishda \(m\) ta segment bo'lsa va ularning kalitlari \(k_1,k_2,\ldots,k_m\) bo'lsa, quyidagi shart bajarilishi kerak:
\[ k_1\le k_2\le \cdots \le k_m \]
Sizning vazifangiz massivni yaxshi bo'linishlar sonini topishdir. Javob juda katta bo'lishi mumkin, shuning uchun uni \(998244353\) ga bo'lgandagi qoldiq sifatida chiqaring.
Birinchi qatorda bitta butun son \(t\) — testlar soni beriladi. Har bir test uchun birinchi qatorda bitta butun son \(n\) beriladi. Ikkinchi qatorda \(n\) ta butun son beriladi:
\[ a_1,a_2,\ldots,a_n \]
Cheklovlar:
\[ \begin{aligned} 1&\le t\le 1000,\\ 1&\le n\le 2000,\\ 1&\le \sum n\le 2000,\\ 1&\le a_i\le 10^9. \end{aligned} \]
Bu yerda \(\sum n\) barcha testlar bo'yicha \(n\) qiymatlari yig'indisini bildiradi.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 3 1 2 3 3 3 1 2 4 5 5 5 5 |
4 2 8 |
Birinchi testda massiv \(1,2,3\) ko'rinishida berilgan. Uning barcha mumkin bo'lgan bo'linishlari yaxshi:
\[ [1][2][3],\quad [1][2,3],\quad [1,2][3],\quad [1,2,3] \]
Bu bo'linishlarning kalitlari mos ravishda:
\[ 2,4,6;\qquad 2,5;\qquad 3,6;\qquad 4 \]
Shuning uchun javob \(4\). Ikkinchi testda massiv \(3,1,2\) ko'rinishida berilgan. Yaxshi bo'linishlar faqat ikkitadir:
\[ [3,1][2],\quad [3,1,2] \]
Uchinchi testda barcha elementlar teng. Har bir segmentning kaliti \(10\) ga teng bo'ladi, shuning uchun har qanday bo'linish yaxshi. Uzunligi \(4\) bo'lgan massiv uchun bo'linishlar soni \(2^3=8\).
Telegram kanalimizga obuna bo'ling