{"problem":{"name":"[ROI 2017] 水星上的服务器 (Day 2)","description":{"content":"水星上有 $n$ 个服务器，有 $n-1$ 根数据线，第 $i$ 根双向连接 $i$ 号服务器和 $i+1$ 号服务器。 假设 $j$ 号服务器收到了地球发来的信息。你需要尽快将信息传输到其他服务器。 一台服务器 $i$ 收到地球发来的信息后可以直接存储一份到它的数据库中，然后在缓冲区滞留 $t_i$ 秒后删除。 由于一些外界因素，第 $i$ 根数据线只能在 $[l_i,r_i]$ 时间段内","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":700,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10654"},"statements":[{"statement_type":"Markdown","content":"水星上有 $n$ 个服务器，有 $n-1$ 根数据线，第 $i$ 根双向连接 $i$ 号服务器和 $i+1$ 号服务器。\n\n假设 $j$ 号服务器收到了地球发来的信息。你需要尽快将信息传输到其他服务器。\n\n一台服务器 $i$ 收到地球发来的信息后可以直接存储一份到它的数据库中，然后在缓冲区滞留 $t_i$ 秒后删除。\n\n由于一些外界因素，第 $i$ 根数据线只能在 $[l_i,r_i]$ 时间段内传输信息。当某根数据线接通后，若这根数据线两边的服务器有一台的缓冲区还存有信息，那么另一台也可以得到这个信息。（每个服务器会在其接收到信息后能传递的**第一时间**把信息传递出去）\n\n你可以任意选择地球发给服务器 $j$ 信息的时刻，要求最后所有服务器都收到这个信息，问最早可以在多久发送信息，如果不存在可行解，请输出 $-1$。\n\n## Input\n\n第一行一个整数 $n$。\n\n第二行 $n$ 个整数 $t_1,t_2,\\dots,t_n$。\n\n在接下来的 $n-1$ 行中，每行两个整数 $l_i,r_i$。\n\n## Output\n\n输入 $n$ 行，每行一个整数，第 $i$ 行的数表示当 $j=i$ 时的答案，如果不可能输出 $-1$。\n\n[samples]\n\n## Note\n\n#### 【样例解释】\n\n对于样例组 #3：\n\n如果 $1$ 号服务器首先收到补丁，$3$ 号服务器就无法得到补丁，因为 $2$ 号信道在 $1$ 号信道开启前就关闭了。如果 $2$ 号服务器在第 $5$ 秒收到补丁，则 $3$ 号服务器可以立即收到补丁，之后，等到第 $7$ 秒时 $1$ 号信道开启时，$1$ 号服务器就会收到补丁。如果 $3$ 号服务器在第 $5$ 秒收到补丁，则 $2$ 号服务器可以立即收到补丁，之后，等到第 $7$ 秒时 $1$ 号信道开启时，$1$ 号服务器就会收到补丁。\n\n对于样例组 #4：\n\n若 $2$ 号服务器首先收到补丁，由于 $2$ 号服务器从不缓存，且 $2$ 号信道只在第 $5$ 秒开启，为了让 $3$ 号服务器拿到补丁，你只能选择在第 $5$ 秒把补丁发给 $2$ 号服务器。若 $3$ 号服务器首先收到补丁，不妨选择第 $4$ 秒，$3$ 号服务器会将其缓存至第 $7$ 秒，这样 $2$ 号和 $4$ 号服务器都能拿到补丁。\n\n#### 【数据范围】\n\n注：本题只放部分数据，完整数据请左转 [LOJ P2771](https://loj.ac/p/2771) 评测。\n\n对于所有数据，$0 \\le l_i \\le r_i \\le 10^9$。\n\n| 子任务编号 | 分值 | $1 \\le n \\le $ | $0 \\le t_i \\le$ | $0 \\le r_i \\le$ | 特殊性质 |\n| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |\n| $1$ | $20$ | $500$ | $500$ | $500$ | 无 |\n| $2$ | $10$ | $5000$ | / | $5000$ | $t_i=5000$ |\n| $3$ | $10$ | $5000$ | $5000$ | / | $r_i=5000$ |\n| $4$ | $10$ | $5000$ | $5000$ | $5000$ | 无 |\n| $5$ | $15$ | $2 \\times 10^5$ | / | $10^9$ | $t_i=10^9$ |\n| $6$ | $15$ | $2 \\times 10^5$ | $10^9$ | / | $r_i=10^9$ |\n| $7$ | $20$ | $2 \\times 10^5$ | $10^9$ | $10^9$ | 无 |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10654","tags":["2017","O2优化","ROI（俄罗斯）"],"sample_group":[["1\n10","0"],["2\n3 5\n6 8","3\n1"],["3\n1 2 4\n7 10\n3 5","-1\n5\n5"],["4\n1 0 3 2\n4 6\n5 5\n7 10","5\n5\n4\n-1"]],"created_at":"2026-03-03 11:09:25"}}