Робот Валл-І влаштувався на нову роботу в невеличкий склад, що обслуговує компанію Замало. Склад вже давно повністю автоматизований, тож на ньому працює лише 1 робот. На складі є всього полиць, які занумеровані цілими числами від 1 до . Всі полиці розташовані по одну сторону від доріжки, по якій рухається наш робот. Полиці не обов'язково розташовані в порядку зростання від початку доріжки.
Робот Валл-І має два контейнери: робочий та прокрастиначий. Спочатку в робочому контейнері Валл-І знаходиться рівно коробок, кожну з яких потрібно покласти на одну з полиць. На кожній коробці написаний номер, який означає на яку полицю потрібно її покласти. Кожного дня, коли робот починає працювати і йти повз полиці, він отримує в свій робочий контейнер коробки відсортовані в порядку зростання номерів, що на них написані. Робот може брати для обробки лише ту коробку, яка знаходиться вгорі робочого контейнера.
Робот починає маршрут з полиці, яка розташована на початку доріжки. Зупиняючись біля кожної полиці, робот дивиться на номер полиці. Далі він або проходить мимо, або відкладає певну кількість коробок в прокрастиначий контейнер і якщо вгорі залишається коробка, яку потрібно поставити на цю полицю, то він її ставить і йде далі. Валл-І не може брати коробки з прокрастиначного контейнера.
Наприклад, якщо Валл-І підійшов до полиці з номером 5, а верхню коробку потрібно поставити на полицю з номером 2, то він або прибирає в прокрастиначий контейнер коробки 2, 3 та 4 і викладає коробку 5 на полицю, або проходить до наступної полиці. За один день Валл-І проходить по доріжці разів, тому коли він доходить до її кінця, він розвертається і йде в зворотньому напрямку, продовжуючи розставляти коробки.
Програмне забезпечення Валл-І вже застаріле, він не здатен розставити коробки оптимально. Тому ми просимо вас оновити його програмне забезпечення, тобто обрахувати яку максимальну кількість коробок теоретично може розставити Валл-І за 1 робочий день.
В першому рядку вхідних даних знаходяться 2 числа та (1 \le N \le 10^5, 1 \le K \le 100) – кількість полиць на складі (кількість коробок в робочому контейнері відповідно) і кількість проходів робота за 1 день. В другому рядку вхідних даних знаходиться перестановка з цілих чисел – номера полиць в порядку від початку до кінця доріжки.
В єдиному рядку вихідних даних має бути єдине ціле число – максимальна кількість коробок, яку зможе розставити Валл-І за 1 робочий день.
Example 1
Example 2
Перший приклад. За один прохід Валл-І може розставити не більше 3 коробок – покласти коробки 1, 2, 4 або ж 1, 3, 4.
Другий приклад. За три проходи по доріжці Валл-І може розкласти 5 коробок. Рухаючись перший раз від початку до кінця він розставить 1, 3, 4, в зворотньому порядку коробку 5, і третій раз, рухаючись зліва, коробку 6.
Ця задача складається з трьох підзадач. Для підзадач виконуються додаткові обмеження, вказані в таблиці. Бали за підзадачу будуть нараховані лише за умови проходження усіх тестів підзадачі.
№ підзадачі | Бали | Обмеження | Примітка |
0 | 0 | Тести з умови | |
1 | 27 | K = 1; N \le 1000 | |
2 | 31 | K \le 10; 1 \le N \le 10000 | |
3 | 42 | K \le 100; 1 \le N \le 10000 |