Немає часу на сушку
Бесі нещодавно отримала набір фарб і хоче розфарбувати довгий паркан з одного боку пасовища. Паркан складається з n послідовних однометрових сегментів. У Бесі є n різних кольорів, які вона позначила числами від 1 до n у порядку зростання темряви (1 — дуже світлий колір, а n — дуже темний). Таким чином, Бесі може описати розфарбування паркану як масив з n цілих чисел.
Спочатку всі сегменти не розфарбовані. Бесі може розфарбувати будь-який неперервний інтервал сегментів одним кольором за один рух пензля. Вона ніколи не фарбує більш світлим кольором поверх більш темного. Вона може фарбувати лише більш темним кольором поверх більш світлого.
Наприклад, спочатку нефарбований паркан довжини 4 може бути зафарбований так:
0000 -> 1110 -> 1122 -> 1332
На жаль, у Бесі немає часу чекати, поки фарба висохне. Тому вона вважає, що може залишати деякі ділянки паркану незабарвленими. Зараз вона розглядає q кандидатів-інтервалів, кожен з яких описується двома цілими числами (a, b), де 1 ≤ a ≤ b ≤ n, що вказують на індекси кінцевих точок інтервалу, які потрібно розфарбувати.
Для кожного кандидата-інтервалу вкажіть мінімальну кількість рухів пензля, необхідних для розфарбування всіх сегментів всередині цього діапазону потрібним кольором, залишивши незабарвленими всі сегменти паркану поза цим діапазоном. Зазначимо, що Бесі не виконує процес фарбування, тому відповіді для всіх діапазонів незалежні.
Вхідні дані
Перший рядок містить n (1 ≤ n ≤ 2 * 10^5) і q (1 ≤ q ≤ 2 * 10^5).
Наступний рядок містить масив з n цілих чисел, що представляють бажаний колір для кожного сегмента паркану.
Кожен з наступних q рядків містить два цілі числа a і b, що представляють кандидат-інтервал на розфарбування.
Вихідні дані
Для кожного з q кандидатів виведіть відповідь у новому рядку.
Приклад
У цьому прикладі перший піддіапазон, що вимагає розфарбування, має бажаний зразок
1 1 2
потрібно 2 рухи пензля.
Наступний діапазон має зразок
2 1 1 2
Потрібно три рухи для розфарбування.
Наступний діапазон має зразок
1 2 2 1 1 2
Потрібно три рухи для розфарбування.
Наступний діапазон має зразок
1 2 3 2
Потрібно три рухи для розфарбування.