Masala #PONTAPZBVJ

Sardorda  \(n\) ta butun sondan iborat \(a\) massiv bor \((0 \leq a[i] \leq 20, 1 \leq n \leq 10^5)\) . Sardor massivni bir nechta uzluksiz va o'zaro kesishmaydigan qism massivlarga ajratmoqchi, boshqacha so'zlar bilan aytganda har bir element aynan bitta qism massivda bo'lishi va har bir qism massiv kamida 1 ta elementdan iborat bo'lishi lozim.

Uning do'sti Farrux ajratilgan har bir qism massivning faqat birinchi elementiga qiziqadi, va uning norozilik darajasi ushbu qism massivlarning turli xil birinchi elementlarining soniga teng (turlilar soni).

Bundan tashqari, Farrux Sardoga \(m\) ta \((1 \leq m \leq 10^5)\) shart bergan:

• Har bir shart \(l\) va \(r\) \((1 \leq l \leq r \leq n )\) qiymatlaridan iborat  – shu \(l\) va \(r\) oraliqdagi birorta elementdan boshlangan kamida 1 ta qism massiv bo'lishi kerak.

Sardor Farruxning noroziligini minimallashtiradigan va barcha \(m\) ta shartlarni qanoatlantiradigan qism-massivlarga bo'lish usulini topishi kerak.  Unga yordam bering!

Birinchi qatorda \(n\) va \(m\) – mos ravishda massivnig uzunligi va Farrux bergan shartlar soni.

Keyingi qatorda \(n\) ta elementdan iborat \(a\) massiv elementlari.

Keyingi \(m\) ta qatorning har birida ikkita butun son \((l, r)\) - shartlarning parametrlari kiritiladi.

Birinchi qatorda minimal norozilik darajasini va massivning necha bo'lakka bo'linganligini \((k)\) ni chop eting.

Keyingi qatorda uzunligi \(k\) ta elementdan iborat, optimal bo'linishni tasvirlovchi massivni chiqaring. 

Shu massivni way deb olaylik. 

• \(way[i]\) – \(i\)-qismmassivning birinchi elementi indexiga teng bo'lsin. 
• \(way[1] = 1\) va \(way[i] > way[i - 1] (2  \leq i \leq k)\) bo'lsin

Agar optimal bo'lish bir nechta bo'lsa istalganini chop eting.