세 점

x 좌표가 증가하고 y 좌표가 r < b < g 순서가 되는 세 점의 조합 수를 센다.

보통7정렬누적 합조합론아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

무한히 넓은 이차원 평면에 점이 N개 있다. 점의 번호는 0번부터 N-1번까지이고, i번 점의 좌표는 (xi,yi)(x_i, y_i)이다. 서로 다른 두 점이 같은 x좌표를 갖는 경우는 없고, 같은 y좌표를 갖는 경우도 없다.

이 중에서 세 점을 골라 각각 빨간색, 초록색, 파란색으로 칠한다. 빨간색으로 칠한 점의 번호를 rr, 초록색으로 칠한 점의 번호를 gg, 파란색으로 칠한 점의 번호를 bb라고 하자. 색칠은 xr<xg<xbx_r < x_g < x_byr<yb<ygy_r < y_b < y_g를 동시에 만족해야 한다.

점의 좌표가 주어졌을 때, 조건을 만족하도록 세 점을 색칠하는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 둘째 줄부터 N개의 줄에 점의 좌표 xxyy가 공백을 사이에 두고 하나씩 주어진다. (1N300,0001 \le N \le 300{,}000, 0x,y<1,000,000,0000 \le x, y < 1{,}000{,}000{,}000)

출력

첫째 줄에 조건을 만족하도록 세 점을 색칠하는 방법의 수를 출력한다. 이 값은 32비트 정수의 범위를 넘을 수 있다.