시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 5 | 2 | 2 | 50.000% |
Пете подарили на день рождения новую карточную игру <<Салют>>. Эта игра предназначена для одного человека. В комплект игры входит колода, состоящая из $n$ карт. На каждой карте написано целое число от 1 до $m$.
Игра происходит следующим образом. Колода карт перемешивается, и игрок берет в руку верхние $k$ карт из колоды. В каждый момент времени игрок может держать в руке не более $k$ карт. Есть три различных вида хода.
Игра заканчивается, когда нельзя сделать ни одного из вышеперечисленных ходов. Цель игры состоит в том, чтобы выложить на стол как можно больше карт.
Петя подсмотрел, в каком порядке лежат карты в колоде, и теперь хочет сделать ходы так, чтобы максимизировать число выложенных карт. Помогите ему выяснить, какое максимальное число карт ему удастся выложить.
Входной файл содержит несколько тестовых примеров. В первой строке находится целое число $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$.
Для каждого тестового примера в отдельной строке выведите единственное целое число --- максимальное число карт, которое можно выложить.
3 4 3 1 3 2 1 2 1 2 1 2 5 5 2 4 2 1 4 3
2 0 4
В третьем примере следует играть следующим образом. Исходно у Пети в руках 4 и 2. Петя сбрасывает 4, берет из колоды 1. Теперь у него в руках 2 и 1. Петя выкладывает 1, затем 2. Теперь у него в руке нет карт. Он берет из колоды 4, затем берет из колоды 3. Теперь у него в руке 4 и 3, он выкладывает 3 и затем выкладывает 4.