TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

Description

在一座草原上遍佈著許多美麗的花朵,每一株花朵都可以用一個二維平面座標 $(x_i, y_i)$ 來代表他在草原上的位置。小風想要在這座廣闊無際的草原上蓋一棟房子,他想要偷偷用圍籬將一些花朵圍起來,這樣他就可以獨自欣賞這些美麗的花朵了。小風的圍籬可以用兩條鉛直線 $x = l, x = r$ 以及一條水平線 $y = a$ 來表示,在這三條直線圍起來向上無限延伸的矩形區域就是小風的家了,如圖為一個例子,其中 $p_1$ 在小風家內,而 $p_2$ 不在內,注意 $l, r, a$ 均可以為任意實數。

小風想要知道幾種花朵們的集合是剛好可以被他為在圍欄裡的,因為小風一定要欣賞花朵,所以不可以沒有包住任何花朵,請你幫助他計算可能的數量。只要有一株花朵在其中一個集合而不在另一個集合中,這兩個集合就被視為相異的。

以下為一個例子:四株花朵分別座落於 $(1, 1), (1, 2), (2, 1), (2, 2)$,一共有六種可能的集合,其中兩個集合恰包含一株花朵,三個集合恰包含兩株花朵,一個集合包含所有花朵。

Input Format

輸入第一行包含一個正整數 $N (1 \leq N \leq 2 \times 10^ 5)$,代表草原上花朵的數量。
接下來的 $N$ 行,第 $i$ 包含兩個整數 $x_i, y_i (1 \leq x_i, y_i \leq 10^ 9)$,代表第 $i$ 株花朵的座標位置。
輸入保證所有花朵的座標街相異。

Output Format

請輸出一個整數代表有幾種可能的花朵集合可以被小風圍起來。

Sample Input 1

3
1 1
1 2
1 3

Sample Output 1

3

Sample Input 2

3
1 1
2 1
3 1

Sample Output 2

6

Sample Input 3

4
2 1
2 2
3 1
3 2

Sample Output 3

6

Hints

Problem Source

Codeforces

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~26 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 524288 65536 1 2
1 3000 524288 65536 1 2
2 3000 524288 65536 1 2
3 3000 524288 65536 2
4 3000 524288 65536 2
5 3000 524288 65536 2
6 3000 524288 65536 2
7 3000 524288 65536 2
8 3000 524288 65536 2
9 3000 524288 65536 2
10 3000 524288 65536 2
11 3000 524288 65536 2
12 3000 524288 65536 2
13 3000 524288 65536 2
14 3000 524288 65536 2
15 3000 524288 65536 2
16 3000 524288 65536 2
17 3000 524288 65536 2
18 3000 524288 65536 2
19 3000 524288 65536 2
20 3000 524288 65536 2
21 3000 524288 65536 2
22 3000 524288 65536 2
23 3000 524288 65536 2
24 3000 524288 65536 2
25 3000 524288 65536 2
26 3000 524288 65536 2