Как бы вы ответили. У Антона есть массив а длины n, каждый элемент которого имеет целое значение в диапазоне от 1 до k(включительно). Ему хочется узнать: есть ли в массиве какой-нибудь подотрезок длины №, который содержит все числа от 1 до k?
Если же такой подотрезок есть, требуется вывести позицию его начала (элементы массива нумеруются с 1), иначе требуется вывести 1. Если вариантов ответов несколько, то требуется вывести минимальный из них. Формат входных данных:
В первой строке дано два числа n и k (1 ≤ k ≤ n ≤2*10^5) количество элементов массива и число k соответственно.
Во второй строке даны n чисел а(индекс i) (1 ≤ a(индекс i) ≤ k) - элементы массива а. Формат выходных данных:
Выведите ответ на задачу.
Ввод:
4 3
1 2 3 1
Вывод:
1

Ввод:
4 3
1 2 2 2
Вывод:
-1

Ввод:
5 4
2 4 2 1 3
Вывод:
2

Ввод:
5 5
2 5 4 2 1
Вывод:
-1

Ввод:
5 2
2 2 2 1 2
Вывод:
3

Пусть указатель i указывает на начало подотрезка, а указатель j - на конец подотрезка. Тогда, пока j < n, будем сдвигать j вправо, добавляя новые элементы в подотрезок. Если подотрезок содержит все числа от 1 до k, то будем сдвигать i вправо, удаляя элементы из подотрезка, пока он не перестанет содержать все числа от 1 до k. В процессе решения задачи, будем поддерживать массив cnt, где cnt - количество элементов в подотрезке, которые равны i. Также будем поддерживать переменную sum - количество чисел от 1 до k, которые содержатся в текущем подотрезке.

Таким образом, алгоритм решения задачи будет выглядеть следующим образом:

  1. Инициализировать указатели i и j на 1, массив cnt и переменную sum на 0.

  2. Пока j <= n, выполнять следующие действия:

      * Добавить a[j] в подотрезок и увеличить cnt[a[j]] на 1.

      * Если a[j] <= k и cnt[a[j]] = 1, то увеличить sum на 1.

      * Если sum = k, то сдвинуть i вправо, удаляя элементы из подотрезка, пока он не перестанет содержать все числа от 1 до k. Уменьшить cnt[a] на 1 и, если cnt[a] = 0, уменьшить sum на 1.

      * Увеличить j на 1.

  3. Если найден подотрезок, содержащий все числа от 1 до k, то вывести i, иначе вывести -1.

Для примера, если массив a имеет длину n = 4 и k = 3, и его элементы равны 1, 2, 3, 1, то ответ на задачу будет равен 1, так как подотрезок [1, 2, 3] начинается с первого элемента массива. Если же массив a имеет длину n = 4 и k = 3, и его элементы равны 1, 2, 2, 2, то ответ на задачу будет равен -1, так как в массиве нет подотрезка, содержащего все числа от 1 до 3.