АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Калвин машинтайгаа хурдны замаар явж байтал хөдөлгүүрээ шалга гэсэн дохиог машин нь өгөв.

Тэр муу юм болохоос сэргийлж машинаа засварт өгөхийг завдав. Азаар замын хажууд засварын газар байв.

N ширхэг замын өргөнийг илэрхийлэх тоо өгөгдөнө.

Машин засвар замын i-с j-н хооронд байгаа бол машин засвараар багтаж болох машины өргөнийг олоорой. (хамгийн их)

Оролт

Эхний мөрөнд n тоо болон тестийн тоо t зайгаар тусгаарлагдан өгөгдөнө.(2<=n<=10^5) (1<=t<=1000)

Дараагийн мөрөнд замын өргөнийг илэрхийлэх n ширхэг тоо өгөгдөнө.

Дараагийн t мөр бүрт засварын газрыг илэрхийлэх i,j  тооөгөгдөнө.(0<=i<j<n)

(2<=i+j-1<=min(n,1000))

Гаралт

Тест бүр дээрх  засвараар орж болох машины хамтгийн урт өргөнийг хэвлэ.

Жишээ

Оролт

8 5

2 3 1 2 3 2 3 3

0 3

4 6

6 7

3 5

0 7

Гаралт

1

2

3

2

1

Тайлбар

Замын өргөн

0: |       |--|            2

1: |       |---|           3

2: |       |-|             1

3: |       |--|            2

4: |       |---|           3

5: |       |--|            2

6: |       |---|           3

7: |       |---|           3

Тестүүд

0-4 хооронд явж байгаа машин учир байж болох хамгийн урт өргөн нь 1

4-6 хооронд 2

6-7 хооронд 3

3-5 хооронд 2

0-7 хооронд 1

Орчуулсан : Дархан-Уул аймгийн Монгол-Оюу сургуулийн 11.1 ангийн сурагч Э.Цэлмэг