限制

• 1000ms
• 512MB

题目描述

lxy 来到了河边散步，看见了远处的一个射箭场，他观察到有 $n$ 个人在比赛射箭。

如果把射箭场看作是一条数轴，第 $i$ 个人射箭起点为 $s_i$，箭落到 $t_i$，其中有一些人在向右射箭，另一部分人在向左射箭

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

如果两个人分别在向右和向左射箭，并且他们射箭的轨迹有相交部分（计算端点），则我们称这一对人是危险的，现在 lxy 想知道，有多少对人是危险的。

输入格式

第一行，一个数 $n$。

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

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

输出格式

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

数据规模与约定

对于 $30\%$ 的数据， $1\leq n \leq 1000$；

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

样例输入

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

样例输出

3