Дается непустой нуль-индексированный массив A, состоящий из N целых чисел. Первый префикс покрытия массива A представляет собой наименьшее целое число P такое, что $ 0 \ leq P <N $ и такое, что каждое значение, которое встречается в массиве A, также встречается в последовательности $ A [0], A [1], \ ldots, A [P] $.
Например, первый префикс покрытия массива A такой, что
A[0]=2 A[1]=2 A[2]=1 A[3]=0 A[4]=1 3, поскольку последовательность A[0], A[1], A[2], A[3] равная 2, 2, 1, 0 содержит все значения, которые встречаются в массиве A.
Напишите функцию
int ps(int[] A);
что при нулевом индексированном непустом массиве A, состоящем из N целых чисел, возвращается первый префикс покрытия A. Предположим, что $N <= 1,000,000$ . Предположим, что каждый элемент в массиве является целым числом в диапазоне [0..N-1] .
Например, данный массив A такой, что A[0]=2 A[1]=2 A[2]=1 A[3]=0 A[4]=1
функция должна возвращать 3, как описано в примере выше.