Sprinklers

提交数: 5, 通过率: 100%, 平均分: 100

农夫约翰有一块很大的田，他正在考虑种甜玉米。经过对他农田的调查，FJ发现它形成了一个（N-1）×（N-1）的

正方形。西南角为坐标（0,0），东北角是（N-1，N-1）。在某些整数坐标的位置中有双头喷头，每一个都能够同

时喷洒水和肥料。一个在（i，j）处的双头喷头会将水洒在农田中所有在其东面且在其北面的区域，将肥料洒在农

田中所有在其南面且在其西面的区域。形式化地说，这个喷头将会将水洒在所有满足N≥x≥i和N≥y≥j的实数坐标

(x,y)上，会将肥料洒在所有满足0≤x≤i和0≤y≤j的实数坐标上农民约翰想在一些边与坐标轴平行的长方形农田

里种植甜玉米。然而，为了甜玉米的生长，矩形内的所有点都必须由双头喷头浇水和施肥。当然，矩形必须有正的

面积，否则农民约翰就不能在里面种植任何玉米！帮助农民约翰确定可以种植甜玉米的拥有正面积的矩形农田数。

由于这个数字可能很大，所以输出对为10^9 + 7取模

第一行包含一个整数N，表示农场的大小（1≤N≤10^5）。

接下来的n行各包含两个由空格分隔的整数。这些整数中0≤i，j≤N-1，这表示有一个双头喷头位于（i，j）的位置。

保证每列都有一台喷头，每排正好有一台喷头。这也就是说，没有两个喷头有相同的x坐标或y坐标。

输出包含一行，表示拥有正面积的合法矩形农田的个数，对10^9+7取模.

时间限制: 1000ms
空间限制: 128MB

来源: Usaco2018 Jan Platinum