The best vacation

In one country's calendar a year has $n$ months, month $i$ lasts $d_i$ days, and the days of a month are numbered from $1$ to $d_i$. Years follow one another. You take a vacation of exactly $x$ consecutive days, and on day $j$ of a month your friend hugs you $j$ times.

The vacation may start on any day and continue past the end of the year into the next one. What is the maximum number of hugs you can get?

The first line contains $n$ and $x$ ($1 \le n \le 2 \cdot 10^5$, $1 \le x \le d_1 + \ldots + d_n$). The second line contains $n$ integers $d_i$ ($1 \le d_i \le 10^6$).

A single number — the maximum number of hugs.

To handle the wrap-around, write the months twice. The best vacation always ends on the last day of some month: otherwise shifting it one day to the right gives at least as many hugs. Build two prefix sums — of days and of hugs ($\frac{d(d+1)}{2}$). For every ending month find the starting month with two pointers or binary search; only the last days of the first month are taken.

The answer reaches $2 \cdot 10^{17}$ — a 64-bit type is needed. In the first example the days are 1 1 2 3 1, and the best choice is 2 3: the answer is $5$.

Source: Codeforces, problem 1358D.