Сходи#11383
У чарівному замку є цікаві сходи – від вхідних дверей вони йдуть угору, потім вниз і знову вгору і вниз, і ще, і ще ... Кожна сходинка має свою висоту, але ширина сходинок однакова. Якщо по обидва боки від нижньої сходинки є сходинки однакової висоти, можна покласти дошку горизонтально, пройти по ній і не спускатися на нижню сходинку.
Леді в замку поставила дошку відповідної довжини, щоб з'єднати пари сходинок там, де були дві сходинки однакової висоти, але між якими не було сходинок, вищих за ці дві сходинки, і між якими не було сходинок такої самої висоти, як ці дві. Якщо є дві сусідні сходинки однакової висоти, вона також поставила дошку для цієї пари сходинок. На кожну сходинку можна розмістити щонайбільше одну або дві дошки. Якщо розміщено дві дошки, то одна з них повинна з'єднувати зі сходинкою зліва, а друга – справа.
Так стало багато дошок, деякі з яких можуть бути під іншими дошками. З міркувань безпеки Леді вирішила зняти мінімальну кількість дошок із тих, що вже були на місці, щоб жодна з тих, що залишилися, не була під іншою.
Напишіть програму, яка знаходить, скільки дошок поставила Леді та скільки вона потім прибрала.
У першому рядку міститься число (3 < N \leq 100000) – кількість сходинок і ( є цілим числом, що дорівнює або ) - тип запиту до вашої програми. Другий рядок містить цілих чисел – висоти сходинок відповідно до розташування сходинок зліва направо. Висота кожної сходинки є натуральним числом, меншим за .
Виведіть одне ціле число відповідно до типу запиту: для q=1 потрібно вивести кількість усіх дошок, які спочатку розмістила Леді, а для q=2 — мінімальну кількість дошок, які потрібно прибрати.
Приклад 1
Спочатку Леді розмістила дошок, що з'єднують пари сходинок під номерами -, -, -, -, - і -.
Мінімальна кількість дошок для видалення — , і це можуть бути дошки - і -, або іншим можливим рішенням є видалення дошок - і -.