Masala #1034
Asadbekning gullari
Asadbek gullarni parvarishlashni yoqtiradi. U “Ci plus plusium” gullaridan o‘zining qator joylashgan \(n\) ta tuvagining barchasiga ekdi. Birinchi kuni barcha gullarning bo‘yi 0 deb hisoblasa bo‘ladi. Shu kundan boshlab har kuni Asadbek:
- shunday \([l, r]\) oraliqni tanlaydiki, shu oraliqdagi barcha tuvaklardagi gullarning bo‘yi bir xil bo‘lsin;
- \([l+1,r-1]\) oraliqdagi barcha tuvaklarga suv quyadi. Keyingi kungacha shu oraliqdagi tuvaklarda joylashgan gullar 1 birlikka ga o‘sadi.
Misol, \(n=6\) uchun mos ravishda 1-2-3-kunlardagi gullarning bo‘yini quyidagicha tasvirlash mumkin:
1-kuni \([1,6]\) oraliq tanlangan va \([2,5]\) oraliqdagi tuvaklarga suv quyilgan.
2-kuni \([3,5]\) oraliq tanlangan va \([4,4]\) oraliqdagi tuvaklarga suv quyilgan.
0 yoki bir necha kundan so‘ng, Asadbek o‘zining gullari bilan maqtanmoqchi bo‘lib, har bir gulining bo‘yini \(A\) massiviga yozib, uni sizga berdi (\(A_i=i\)-tuvakdagi gulning bo‘yi). Ammo ba’zi gullarining bo‘ylarini eslay olmagani uchun, ularning bo‘ylarini o‘rniga -1 sonini yozdi.
Sizning vazifangiz Asadbek bergan ma’lumotlarga ko‘ra, bugungi kunda uning gullari necha xil ko‘rinishda bo‘lishi mumkinligini sanashdir. Agarda Asadbek sizni aldagan bo‘lsa, 0 chiqaring.
Natija katta bo‘lishi mumkinligi sababli, natijani \(10^9+7\) ga bo‘lingandagi qoldig‘ini chiqaring.
Kirish oqimining birinchi qatorida bitta butun son - \(n(1 \le n \le 10^4)\) kiritiladi.
Keyingi qatorda \(n\) ta butun son - Asadbek sizga bergan \(A\) massiv elementlari kiritiladi. Massiv elementlari yoki -1 yoki \(10^4\) dan oshmaydigan butun manfiy bo‘lmagan sonlardir.
Hozir Asadbekning gullari necha xil ko‘rinishda bo‘lishi mumkin ekanligini \(10^9+7\) ga bo‘lgandagi qoldig‘ini chiqaring. U aldagan bo‘lsa 0 chiqaring.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
4 -1 -1 3 -1 |
0 |
| 2 |
6 -1 -1 2 -1 -1 -1 |
3 |
Birinchi testda:
Hech qanday usulda \(n=4\) uchun bo‘yi 3 bo‘lgan gul o‘stirib bo‘lmaydi. Demak Asadbek aldagan.
Ikkinchi testda:
Asadbekning gullari quyidagi 3 xil ko‘rinishda bo‘lishi mumkin:
\([0,1,2,2,1,0]\);
\([0,1,2,1,1,0]\);
\([0,1,2,1,0,0]\).
Telegram kanalimizga obuna bo'ling