Самое большое пастбище фермера Джона можно рассматривать как большую двумерную сетку квадратных "ячеек" (изобразите огромную шахматную доску). В настоящее время некоторые из этих клеток занимают коров.
Фермер Джон хочет построить забор, ограждающий прямоугольную область ячеек; прямоугольник должен быть ориентирован так, чтобы его стороны были параллельны осям и , и он может быть размером в одну ячейку. Помогите ФД подсчитать количество отдельных групп коров, которых он может огородить в таком регионе. Обратите внимание, что пустое подмножество следует считать одним из них.
Первая строка содержит одно целое число . Каждая из следующих строк содержит два целых числа, обозначающих координаты клетки коровы. Все координаты отличаются друг от друга, все координаты отличаются друг от друга. Все значения и лежат в диапазоне .
Выведите количество подмножеств коров, которых может отгородить ФД. Можно показать, что эта величина умещается в 64-битное целое число со знаком (например, long long в C/C++).
Всего существует подмножества. ФД не может создать забор, ограждающий только коров и , или только коров и , или только коров и , поэтому ответ будет .