공기 흐름

콜로복은 할머니 곁을 떠나 여행을 다니다가 뜻밖에도 이벤랜드라는 나라에 들어가게 되었다. 나라 입구 앞에는 커다란 물 도랑이 있는데, 이 물은 주인공에게 좋지 않은 것으로 알려져 있다. 다행히 곳곳에 기류가 있어서, 그 위에 올라서는 사람을 일정한 높이만큼 들어 올린다. 나라 이름이 이벤랜드인 만큼, 기류가 들어 올릴 수 있는 높이는 모두 짝수다.

기류의 높이를 길이 $n$의 배열 $h[1..n]$으로 나타낸다. 배열의 원소는 자연수다. 각 $1 \le i \le n$에 대해 $G[i]$는 $i$의 왼쪽에서 $h[i]$보다 엄격하게 큰 원소 중 가장 가까운 원소의 인덱스다. 식으로 쓰면 $G[i] = \max\{j \mid j < i \text{ 이고 } h[j] > h[i]\}$이다. $i = 1$이거나 왼쪽에 $h[i]$보다 큰 원소가 없으면 $G[i] = 0$이다.

콜로복은 배치의 좋고 나쁨을 $S(h) = \sum_{i=1}^n (i - G[i])$로 잰다. 합이 작을수록 배치가 좋다. 콜로복이 할 수 있는 일은 기류 하나의 높이를 최대 $m$만큼 올리는 것뿐이다. 변경 후에도 높이는 정수여야 하며, 필요하다면 홀수가 될 수도 있다.

콜로복이 $S(h)$를 최소로 만들 수 있도록 최적의 변경을 찾아 주자.

첫 줄에 $n$과 $m$이 주어진다 ($1 \le n \le 10^5$, $1 \le m \le 10^9$). $n$은 기류의 개수이고, $m$은 그중 하나의 높이를 올릴 수 있는 최댓값이다. 둘째 줄에 기류의 높이 $h[i]$ ($1 \le h[i] \le 10^9$)가 주어진다. 모든 높이는 짝수임이 보장된다.

$S(h)$의 최솟값을 정수 하나로 출력한다.

첫 번째 예제에서는 첫 원소를 3만큼 올려 7로 만드는 것이 유리하다. 그러면 $h = [7, 2, 6]$이고 $G[1] = 0$, $G[2] = 1$, $G[3] = 1$이므로 $S(h) = (1 - 0) + (2 - 1) + (3 - 1) = 1 + 1 + 2 = 4$이다. 어떤 변경으로도 $S(h) < 4$를 만들 수 없다.

두 번째 예제에서는 $m = 2$이므로 첫 원소를 그만큼 올릴 수 없다. 어떤 행동을 하든 $S(h)$는 5 또는 6이 된다. 첫 원소를 1만큼 올려 $[5, 2, 6]$을 만들면 $S(h) = 5$가 된다.