G. Slot Machines
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Due to the rapid development of humanity in the space sphere, the fairy tales that parents tell their children have become distorted. They have ceased to be interesting or funny and have turned into computer science problems. For example, Martian children are told the following problem at night.

Once upon a time, there were three friends — Sasha, Kirill, and Yuri. At some point, they ran out of money. Therefore, they decided to build a casino and started to come up with rules:

  • Sasha: — There will be $$$a$$$ stones in the slot machine, and you can take any number of stones from $$$1$$$ to $$$k$$$ in one move;
  • Kirill: — If someone takes the same number of stones from the machine as the previous person, they lose.
  • Yuri: — There will be $$$n$$$ slot machines, and the $$$i$$$-th one will contain $$$a_i$$$ stones.

Playing the same game all the time is boring, and there is no element of randomness. Therefore, the friends decided to clarify the rules:

  • Sasha: — When a player enters, a pair of random numbers $$$(l,r)$$$ ($$$1 \le l \le r \le n$$$) is generated for them. In one move, you can take stones from any machine with a number $$$i$$$ such that $$$l \le i \le r$$$.
  • Kirill: — Specially trained staff play with the player, taking turns to make moves, with the player making the first move.
  • Yuri: — The player loses if they cannot make any moves according to the rules of the game, in which case they give their apartment to the casino owners.

The friends also decided to assess the profitability of their scheme, but they couldn't manage it. Therefore, they ask you to help them calculate the number of pairs $$$(l, r)$$$, for which the casino wins the game.

Input

The first line contains the numbers $$$n$$$ and $$$k$$$ — the number of slot machines and the maximum number of stones that can be taken in one move.

The second line contains the numbers $$$a_1, \ldots, a_n$$$ — the initial number of stones in each of the machines.

$$$$$$1 \le n \le 1\,000\,000$$$$$$ $$$$$$2 \le k \le 100$$$$$$ $$$$$$1 \le a_i \le 10^{18}$$$$$$

Output

Output a single number — the answer to the problem.

Examples
Input
3 2
1 2 3
Output
3
Input
2 10
308 693
Output
3
Note

Consider the first example:

  • $$$(l,r)=(1,1)$$$. The player wins, as they can take all the stones in the first move.
  • $$$(l,r)=(2,2)$$$. The player wins, as they can take all the stones in the first move.
  • $$$(l,r)=(3,3)$$$. The casino wins. Let the player take $$$x$$$ stones on the first move, then the casino will take $$$3-x$$$.
  • $$$(l,r)=(1,2)$$$. The casino wins. Note that you can only take stones from a pile of size $$$2$$$ once (if you take only $$$1$$$ stone, you cannot take another one ever, as it would be a repeat move). Therefore, the player will always run out in two moves.
  • $$$(l,r)=(2,3)$$$. The player wins, as in the first move they can take all the stones from the second pile.
  • $$$(l,r)=(1,3)$$$. The casino wins, as they have a strategy for counter moves:
    • If the player takes stones from the first pile, the casino takes stones from the second, and vice versa.
    • If the player takes $$$x$$$ stones from the third pile, the casino takes $$$3-x$$$ stones from the same pile.

Out of all possible pairs $$$(l, r)$$$, $$$3$$$ pairs $$$(3,3)$$$, $$$(1,2)$$$, $$$(1,3)$$$ are suitable for us, so the answer is $$$3$$$.