Background

kls is very good at “poisoning milk” (du nai).

Problem Description

There are $n$ OI contestants, and each of them set up a flag. One day, for some reason, all the flags were triggered, so there is a row of $n$ bamboo poles on the ground. The distance between adjacent poles is $1$ unit, and their heights are in $1 \sim m$.

When kls saw these bamboo poles, he felt they did not look nice, so he plans to knock all of them down.

Before doing that, kls thought of a math problem. Each bamboo pole can fall to the left or to the right. If, after choosing their falling directions, the top ends of two bamboo poles can coincide, then we call this pair excellent. Now kls wants to know how many pairs of bamboo poles are excellent.

Input Format

The first line contains two integers $n, m$, representing the number of bamboo poles and the maximum height.

The second line contains $n$ positive integers, representing the height of each bamboo pole.

Output Format

Output one line with a single integer, representing how many pairs of bamboo poles are excellent.

5 5
2 3 3 3 2

3

Hint

Sample Explanation

• Poles $1$ and $2$ can have their top ends coincide if they both fall to the left.
• Poles $4$ and $5$ can have their top ends coincide if they both fall to the right.
• Pole $1$ falling to the right and pole $5$ falling to the left can have their top ends coincide.

Constraints

For $30\%$ of the testdata, $n \le 2000$, $m \le 5000$.

For $60\%$ of the testdata, $n \le 200000$, $m \le 500000$.

For $100\%$ of the testdata, $n \le 200000$, $m \le 10^9$.

Translated by ChatGPT 5