P10654 [ROI 2017] Servers on Mercury (Day 2)

There are $n$ servers on Mercury and $n-1$ data cables. The $i$-th cable connects server $i$ and server $i+1$ in both directions. Suppose server $j$ receives a message sent from Earth. You need to transmit the message to all other servers as quickly as possible. After a server $i$ receives the message from Earth, it can immediately store a copy in its database, and then keep it in its buffer for $t_i$ seconds before deleting it. Due to some external factors, the $i$-th data cable can transmit information only during the time interval $[l_i,r_i]$. When a cable is active, if at least one of the two servers at its ends still has the message in its buffer, then the other one can obtain the message as well. (After a server receives the message, it will forward the message at the **earliest possible** time.) You may choose any time to send the message from Earth to server $j$. In the end, all servers must receive this message. Find the earliest time at which you can send the message. If no feasible solution exists, output $-1$.

The first line contains an integer $n$. The second line contains $n$ integers $t_1,t_2,\dots,t_n$. In the next $n-1$ lines, each line contains two integers $l_i,r_i$.

Output $n$ lines, each containing one integer. The number on line $i$ is the answer when $j=i$. If it is impossible, output $-1$.

#### Sample Explanation For sample group #3: If server $1$ receives the patch first, then server $3$ cannot get the patch, because channel $2$ closes before channel $1$ opens. If server $2$ receives the patch at second $5$, then server $3$ can receive the patch immediately. After that, when channel $1$ opens at second $7$, server $1$ will receive the patch. If server $3$ receives the patch at second $5$, then server $2$ can receive the patch immediately. After that, when channel $1$ opens at second $7$, server $1$ will receive the patch. For sample group #4: If server $2$ receives the patch first, since server $2$ never caches it and channel $2$ opens only at second $5$, in order for server $3$ to get the patch, you can only choose to send the patch to server $2$ at second $5$. If server $3$ receives the patch first, you may choose second $4$. Server $3$ will cache it until second $7$, so both server $2$ and server $4$ can get the patch. #### Constraints Note: This problem provides only part of the testdata. For the full testdata, please go to [LOJ P2771](https://loj.ac/p/2771) for judging. For all data, $0 \le l_i \le r_i \le 10^9$. | Subtask ID | Score | $1 \le n \le $ | $0 \le t_i \le$ | $0 \le r_i \le$ | Special Property | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $20$ | $500$ | $500$ | $500$ | None | | $2$ | $10$ | $5000$ | / | $5000$ | $t_i=5000$ | | $3$ | $10$ | $5000$ | $5000$ | / | $r_i=5000$ | | $4$ | $10$ | $5000$ | $5000$ | $5000$ | None | | $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$ | None | Translated by ChatGPT 5