Пары с небольшой суммой

Сколько существует пар элементов с разными номерами, сумма которых не превосходит $S$?

Значения неотрицательны и не превосходят миллиона.

В первой строке $n$ от $1$ до $2 \cdot 10^5$ и $S$ от $0$ до $2 \cdot 10^6$. Во второй — $n$ чисел от $0$ до $10^6$.

Одно число.

Ответ доходит до $2 \cdot 10^{10}$ — только long long. Способов два: массив счётчиков по значениям с подсчётом «сколько чисел меньше данного» или сортировка и два указателя. Оба дают линейное время после сортировки.