Экспедиция за сокровищами началась, но Капитану Смолетту ничего не нравится. Особенно матросы.
Всего на борту есть $$$n$$$ матросов, у каждого из них есть своя роль. Роль $$$i$$$-го матроса описывается натуральным числом $$$a_i$$$. Экспедиция будет длиться $$$q$$$ дней, и в начале каждого дня Капитан Смолетт собирается менять роль ровно одного матроса. После этого, к концу дня капитан Смолетт оценивает свою команду и решает, какая из ролей самая важная, но делает он это не совсем обычным образом.
Вместо того чтобы просто выбирать самую частую роль, капитан ищет такую роль $$$x$$$, чтобы количество подотрезков массива ролей $$$a$$$, не содержащих роль $$$x$$$, было как можно меньше. Капитана Смолетта интересует, какое минимальное количество подотрезков массива ролей $$$a$$$ не содержат роль $$$x$$$. Помогите капитану посчитать это значение.
В первой строке вводится два натуральных числа $$$n$$$ и $$$q$$$ — количество матросов и количество дней экспедиции соответственно ($$$1 \leq n, q \leq 10^5$$$).
Во второй строке вводится последовательность из $$$n$$$ натуральных чисел $$$a_1, a_2, \dots, a_n$$$, где $$$a_i$$$ — роль $$$i$$$-го матроса ($$$1 \leq a_i \leq 10^9$$$).
В следующих $$$q$$$ строках содержится по два числа $$$s$$$ и $$$r$$$ — индекс матроса, чью роль капитан хочет изменить, и новая роль этого матроса ($$$1 \leq s \leq n$$$, $$$1 \leq r \leq 10^9$$$).
Для каждого из $$$q$$$ дней выведите одно число — минимальное количество подотрезков массива ролей $$$a$$$, не содержащих какую-то конкретную роль $$$x$$$.
6 51 2 3 1 1 23 45 42 13 16 1
4 5 4 3 1
7 42 3 2 3 4 2 31 44 26 52 1
5 5 9 9
Рассмотрим первый пример.
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.
