Самое большое пастбище Фермера Джона может быть рассмотрено как большая
2D-решётка из квадратных ячеек (как большая шахматная доска). В настоящий
момент \(N\) коров занимают некоторые из этих ячеек (\(1 \leq N \leq 2500\)).
ФД хочет построить изгородь, которая окружит прямоугольный регион ячеек
Стороны этого прямоугольника должны быть параллельны осям координат, и он может
быть мал, вплоть до одной ячейки. Помогите ФД посчитать количество различных
подмножеств коров, которые он может окружить таким регионом. Заметим, что
пустое подмножество должно быть рассмотрено как одно из таких подмножеств.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит одно целое число
\(N\). Каждая из последующих
\(N\) строк
содержит два разделённых пробелом целых числа - указывающих
\((x,y)\)-координаты ячейки,
в которой находится соответствующая корова. Все
\(x\) координаты различны. Все
\(y\)
координаты различны. Все
\(x\) и
\(y\) лежат в интервале
\(0 \ldots 10^9\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Количество подмножеств коров, которые ФД может огородить. Можно доказать,
что это количество поместиться в 64-битное знаковое (например, long long в С/C++).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
0 2
1 0
2 3
3 5
|
13
|