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\).
Выходные данные
Для каждого набора входных данных выведите одно число — минимальную длину отрезка, к которому можно применить описанную в условии операцию, чтобы сделать элементы на всех заданных отрезках различными. Если можно не применять операцию, то выведите \(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]\), в котором все числа различны, а значит, на каждом из данных отрезков все число также различны.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|