Люблять, не люблять#12343

Люблять, не люблять

1 секунда

256 мегабайтів

Складна

Дано масив $a$ довжиною $n$ .

Ми можемо виконати наступні дві операції з масивом:

Вибрати будь-який індекс $1 \leq i \leq n$ 1 \leq i \leq n, такий що $a_{i} > 0$ a_i > 0, та відняти від нього одиничку.
Вибрати будь-який індекс $1 \leq i \leq n$ 1 \leq i \leq n, такий що $a_{i} > 0$ a_i > 0, та для всіх $j$ , таких що $i \leq j \leq n$ i \leq j \leq n та $a_{j} > 0$ a_j>0, відняти $1$ (іншими словами, відняти $1$ від усіх чисел, починаючи з вибраного $i$ до самого кінця списку, якщо ці числа ще не дорівнюють $0$ ).

Ми застосовуємо ці операції до тих пір, поки існує індекс $1 \leq i \leq n$ 1 \le i \le n, такий що $a_{i} > 0$ a_i > 0. Тобто припиняємо, коли у списку не залишиться жодного числа, що не дорівнює $0$ .

Вважаємо, що нас люблять, якщо ми зробили непарну кількість операцій, щоб всі числа масиву $a$ стали рівними $0$ .

Потрібно сказати, чи можливо зробити так, щоб нас любили, та якщо це можливо, то яка мінімальна кількість операцій нам для цього знадобиться.

Вхідні дані

Перший рядок містить одне ціле число $n$ $(1 \leq n \leq 1 0^{6})$ (1 \le n \le 10^6) — довжина масиву $a$ .

Другий рядок містить $n$ цілих чисел $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \dots, a_n $(1 \leq a_{i} \leq 1 0^{9})$ (1 \le a_i \le 10^9) — масив $a$ .

Вихідні дані

Виведіть у першому рядку «YES», якщо це можливо, або «NO», якщо неможливо.

Якщо відповідь «YES», у другому рядку потрібно вивести мінімальну кількість операцій.

Приклади

Приклад 1

Примітка

У прикладі можна $12$ разів видалити $1$ з усього масиву, а потім ще $5$ разів на суфіксі останніх чотирьох елементів.

Оцінювання

В задачі буде $20$ тестів(крім прикладів), кожен з яких буде оцінюватися у $5$ балів.