Задачи
Прямоугольное пастбище
Прямоугольное пастбище
Самое большое пастбище фермера Джона можно рассматривать как большую двумерную сетку квадратных "ячеек" (изобразите огромную шахматную доску). В настоящее время некоторые из этих клеток занимают $n$ коров.
Фермер Джон хочет построить забор, ограждающий прямоугольную область ячеек; прямоугольник должен быть ориентирован так, чтобы его стороны были параллельны осям $x$ и $y$, и он может быть размером в одну ячейку. Помогите ФД подсчитать количество отдельных групп коров, которых он может огородить в таком регионе. Обратите внимание, что пустое подмножество следует считать одним из них.
\InputFile
Первая строка содержит одно целое число $n~(1 \le n \le 2500)$. Каждая из следующих $n$ строк содержит два целых числа, обозначающих координаты $(x, y)$ клетки коровы. Все координаты $x$ отличаются друг от друга, все координаты $y$ отличаются друг от друга. Все значения $x$ и $y$ лежат в диапазоне $0 ... 10^9$.
\OutputFile
Выведите количество подмножеств коров, которых может отгородить ФД. Можно показать, что эта величина умещается в 64-битное целое число со знаком (например, long long в C/C++).
\Examples
Всего существует $24$ подмножества. ФД не может создать забор, ограждающий только коров $1, 2$ и $4$, или только коров $2$ и $4$, или только коров $1$ и $4$, поэтому ответ будет $24 − 3 = 16 − 3 = 13$.
Входные данные #1
4 0 2 1 0 2 3 3 5
Выходные данные #1
13