Задача №113291. Игра
Пете подарили на день рождения новую карточную игру «Салют». Эта игра предназначена для одного человека. В комплект игры входит колода, состоящая из n карт. На каждой карте написано целое число от 1 до \(m\).
Игра происходит следующим образом. Колода карт перемешивается, и игрок берет в руку верхние \(k\) карт из колоды. В каждый момент времени игрок может держать в руке не более \(k\) карт. Есть три различных вида хода.
- Сбросить любую карту, находящуюся в руке. Сброшенная карта отправляется в снос и не может быть далее использована в игре.
- Если в колоде еще есть карты, то взять в руку верхнюю карту колоды. Такой ход можно сделать только, если в руке у игрока строго меньше, чем \(k\) карт.
- Выложить карту из руки на стол. Карту с числом \(x\) можно выложить в том случае, если игрок до этого уже выложил на стол карты с числами 1, 2, \(\dots\) , \(x−1\), но еще не выложил карту с числом \(x\).
Петя подсмотрел, в каком порядке лежат карты в колоде, и теперь хочет сделать ходы так, чтобы максимизировать число выложенных карт. Помогите ему выяснить, какое максимальное число карт ему удастся выложить.
Входной файл содержит несколько тестовых примеров. В первой строке находится целое число T — количество тестовых примеров (\(1 \le T \le 10^5 \)). Следующие \(2T\) строк содержат описание тестовых примеров.
Описание каждого тестового примера состоит из двух строк. В первой строке находятся целые числа \(n\), \(m\) и \(k\) — количество карт в колоде, максимальное число, которое может быть написано на карте, и максимальное количество карт в руке (\(1 \le n, m \le 10^5 , 1 \le k \le n\)).
Во второй строке находятся n целых чисел \(a_i\) — числа, написанные на картах, в том порядке, в котором они лежат в колоде, начиная с самой верхней карты (\(1 \le a_i \le m\)).
Сумма \(n\) во всех тестовых примерах не превосходит \(10^5\) .
Для каждого тестового примера в отдельной строке выведите единственное целое число - максимальное число карт, которое можно выложить.
В третьем примере следует играть следующим образом. Исходно у Пети в руках 4 и 2. Петя сбрасывает 4, берет из колоды 1. Теперь у него в руках 2 и 1. Петя выкладывает 1, затем 2. Теперь у него в руке нет карт. Он берет из колоды 4, затем берет из колоды 3. Теперь у него в руке 4 и 3, он выкладывает 3 и затем выкладывает 4.
3 4 3 1 3 2 1 2 1 2 1 2 5 5 2 4 2 1 4 3
2 0 4