Беси недавно получила набор красок, и она хочет раскрасить длинный забор с одной стороны пастбища. Забор состоит из n последовательных однометровых сегментов. У Беси есть n различных цветов, которые она обозначила числами от 1 до n в порядке возрастания темноты (1 очень светлый цвет, а n очень тёмный). Таким образом, Беси может описать раскраску забора как массив из n целых чисел.

Изначально все сегменты не раскрашены. Беси может раскрасить любой непрерывный интервал отрезков одним цветом за одно движение кисти. Она никогда не красит более светлым цветом поверх более темного. Она только может красить более темным цветом поверх более светлого.

Например, изначально нераскрашенный забор длины 4 может быть закрашен так:

0000 -> 1110 -> 1122 -> 1332

К несчастью, у Беси нет времени ждать пока краска высохнет. Поэтому она думает, что может оставлять некоторые участки забора незакрашенными. Сейчас она рассматривает q кандидатов-интервалов, каждый описывается двумя целыми числами (a, b), 1 ≤ a ≤ b ≤ n описывающими индексы конечных точек интервала, которые нужно раскрасить.

Для каждого кандидата-интервала укажите минимальное количество движений кисти, которое требуется чтобы раскрасить все отрезки внутри этого диапазона нужным цветом, оставив незакрашеммыми все отрезки забора вне этого диапазона. Заметим, что Беси не выполняет процесс покраски, поэтому ответы для всех диапазонов независимы.

Входные данные

Первая строка содержит n (1 ≤ n ≤ 2 * 105) и q (1 ≤ q ≤ 2 * 105).

Следующая строка содержит массив из n целых чисел, представляющих желаемый цвет для каждого отрезка забора.

Каждая из следующих q строк содержит два целых числа a и b, представляющих кандидат-интервал на раскраску.

Выходные данные

Для каждого из q кандидатов, выведите ответ в новой строке.

Пример

В этом примере первый поддиапазон, требующий раскраски имеет желаемый образей

1 1 2

требуется 2 движения кисти.

Следующий диапазон имеет образец

2 1 1 2

Требуется три движения для раскраски

Следующий диапазон имеет образец

1 2 2 1 1 2

Требуется три движения для раскраски

Следующий диапазон имеет образец

1 2 3 2

Требуется три движения для раскраски