Codeforces Round 942 (Div. 1) |
---|
Закончено |
Малышка 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$$$. Формально определим фокус как процедуру, которая выполняет следующие действия по порядку:
Малышка R задается вопросом, сколько нужно сделать фокусов, чтобы исходный массив стал неубывающим. Если это невозможно ни при каком количестве фокусов, выведите вместо этого $$$-1$$$.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1\le t\le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1\leq n \leq 10^6$$$, $$$1 \leq m \leq 10^6$$$) — длину исходного массива и диапазон элементов в массиве.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq m$$$) — изначальный массив.
Третья строка каждого набора входных данных содержит $$$m$$$ целых чисел $$$b_1, \ldots, b_m$$$ ($$$1 \leq b_i \leq m$$$) — фиксированный магический массив.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$, и сумма $$$m$$$ по всем наборам входных данных не превосходит $$$10^6$$$.
Для каждого набора входных данных выведите одно целое число: минимально необходимое количество фокусов или $$$-1$$$, если невозможно сделать $$$a_1, \ldots, a_n$$$ неубывающим.
35 81 6 3 7 12 3 5 8 7 1 5 63 31 3 22 1 310 102 8 5 4 8 4 1 5 10 106 7 2 6 3 4 1 1 3 5
3 -1 3
В первом наборе входных данных изначальный массив $$$a_1, \ldots, a_n$$$ равен $$$[1, 6, 3, 7, 1]$$$. Вы можете выбрать $$$S$$$ следующим образом:
Во втором наборе входных данных невозможно сделать $$$a_1, \ldots, a_n$$$ неубывающим.
Название |
---|