Лучший отпуск

В календаре одной страны год состоит из $n$ месяцев, $i$-й месяц длится $d_i$ дней; дни месяца нумеруются от $1$ до $d_i$. Годы идут друг за другом. Вы уходите в отпуск ровно на $x$ дней подряд, и в $j$-й день месяца друг обнимает вас $j$ раз.

Отпуск может начаться в любой день и переходить через конец года в следующий. Какое наибольшее число объятий вы можете получить?

В первой строке $n$ и $x$ ($1 \le n \le 2 \cdot 10^5$, $$). Во второй — целых чисел ().

Одно число — наибольшее число объятий.

Чтобы учесть переход через год, запишите массив месяцев дважды. Лучший отпуск всегда заканчивается в последний день какого-то месяца: иначе сдвиг на день вправо даёт не меньше объятий. Постройте две префиксные суммы — числа дней и числа объятий ($\frac{d(d+1)}{2}$). Для каждого месяца окончания найдите месяц начала двумя указателями или бинарным поиском; из первого месяца берутся только последние дни.

Ответ достигает $2 \cdot 10^{17}$ — нужен 64-битный тип. В первом примере дни , лучший вариант : ответ .