Экспедиция за сокровищами началась, но Капитану Смолетту ничего не нравится. Особенно матросы.

Всего на борту есть n матросов, у каждого из них есть своя роль. Роль i-го матроса описывается натуральным числом a_i. Экспедиция будет длиться q дней, и в начале каждого дня Капитан Смолетт собирается менять роль ровно одного матроса. После этого, к концу дня капитан Смолетт оценивает свою команду и решает, какая из ролей самая важная, но делает он это не совсем обычным образом.

Вместо того чтобы просто выбирать самую частую роль, капитан ищет такую роль x, чтобы количество подотрезков массива ролей a, не содержащих роль x, было как можно меньше. Капитана Смолетта интересует, какое минимальное количество подотрезков массива ролей a не содержат роль x. Помогите капитану посчитать это значение.

В первой строке вводится два натуральных числа n и q — количество матросов и количество дней экспедиции соответственно (1 ≤ n, q ≤ 10⁵).

Во второй строке вводится последовательность из n натуральных чисел a₁, a₂, …, a_n, где a_i — роль i-го матроса (1 ≤ a_i ≤ 10⁹).

В следующих q строках содержится по два числа s и r — индекс матроса, чью роль капитан хочет изменить, и новая роль этого матроса (1 ≤ s ≤ n, 1 ≤ r ≤ 10⁹).

Для каждого из q дней выведите одно число — минимальное количество подотрезков массива ролей a, не содержащих какую-то конкретную роль x.

Рассмотрим первый пример.

1) В начале первого дня меняется роль 3-го матроса на 4. Массив ролей выглядит следующим образом: [1, 2, 4, 1, 1, 2]. Минимальное количество подотрезков без роли 1 равно 4.

2) В начале второго дня меняется роль 5-го матроса на 4. Массив ролей выглядит следующим образом: [1, 2, 4, 1, 4, 2]. Минимальное количество подотрезков без роли 4 равно 5. Заметьте, что, например, для первой роли количество подотрезков без неё равно 6.

3) В начале третьего дня меняется роль 2-го матроса на 1. Массив ролей выглядит следующим образом: [1, 1, 4, 1, 4, 2]. Минимальное количество подотрезков без роли 1 равно 4.

4) В начале четвертого дня меняется роль 3-го матроса на 1. Массив ролей выглядит следующим образом: [1, 1, 1, 1, 4, 2]. Минимальное количество подотрезков без роли 1 равно 3.

5) В начале пятого дня меняется роль 6-го матроса на 1. Массив ролей выглядит следующим образом: [1, 1, 1, 1, 4, 1]. Минимальное количество подотрезков без роли 1 равно 1.