Сумерки охватывают леса и весь мир. Реку и лодку освещает луна.— Сложно возможно затмить свет луны. Тени лишь раскрывают ее красоту и мягкость, — пропел Мино.
— Видишь? Облака, — сказал Канно, вглядываясь вдаль.
— Не может быть ничего лучше, — обернулся Мино к Канно.
Представим небо как координатную ось. Луна находится в начале координат, то есть в точке с координатой \(0\).
В небе есть \(n\) облаков. Все облака имеют одинаковую длину \(l\). \(i\)-е облако изначально покрывает отрезок \((x_i, x_i + l)\) (не включая границы). Изначально облако двигается со скоростью \(v_i\), которая равна либо \(1\), либо \(-1\).
Изначально никакие два облака не пересекаются, то есть для всех \(1 \leq i \lt j \leq n\) выполняется \(\lvert x_i - x_j \rvert \geq l\).
Если скорость ветра равна \(w\), то скорость \(i\)-го облака станет равна \(v_i + w\), то есть его координаты будут увеличиваться на \(v_i + w\) за единицу времени. Обратите внимание, ветер может быть достаточно сильным и направления движения облаков могут изменяться.
Помогите Мино, подсчитайте число пар \((i, j)\) (\(i < j\)) таких, что существует такая скорость ветра \(w\), не превышающая \(w_\mathrm{max}\) по модулю (возможно, отрицательная и/или вещественная) такая, что \(i\)-е и \(j\)-е облака в какой-то момент будут оба закрывать луну. Скорость ветра \(w\) может быть различной для различных пар.
Выходные данные
Выведите одно целое число — количество неупорядоченных пар облаков таких, что они могут закрыть луну в один и тот же момент при некотором выборе скорости ветра \(w\).
Примечание
В первом примере начальные позиции и скорости облаков проиллюстрированы на рисунке ниже.
Пары облаков, которые могут одновременно закрыть луну:
- \((1, 3)\) закроют луну в момент времени \(2.5\) при \(w = -0.4\);
- \((1, 4)\) закроют луну в момент времени \(3.5\) при \(w = -0.6\);
- \((1, 5)\) закроют луну в момент времени \(4.5\) при \(w = -0.7\);
- \((2, 5)\) закроют луну в момент времени \(2.5\) при \(w = -2\).
На рисунке ниже приведены положения облаков в момент времени \(2.5\) при скорости ветра \(w = -0.4\). В этот момент \(1\)-е и \(3\)-е облака оба закрывают луну.
Во втором примере только пара \((1, 4)\) закроют луну в момент времени \(15\) при скорости ветра \(w = 0\).
Обратите внимание, что все времена и скорости ветра в примечании даны для примера, на самом деле существует бесконечное число способов выбрать их.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 1 2
-2 1
2 1
3 -1
5 -1
7 -1
|
4
|
|
2
|
4 10 1
-20 1
-10 -1
0 1
10 -1
|
1
|