F. Бинарный не-поиск и запросы
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для последовательности $$$b$$$, состоящей из $$$m$$$ целых чисел, множество $$$S(b)$$$ определяется как множество кортежей $$$(i,j,k)$$$, которые удовлетворяют следующим условиям:

  • $$$i$$$, $$$j$$$, $$$k$$$ — целые числа;
  • $$$1 \le k \lt m$$$;
  • $$$1 \le i \lt j \le m-k+1$$$;
  • Для каждого элемента $$$v$$$ в $$$b$$$, $$$v$$$ появляется одинаковое количество раз в $$$[b_i,b_{i+1},\ldots,b_{i+k-1}]$$$ и $$$[b_j,b_{j+1},\ldots,b_{j+k-1}]$$$.

Например, когда $$$b=[1,2,1,2]$$$, кортеж $$$(1,3,2)$$$ является элементом $$$S(b)$$$, потому что $$$1$$$ и $$$2$$$ оба появляются по одному разу в $$$[b_1,b_2]$$$ и $$$[b_3,b_4]$$$.

Кроме того, мы определяем две функции для последовательностей целых положительных чисел:

  • $$$k_\max(b)$$$ определяется как максимальное значение $$$k$$$ для всех элементов $$$(i,j,k)$$$ из $$$S(b)$$$;
  • $$$f(b)$$$ определяется как количество различных элементов $$$(i,j,k)$$$ из $$$S(b)$$$ таких, что $$$k=k_\max(b)$$$.

В качестве исключения, когда множество $$$S(b)$$$ пусто, они определяются как $$$k_\max(b)=0$$$ и $$$f(b)=0$$$.

Вам дана последовательность $$$a$$$ из $$$n$$$ целых чисел. Пожалуйста, ответьте на $$$q$$$ запросов следующего вида:

  • $$$i\;x$$$: Измените значение $$$a_i$$$ на $$$x$$$. Затем найдите значения $$$k_\max(a)$$$ и $$$f(a)$$$.

Обратите внимание, что обновления являются постоянными. Другими словами, обновление из одного запроса влияет на последующие запросы.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$2 \le n \le 200\,000$$$, $$$1 \le q \le 100\,000$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$).

Каждая из следующих $$$q$$$ строк содержит два целых числа $$$i_j$$$ и $$$x_j$$$, обозначающие $$$j$$$-й запрос ($$$1 \le i_j,x_j \le n$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$200\,000$$$.

Гарантируется, что сумма $$$q$$$ по всем наборам входных данных не превосходит $$$100\,000$$$.

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

Для каждого набора входных данных выведите $$$q$$$ строк.

В $$$j$$$-й строке вы должны вывести значения $$$k_\max(a)$$$ и $$$f(a)$$$ для $$$j$$$-го запроса.

Можно показать, что оба значения никогда не превосходят $$$10^{11}$$$ в рамках ограничений этой задачи.

Пример
Входные данные
4
5 3
1 2 3 4 5
3 2
4 1
5 2
4 3
1 2 1 1
4 2
3 2
2 1
5 2
1 3 2 4 5
5 3
5 5
8 3
1 2 3 4 1 2 5 4
7 3
7 4
2 1
Выходные данные
1 1
3 1
3 3
2 3
2 1
1 2
3 1
0 0
4 10
4 4
4 2
Примечание

Сразу после первого запроса второго набора входных данных, $$$a=[1,2,1,2]$$$. Элементы множества $$$S(a)$$$ следующие:

  • $$$(1,3,1)$$$: $$$[\color{red}{1},2,\color{blue}{1},2]$$$;
  • $$$(2,4,1)$$$: $$$[1,\color{red}{2},1,\color{blue}{2}]$$$;
  • $$$(1,2,2)$$$: $$$[\color{red}{1},\color{magenta}{2},\color{blue}{1},2]$$$;
  • $$$(1,3,2)$$$: $$$[\color{red}{1},\color{red}{2},\color{blue}{1},\color{blue}{2}]$$$;
  • $$$(2,3,2)$$$: $$$[1,\color{red}{2},\color{magenta}{1},\color{blue}{2}]$$$.

Таким образом, $$$k_\max(a)=2$$$, и $$$f(a)=3$$$, потому что существует три элемента $$$(i,j,k)$$$, где $$$k=k_\max(a)=2$$$.

Сразу после второго запроса третьего набора входных данных, $$$a=[1,3,2,4,5]$$$. Множество $$$S(a)$$$ в этот момент пусто.

По определению, вы должны вывести $$$k_\max(a)=0$$$ и $$$f(a)=0$$$, потому что $$$S(a)$$$ в данный момент пусто.