Дуэты для арены: не перегрузи сервер

В игре открыли «арену дуэтов». Игроки заходят парами, но у сервера есть лимит: если сумма сил двух игроков в паре больше L, сервер перегружается и такая пара не допускается.

Каждый игрок может попасть на арену не более одного раза. Хочется пустить на арену как можно больше дуэтов.

Посчитайте максимальное число допустимых дуэтов.

Формат ввода

Первая строка: два целых числа n и L — число игроков и лимит сервера. Вторая строка: n целых чисел a1, a2, ..., an — силы игроков.

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

Выведите одно целое число — максимальное количество дуэтов.

Ограничения

• 1 ≤ n ≤ 50000
• 1 ≤ L ≤ 2 000 000
• 1 ≤ ai ≤ 1 000 000

Пример

Ввод:

6 10
1 2 3 7 8 9

Вывод:

3

Ключевое наблюдение: чтобы сделать максимум пар с ограничением по сумме, сильных игроков «опасно» тратить на средних — лучше пытаться пристроить каждого сильного к самому слабому, который ещё подходит. Если даже с самым слабым сильный не проходит по лимиту, то он не пройдёт ни с кем (все остальные только сильнее), значит его можно смело исключить.

Приём: жадность с двумя указателями после сортировки. Это работает, потому что выбор для самого сильного игрока максимально ограничен: либо он идёт в пару с самым слабым (если помещаются), либо не идёт вообще. Любая другая попытка «спасти» сильного только ухудшит шансы слабых собрать пары.

План:

• Отсортировать массив сил по возрастанию.
• Поставить i на начало (самый слабый), j на конец (самый сильный), ответ = 0.
• Пока i < j:
• Если a[i] + a[j] <= L, засчитываем дуэт, делаем i += 1, j -= 1.
• Иначе пара с j невозможна ни с кем, уменьшаем j -= 1.
• Вывести ответ.

Сложность: сортировка O(n log n), проход двумя указателями O(n), памяти O(1) кроме массива.

Частая ошибка: при a[i] + a[j] > L двигать i (теряя слабого зря). Нужно двигать j, потому что проблема в слишком сильном игроке.