在一座草原上遍佈著許多美麗的花朵,每一株花朵都可以用一個二維平面座標 $(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)$,一共有六種可能的集合,其中兩個集合恰包含一株花朵,三個集合恰包含兩株花朵,一個集合包含所有花朵。
輸入第一行包含一個正整數 $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$ 株花朵的座標位置。
輸入保證所有花朵的座標街相異。
請輸出一個整數代表有幾種可能的花朵集合可以被小風圍起來。
Codeforces
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~2 | 範例測資 | 0 |
2 | 0~26 | 無額外限制 | 100 |