Problem5316--射箭

5316: 射箭

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

小 O 来到了河边散步,看见了远处的一个射箭场,小 O 对射箭造诣颇深,他观察到有 n 个人在比赛射箭,第 i 个人射箭起点为 si,箭落到 ti,其中有一些人在向右射箭,另一部分人在向左射箭,并且任意两个同向射箭的人,不会有一个人的箭的飞行轨迹被另一个人的完全包含(端点重合不计)。如果两个人分别在向右和向左射箭,并且他们射箭的轨迹有相交部分(计算端点),则我们称这一对人是危险的,现在小 O 想知道,有多少对人是危险的。

Input

第一行,一个数 n。
第二行,n 个数,第 i 个数是 1 代表第 i 个人向右,是 0 代表向左。
接下来 n 行,每行两个数,第 ii 行为 si, ti。(向右的人 $s_{i} \leq t_{i}$,向左的人 $s_{i} \geq t_{i}$)

Output

一行,一个数,危险的人的对数。

Sample 1 Input

4
1 1 1 0
1 2
1 4
1 8
5 2

Sample 1 Output

3

HINT

【数据范围】
对于 30% 的数据, $1 \leq n \leq 1000$;
对于 100% 的数据,$1 \leq n \leq 10^{5}, 1 \leq s_{i}, t_{i} \leq 10^{9}$。

Source/Category