Air Currents

Kolobok left his grandmother and set off to travel. By accident he wandered into the land of Ivenland. His first trouble was a huge moat of water in front of the entrance, and that water is known to be bad for our hero. Fortunately, air currents are placed all around, and each one lifts whoever stands on it to a certain height. Since the country is called Ivenland, every height an air current can lift the hero to is an even number.

Let the air currents be an array $h[1..n]$ of $n$ positive integers, the heights of the currents. For each $1 \le i \le n$, let $G[i]$ be the index of the nearest element to the left of $i$ that is strictly greater than $h[i]$. Formally, $G[i] = \max\{j \mid j < i \text{ and } h[j] > h[i]\}$. If $i = 1$ or no element to the left of $i$ is greater than $h[i]$, then $G[i] = 0$.

Kolobok measures the layout by $S(h) = \sum_{i=1}^n (i - G[i])$. The smaller the sum, the better the layout. The only thing Kolobok can do is raise the height of one air current by at most $m$. The height must remain an integer after the change, but it may become odd if needed.

Help Kolobok make the change that makes $S(h)$ as small as possible.

The first line contains $n$ and $m$ ($1 \le n \le 10^5$, $1 \le m \le 10^9$), the number of air currents and the maximum amount by which one of them can be raised. The second line contains the heights $h[i]$ ($1 \le h[i] \le 10^9$). All heights are guaranteed to be even.

Print one integer, the minimum possible value of the sum.

In the first example, raising the first element by 3 to make it 7 is beneficial. Then $h = [7, 2, 6]$, $G[1] = 0$, $G[2] = 1$, and $G[3] = 1$, so $S(h) = (1 - 0) + (2 - 1) + (3 - 1) = 1 + 1 + 2 = 4$. No change can give $S(h) < 4$.

In the second example, $m = 2$, so the first element cannot be raised that much. After any action, $S(h)$ is 5 or 6. Raising the first element by 1 gives $[5, 2, 6]$, where $S(h) = 5$.