Along a straight road where autonomous truck tests are taking place, there are $n$ cities, with the $i$-th city located at coordinate $i$. In the $i$-th city, an antenna with power $a_i$ is installed, covering all cities from $L_i = \max(1, i - a_i)$ to $R_i = \min(n, i + a_i)$ inclusive.
An autonomous truck travels along the road from city $s$ to city $t$, where $s < t$. In each city along the route, the truck is connected to one of the antennas. The connection to the antennas occurs as follows:
- In the starting city, the truck connects to an antenna covering this city that has the maximum $R_i$ value. If there are several such antennas, any one of them is chosen.
- After the truck moves from city $v$ to city $v + 1$, if the antenna to which it was connected in city $v$ also covers city $v + 1$, the truck remains connected to this antenna. Otherwise, if the antenna to which it was connected does not cover city $v + 1$, the truck reconnects to an antenna covering city $v + 1$ that has the maximum $R_i$ value. If there are several such antennas, any one of them is chosen.
Let $f(s, t)$ be the number of reconnections between antennas for a truck that starts its route in city $s$ and ends its route in city $t$ ($s < t$). The initial connection to an antenna in city $s$ is not counted as a reconnection.
The instability of the road coverage by antennas is defined as the sum of $f(s, t)$ values over all valid pairs of cities, that is, the value $$F = \sum_{s=1}^{n-1} \sum_{t=s+1}^{n} f(s, t).$$
The road operator has one spare antenna with power $x$. To reduce the coverage instability, one of the existing antennas can be replaced with the spare one. It is required to determine the minimum value of the road coverage instability $F$ if at most one antenna is replaced with the spare antenna of power $x$.
Input
The first line contains two integers $n$ and $x$ ($1 \le n \le 10^6$, $0 \le x \le n$) — the number of cities and the power of the spare antenna.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le n$) — the powers of the antennas.
Output
Output the minimum possible value of the road coverage instability if at most one antenna can be replaced with the spare antenna of power $x$.
Subtasks
| Subtask | Points | Constraints | Required Subtasks |
|---|---|---|---|
| 1 | 7 | $n \le 100$ | |
| 2 | 8 | $n \le 500$ | 1 |
| 3 | 6 | $n \le 5000$ | 1, 2 |
| 4 | 12 | $x = 0$ | |
| 5 | 5 | $a_i = 0$ | |
| 6 | 16 | $a_i \le 1$ | 5 |
| 7 | 14 | $a_i \ge \frac{n}{20}$ | |
| 8 | 32 | 1–7 |
Examples
Input 1
3 1 1 0 0
Output 1
0
Input 2
5 0 2 1 0 0 1
Output 2
6
Note
In the first example, we can replace the second antenna with the spare one. Then, a truck starting at any point will connect to it, and no truck will need to reconnect.
In the second example, there is no need to use the spare antenna. Trucks starting in one of the first three cities and finishing in one of the last two cities will have to reconnect once to the last antenna, so the road coverage instability is 6.