Сходи

У чарівному замку є цікаві сходи – від вхідних дверей вони йдуть угору, потім вниз і знову вгору і вниз, і ще, і ще ... Кожна сходинка має свою висоту, але ширина сходинок однакова. Якщо по обидва боки від нижньої сходинки є сходинки однакової висоти, можна покласти дошку горизонтально, пройти по ній і не спускатися на нижню сходинку.

Леді в замку поставила дошку відповідної довжини, щоб з’єднати пари сходинок там, де були дві сходинки однакової висоти, але між якими не було сходинок, вищих за ці дві сходинки, і між якими не було сходинок однакової висоти, цим двом сходинкам. Якщо є дві сусідні сходинки однакової висоти, також поставила дошку для цієї пари сходинок. На кожну сходинку можна розмістити щонайбільше одну-дві дошки. Якщо розміщено дві дошки, то одна з них повинна з’єднатися сходинкою вліво, а друга – вправо.

Так стало багато дошок і деякі з яких можуть бути під іншими дошками. З міркувань безпеки Леді вирішила зняти мінімальну кількість дошок із тих, що вже були на місці, щоб ті, що залишилися, не мали жодної, яка була б одна під одною.

Напишіть програму, яка знаходить, скільки дошок поставила Леді та скільки вона потім прибрала.

Input

У першому рядку міститься число N (3 < N ≤ 100 000) – кількість сходинок і q (q є цілим числом, що дорівнює 1 або 2) - тип запиту до вашої програми. Другий рядок містить N цілих чисел – висоти сходинок відповідно до розташування сходинок зліва направо. Висота кожної сходинки є натуральним числом, меншим за 101.

Output

Виведіть одне ціле число відповідно до типу запиту: для q=1 потрібно вивести кількість усіх дошок, які спочатку розмістила Леді, а для q=2 — мінімальну кількість дошок, які потрібно прибрати.

Examples

Note

Спочатку Леді розмістили 6 дошок, що з’єднують пари сходів під номерами 1-7, 2-4, 4-6, 7-8, 8-11 і 9-10.

Мінімальна кількість дошок для видалення — 2, і це можуть бути дошки 1-7 і 8-11, або іншим можливим рішенням є видалення дошок 1-7 і 9-10.