Дано \(n\) точек на плоскости, \(i\)-я из которых расположена в \((x_i, y_i)\). Tokitsukaze хочет нарисовать странную прямоугольную область и взять все точки в этой области.
Странная область ограничена тремя прямыми, \(x = l\), \(y = a\) и \(x = r\), это ее левая, нижняя и правая сторона, соответственно, где \(l\), \(r\) и \(a\) могут являться любыми вещественными числами, удовлетворяющими \(l < r\). Верхняя сторона области неограничена, то есть можно считать, что она ограничена прямой, параллельной оси \(x\), и бесконечно удаленной. Странная прямоугольная область изображена на следующей иллюстрации.
Точка \((x_i, y_i)\) находится в странной прямоугольной области тогда и только тогда, когда \(l < x_i < r\) и \(y_i > a\). К примеру, на иллюстрации выше \(p_1\) находится в области, а \(p_2\) — нет.
Tokitsukaze хочет узнать, сколько существует различных непустых множеств, которые можно получить, выбирая все точки в некоторой странной прямоугольной области. Два множества считаются различными, если существует хотя бы одна точка в одном из них, которой нет во втором.
Примечание
В первом примере существует только одно множество, содержащее \(k\) точек для \(k = 1, 2, 3\), поэтому общее число множеств равно \(3\).
Во втором примере количества множеств размера \(k\) для \(k = 1, 2, 3\) равны \(3\), \(2\), \(1\) соответственно, и их сумма равна \(6\).
В третьем примере, как показывает следующая иллюстрация, есть
- \(2\) множества из одной точки;
- \(3\) множества из двух точек;
- \(1\) множество из четырех точек.
Исходя из этого, количество различных непустых множеств в этом примере равно \(2 + 3 + 0 + 1 = 6\).
