Пары очков в аркаде

В аркадной игре в конце раунда выпадает список призовых очков. Игрок получает бонус за каждую пару разных выпадений (то есть за каждую пару индексов i<j), у которых сумма очков ровно равна числу S.

Список уже отсортирован по неубыванию.

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

Формат ввода

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

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

Выведите одно целое число — сколько существует пар индексов (i, j), где 1 ≤ i < j ≤ n и ai + aj = S.

Ограничения

• 2 ≤ n ≤ 20000
• 1 ≤ ai ≤ 1 000 000
• 1 ≤ S ≤ 10^18
• a1 ≤ a2 ≤ ... ≤ an

Пример

Ввод:

6 8
1 2 3 5 5 7

Вывод:

3

Ключевое наблюдение: массив отсортирован, значит если взять левый элемент a[l] и правый a[r], то сумма a[l]+a[r] монотонно меняется при сдвиге указателей. Поэтому можно искать пары без перебора всех i<j.

Приём «два указателя» работает так: держим l=0, r=n-1. Сравниваем s=a[l]+a[r] с S и двигаем тот конец, который может приблизить сумму к S.

Важно про повторы: если s==S, то пар может быть сразу много из-за одинаковых значений слева/справа. Их нужно посчитать пачкой.

План:

• Поставить l на начало, r на конец, ans=0.
• Пока l<r:
• s=a[l]+a[r].
• Если s<S, увеличить l (нужно больше).
• Если s>S, уменьшить r (нужно меньше).
• Иначе s==S:
• Если a[l]==a[r], то все элементы между ними равны, добавляем число пар k*(k-1)//2, где k=r-l+1, и заканчиваем.
• Иначе посчитать, сколько раз повторяется a[l] подряд (cl) и сколько раз повторяется a[r] подряд (cr), сдвинуть l и r за эти группы и прибавить cl*cr.

Сложность по времени: O(n), потому что каждый указатель движется только вперёд/назад. Память O(1).

Частая ошибка: при s==S увеличить/уменьшить указатели только на 1 и забыть про повторы — тогда ответ будет занижен, а иногда и будет O(n^2) на длинных группах.