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