Бесі нещодавно отримала набір фарб, і вона хоче розфарбувати довгий паркан з однієї сторони пасовища. Паркан складається з \(N\) послідовних однометрових сегментів (\(1\le N\le 2\cdot 10^5\)). У Бесі є \( N \) різних кольорів, які вона позначила числами від \(1\) до \(N\) у порядку зростання темного (\(1\) дуже світлий колір, а \(N\) дуже темний). Таким чином, Бесі може описати забарвлення паркану як масив з \( N \) цілих чисел.

Спочатку всі сегменти не розфарбовані. Бесі може розфарбувати будь-який безперервний інтервал відрізків одним кольором за один рух пензля. Вона ніколи не фарбує світлішим кольором поверх темнішого. Вона тільки може фарбувати темнішим кольором поверх світлішого.

Наприклад, спочатку нерозфарбований паркан довжини 4 може бути зафарбований так:

0000 -> 1110 -> 1122 -> 1332

На жаль, у Бесі немає часу чекати поки фарба висохне. Тому вона вважає, що може залишати деякі ділянки паркану незафарбованими. Зараз вона розглядає \(Q\) кандидатів-інтервалів (\(1\le Q\le 2\cdot 10^5\)), кожен описується двома цілими числами \((a,b)\), \(1 \leq a \leq b \leq N\) описують індекси кінцевих точок інтервалу, які потрібно розфарбувати.

Для кожного кандидата-інтервалу вкажіть мінімальну кількість рухів пензля, яке потрібно, щоб розфарбувати всі відрізки всередині цього діапазону потрібним кольором, залишивши незакрашеними всі відрізки паркану поза цим діапазоном.

Зауважимо, що Бесі не виконує процес фарбування, тому відповіді для всіх діапазонів незалежні.

Формат вхідних даних

Перший рядок містить \(N\) та \(Q\).

Наступний рядок містить масив з \(N\) цілих чисел, що становлять бажаний колір для кожного відрізка огорожі.

Кожен із наступних \(Q\) рядків містить два розділені пробілом цілих числа, \(a\) і \(b\), представляють кандидат-інтервал на розмальовку.

Формат вихідних даних

Для кожного з \(Q\) кандидатів, виведіть відповідь у новому рядку.

Приклад вхідних даних

8 4
1 2 2 1 1 2 3 2
4 6
3 6
1 6
5 8

Приклад вихідних даних

2
3
3
3

У цьому прикладі перший піддіапазон, що вимагає розмальовки, має бажаний зразок.

1 1 2 

потрібно 2 рухи пензля.

Наступний діапазон має зразок

2 1 1 2

Потрібно три рухи для розмальовки

Наступний діапазон має зразок

1 2 2 1 1 2

Потрібно три рухи для розмальовки

Наступний діапазон має зразок

1 2 3 2

Потрібно три рухи для розмальовки

ОЦІНЮВАННЯ:

• У тестах 1-2 \(N,Q\le 100\).
• У тестах 3-5 \(N,Q\le 5000\).
• У тестах 6-10, вхідний масив не містить чисел більших за \(10\).
• У тестах 11-20 немає додаткових обмежень.