Тройной перекус

В школьном буфете есть *n* видов перекусов. У каждого вида есть «вес» (например, калории). Ты хочешь взять ровно три разных по позиции в списке перекуса так, чтобы суммарный вес оказался строго меньше лимита *S*.

Посчитай, сколькими способами это можно сделать (тройка считается по индексам: если в списке встречаются одинаковые числа, то выбор разных позиций — разные способы).

Важно: ответ может быть больше, чем помещается в 32-битный тип (как на олимпиадах). В Python это не проблема, но в других языках нужен 64-битный тип.

Формат ввода

В первой строке два целых числа n и S. Во второй строке n целых чисел a1, a2, ..., an — веса перекусов.

Формат вывода

Выведи одно целое число — количество троек индексов i < j < k, для которых ai + aj + ak < S.

Ограничения

• 1 ≤ n ≤ 2000
• 1 ≤ S ≤ 10^9
• 0 ≤ ai ≤ 100000

Пример

Ввод:

5 10
1 2 3 4 5

Вывод:

6

Ключевое наблюдение: если массив отсортировать, то при фиксированных i и j сумма a[i] + a[j] + a[k] монотонно растёт по k. Значит, можно не перебирать третий индекс полностью, а двигать правый указатель влево и считать пачками.

Приём: сортировка + два указателя. Для каждого i ставим l = i+1, r = n-1 и сдвигаем их так, чтобы за O(n) обработать все пары (l, r).

План:

• Отсортируй массив a.
• Заведи ans = 0.
• Для каждого i от 0 до n-3:
• l = i+1, r = n-1.
• Пока l < r:
• Если a[i] + a[l] + a[r] < S, то подходят все k из диапазона (l, r] (потому что при меньшем k сумма только меньше).

Добавь ans += (r - l) и сдвинь l += 1.

• Иначе сумма слишком большая — уменьшаем её: r -= 1.
• Выведи ans.

Мини-сниппет подсчёта: ans += (r - l).

Сложность: сортировка O(n log n), основной цикл O(n^2) (при n=2000 нормально).

Частая ошибка: прибавлять 1 вместо (r - l) (тогда получится медленный/неверный подсчёт) или перепутать строгость: нужно именно < S, не <=.