#10584. 射箭

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Turing001

题目描述

小 O 来到了河边散步,看见了远处的一个射箭场,小 O 对射箭造诣颇深.

他观察到有 n 个人在比赛射箭,第 i 个人射箭起点为 s_i ,箭落到 t_i ,其中有一些人在向右射箭,另一部分人在向左射箭。

并且任意两个同向射箭的人,不会有一个人的箭的飞行轨迹被另一个人的完全包含(端点重合不计)。

例如,2 5 完全包含 3 4;但 2 5 不完全包含 3 5,因为端点重合不计。

如果两个人分别在向右和向左射箭,并且他们射箭的轨迹有相交部分(计算端点),则我们称这一对人是危险的。

现在小 O 想知道,有多少对人是危险的。

输入格式

第一行,一个数 n。

第二行,n 个数,第 i 个数是 1 代表第 i 个人向右,是 0 代表向左。

接下来 n 行,每行两个数,第 i 行为 s_i,t_i 。(向右的人 s_i\leq t_i ,向左的人 s_i\geq t_i

输出格式

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

样例

样例输入

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

样例输出

3

解释:(1,4)(2,4)(3,4)是危险的

数据范围与提示

对于 30% 的数据, 1\leq n \leq 1000

对于 100% 的数据, 1\leq n \leq 10^5,1\leq s_i,t_i \leq 10^9