F. Разнообразные отрезки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

CrowdForces — большой проект с большими амбициями. Тётя Люсине об этом знает и делает всё для развития этого проекта. Не так давно она договорилась с админами самых разных платформ с задачами на программирование, чтобы использовать эти платформы для CrowdForces. Но ей в голову пришла ещё одна гениальная мысль: взять с каждой платформы случайную задачу и из задачи взять что-то своё. Собрав всё вместе, Тётя Люсине с улыбкой представляет вам свою собственную задачу, которую вам и предстоит решить.

Дан массив $$$a$$$ из $$$n$$$ целых чисел. Также вам даны $$$m$$$ отрезков этого массива. Левая и правая границы $$$j$$$-го отрезка равны $$$l_j$$$ и $$$r_j$$$ соответственно.

Вам разрешается не более одного раза применить следующую операцию. Вы выбираете произвольный отрезок массива $$$a$$$ и заменяете значения элементов на этом отрезке на любые (вы также можете не менять значения некоторых элементов на этом отрезке).

Ваша задача заключается в том, чтобы, применив такую операцию, значения элементов на каждом из данных $$$m$$$ отрезков были различны. Более формально, для каждого $$$1 \le j \le m$$$ среди элементов $$$a_{l_{j}}, a_{l_{j}+1}, \ldots, a_{r_{j}-1}, a_{r_{j}}$$$ не должно быть одинаковых.

Вам не хочется применять эту операцию к слишком большому отрезку, поэтому необходимо найти минимальную длину отрезка, к которому можно применить операцию, чтобы данное условие выполнялось. В частности, если такую операцию можно не применять, выведите $$$0$$$.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — длина массива и количество отрезков соответственно.

Следующая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — элементы массива $$$a$$$.

Каждая из следующих $$$m$$$ строк содержит два целых числа $$$l_j$$$ и $$$r_j$$$ ($$$1 \le l_j \le r_j \le n$$$) — описание $$$j$$$-го отрезка.

Гарантируется, что сумма $$$n$$$ и сумма $$$m$$$ по всем наборам входных данных не превышают $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите одно число — минимальную длину отрезка, к которому можно применить описанную в условии операцию, чтобы сделать элементы на всех заданных отрезках различными. Если можно не применять операцию, то выведите $$$0$$$.

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

В первом наборе входных данных можно применить операцию к отрезку $$$[1, 2]$$$ и сделать массив $$$a = [5, 6, 2, 1, 3, 3, 5]$$$.

  • На отрезке $$$[1, 4]$$$ будут числа $$$[5, 6, 2, 1]$$$.
  • На отрезке $$$[4, 5]$$$ будут числа $$$[1, 3]$$$.
  • На отрезке $$$[2, 4]$$$ будут числа $$$[6, 2, 1, 3]$$$.

Таким образом на каждом из данных отрезков все числа будут различны. При этом нельзя заменить ровно одно число, чтобы на каждом из данных отрезков все числа были различны. Поэтому ответ равен $$$2$$$.

Во втором наборе входных данных на каждом из данных отрезков все числа уже различны, поэтому мы можем не применять операцию.

В третьем наборе входных данных мы можем заменить первую $$$5$$$ на $$$1$$$. Тогда мы получим массив $$$[1, 7, 5, 6]$$$, в котором все числа различны, а значит, на каждом из данных отрезков все число также различны.