Малышка R — волшебница, которая любит неубывающие массивы. У нее есть массив длины \(n\), изначально равный \(a_1, \ldots, a_n\), в котором каждый элемент — целое число в диапазоне \([1, m]\). Она хочет, чтобы он стал неубывающим, то есть выполнялось \(a_1 \leq a_2 \leq \ldots \leq a_n\).
Для этого она может проделать несколько фокусов. У малышки R есть фиксированный массив \(b_1\ldots b_m\) длины \(m\). Формально определим фокус как процедуру, которая выполняет следующие действия по порядку:
- Выбрать множество \(S \subseteq \{1, 2, \ldots, n\}\).
- Для каждого \(u \in S\) присвоить \(a_u\) значение \(b_{a_u}\).
Малышка R задается вопросом, сколько нужно сделать фокусов, чтобы исходный массив стал неубывающим. Если это невозможно ни при каком количестве фокусов, выведите вместо этого \(-1\).
Выходные данные
Для каждого набора входных данных выведите одно целое число: минимально необходимое количество фокусов или \(-1\), если невозможно сделать \(a_1, \ldots, a_n\) неубывающим.
Примечание
В первом наборе входных данных изначальный массив \(a_1, \ldots, a_n\) равен \([1, 6, 3, 7, 1]\). Вы можете выбрать \(S\) следующим образом:
- первый фокус: \(S = [2, 4, 5]\), \(a = [1, 1, 3, 5, 2]\);
- второй фокус: \(S = [5]\), \(a = [1, 1, 3, 5, 3]\);
- третий фокус: \(S = [5]\), \(a = [1, 1, 3, 5, 5]\).
Таким образом, с помощью
\(3\) фокусов можно сделать
\(a_1, \ldots, a_n\) неубывающим. Можно показать, что это минимально возможное количество фокусов.
Во втором наборе входных данных невозможно сделать \(a_1, \ldots, a_n\) неубывающим.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5 8
1 6 3 7 1
2 3 5 8 7 1 5 6
3 3
1 3 2
2 1 3
10 10
2 8 5 4 8 4 1 5 10 10
6 7 2 6 3 4 1 1 3 5
|
3
-1
3
|