题目描述

水星上有 $n$ 个服务器，有 $n-1$ 根数据线，第 $i$ 根双向连接 $i$ 号服务器和 $i+1$ 号服务器。

假设 $j$ 号服务器收到了地球发来的信息。你需要尽快将信息传输到其他服务器。

一台服务器 $i$ 收到地球发来的信息后可以直接存储一份到它的数据库中，然后在缓冲区滞留 $t_i$ 秒后删除。

由于一些外界因素，第 $i$ 根数据线只能在 $[l_i,r_i]$ 时间段内传输信息。当某根数据线接通后，若这根数据线两边的服务器有一台的缓冲区还存有信息，那么另一台也可以得到这个信息。

你可以任意选择地球发给服务器 $j$ 信息的时刻，要求最后所有服务器都收到这个信息，问最早可以在多久发送信息，如果不存在可行解，请输出 $-1$。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $t_1,t_2,\dots,t_n$。

在接下来的 $n-1$ 行中，每行两个整数 $l_i,r_i$。

输出格式

输入 $n$ 行，每行一个整数，第 $i$ 行的数表示当 $j=i$ 时的答案，如果不可能输出 $-1$。

1
10

0

2
3 5
6 8

3
1

3
1 2 4
7 10
3 5

-1
5
5

4
1 0 3 2
4 6
5 5
7 10

5
5
4
-1

提示

【样例解释】

对于样例组 #3：

如果 $1$ 号服务器首先收到补丁，$3$ 号服务器就无法得到补丁，因为 $2$ 号信道在 $1$ 号信道开启前就关闭了。如果 $2$ 号服务器在第 $5$ 秒收到补丁，则 $3$ 号服务器可以立即收到补丁，之后，等到第 $7$ 秒时 $1$ 号信道开启时，$1$ 号服务器就会收到补丁。如果 $3$ 号服务器在第 $5$ 秒收到补丁，则 $2$ 号服务器可以立即收到补丁，之后，等到第 $7$ 秒时 $1$ 号信道开启时，$1$ 号服务器就会收到补丁。

对于样例组 #4：

若 $2$ 号服务器首先收到补丁，由于 $2$ 号服务器从不缓存，且 $2$ 号信道只在第 $5$ 秒开启，为了让 $3$ 号服务器拿到补丁，你只能选择在第 $5$ 秒把补丁发给 $2$ 号服务器。若 $3$ 号服务器首先收到补丁，不妨选择第 $4$ 秒，$3$ 号服务器会将其缓存至第 $7$ 秒，这样 $2$ 号和 $4$ 号服务器都能拿到补丁。

【数据范围】

注：本题只放部分数据，完整数据请左转 LOJ P2771 评测。

对于所有数据，$0 \le l_i \le r_i \le 10^9$。