[ROI 2017] 水星上的服务器 (Day 2)

水星上有 $n$ 个服务器，有 $n-1$ 根数据线，第 $i$ 根双向连接 $i$ 号服务器和 $i+1$ 号服务器。 假设 $j$ 号服务器收到了地球发来的信息。你需要尽快将信息传输到其他服务器。 一台服务器 $i$ 收到地球发来的信息后可以直接存储一份到它的数据库中，然后在缓冲区滞留 $t_i$ 秒后删除。 由于一些外界因素，第 $i$ 根数据线只能在 $[l_i,r_i]$ 时间段内传输信息。当某根数据线接通后，若这根数据线两边的服务器有一台的缓冲区还存有信息，那么另一台也可以得到这个信息。（每个服务器会在其接收到信息后能传递的**第一时间**把信息传递出去） 你可以任意选择地球发给服务器 $j$ 信息的时刻，要求最后所有服务器都收到这个信息，问最早可以在多久发送信息，如果不存在可行解，请输出 $-1$。 ## Input 第一行一个整数 $n$。 第二行 $n$ 个整数 $t_1,t_2,\dots,t_n$。 在接下来的 $n-1$ 行中，每行两个整数 $l_i,r_i$。 ## Output 输入 $n$ 行，每行一个整数，第 $i$ 行的数表示当 $j=i$ 时的答案，如果不可能输出 $-1$。 [samples] ## Note #### 【样例解释】 对于样例组 #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](https://loj.ac/p/2771) 评测。 对于所有数据，$0 \le l_i \le r_i \le 10^9$。 | 子任务编号 | 分值 | $1 \le n \le $ | $0 \le t_i \le$ | $0 \le r_i \le$ | 特殊性质 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $20$ | $500$ | $500$ | $500$ | 无 | | $2$ | $10$ | $5000$ | / | $5000$ | $t_i=5000$ | | $3$ | $10$ | $5000$ | $5000$ | / | $r_i=5000$ | | $4$ | $10$ | $5000$ | $5000$ | $5000$ | 无 | | $5$ | $15$ | $2 \times 10^5$ | / | $10^9$ | $t_i=10^9$ | | $6$ | $15$ | $2 \times 10^5$ | $10^9$ | / | $r_i=10^9$ | | $7$ | $20$ | $2 \times 10^5$ | $10^9$ | $10^9$ | 无 |