Qurutmağa vaxt yoxdur

Besi yaxınlarda bir rəng dəsti aldı və otlağın bir tərəfindəki uzun hasarı rəngləmək istəyir. Hasar n ardıcıl bir metrlik seqmentdən ibarətdir. Besinin n fərqli rəngi var və bu rənglər 1-dən n-ə qədər artan tündlük sırasına görə nömrələnib (1 ən açıq rəng, n ən tünd rəngdir). Beləliklə, Besi hasarın rənglənməsini n tam ədəddən ibarət massiv kimi təsvir edə bilər.

Əvvəlcə bütün seqmentlər rənglənməmişdir. Besi hər hansı bir ardıcıl seqment intervalını bir rənglə bir fırça hərəkəti ilə rəngləyə bilər. O, heç vaxt daha açıq rəngi daha tünd rəngin üzərinə çəkmir. O, yalnız daha tünd rəngi daha açıq rəngin üzərinə çəkə bilər.

Məsələn, əvvəlcə rənglənməmiş uzunluğu 4 olan hasar belə rənglənə bilər:

0000 -> 1110 -> 1122 -> 1332

Təəssüf ki, Besinin boyanın qurumasını gözləməyə vaxtı yoxdur. Buna görə də o, hasarın bəzi hissələrini rənglənməmiş buraxa biləcəyini düşünür. İndi o, q namizəd intervalları nəzərdən keçirir, hər biri iki tam ədəd (a, b) ilə təsvir olunur, 1 ≤ a ≤ b ≤ n, intervalın son nöqtələrinin indekslərini göstərir, hansı ki rənglənməlidir.

Hər bir namizəd interval üçün, bu diapazon daxilindəki bütün seqmentləri lazımi rənglə rəngləmək üçün lazım olan minimum fırça hərəkətlərinin sayını göstərin, bu diapazonun xaricindəki hasar seqmentlərini rənglənməmiş buraxın. Qeyd edək ki, Besi rəngləmə prosesini yerinə yetirmir, buna görə də bütün diapazonlar üçün cavablar müstəqildir.

Giriş məlumatları

Birinci sətir n (1 ≤ n ≤ 2 * 10^5) və q (1 ≤ q ≤ 2 * 10^5) ehtiva edir.

Növbəti sətir hasarın hər seqmenti üçün istənilən rəngi təmsil edən n tam ədəddən ibarət massiv ehtiva edir.

Növbəti q sətirin hər biri rəngləmə üçün namizəd intervalı təmsil edən iki tam ədəd a və b ehtiva edir.

Çıxış məlumatları

Hər bir q namizəd üçün cavabı yeni sətirdə verin.

Nümunə

Bu nümunədə rənglənməsi tələb olunan ilk alt diapazonun istənilən nümunəsi var

1 1 2 

2 fırça hərəkəti tələb olunur.

Növbəti diapazonun nümunəsi var

2 1 1 2

Rəngləmə üçün üç hərəkət tələb olunur.

Növbəti diapazonun nümunəsi var

1 2 2 1 1 2

Rəngləmə üçün üç hərəkət tələb olunur.

Növbəti diapazonun nümunəsi var

1 2 3 2

Rəngləmə üçün üç hərəkət tələb olunur.