Loved, Not Loved#12343
Given an array of length .
We can perform the following two operations on the array:
Choose any index 1 \leq i \leq n, such that a_i > 0, and subtract one from it.
Choose any index 1 \leq i \leq n, such that a_i > 0, and for all , such that i \leq j \leq n and a_j>0, subtract (in other words, subtract from all numbers starting from the chosen to the end of the list, if these numbers are not already equal to ).
We perform these operations until there exists an index 1 \le i \le n, such that a_i > 0. That is, we stop when there are no numbers left in the list that are not equal to .
We consider ourselves loved if we performed an odd number of operations to make all numbers of array equal to .
You need to determine whether it is possible to make us loved, and if so, what is the minimum number of operations needed.
The first line contains an integer (1 \le n \le 10^6) — the length of the array .
The second line contains integers a_1, a_2, \dots, a_n (1 \le a_i \le 10^9) — the array .
Output in the first line «YES», if it is possible, or «NO», if it is not possible.
If the answer is «YES», in the second line output the minimum number of operations.
Example 1
In the example, can be removed times from the entire array, and then more times on the suffix of the last four elements.
The problem will have tests (excluding examples), each worth points.