從莎朗大街的街頭走到街尾，依序會經過 \(n\) 棟大樓，其高度分別為 \(h_1, h_2, \ldots, h_n\)。每棟大樓的頂樓都是停機坪，對每個 \(k \in \{ 1, 2, \ldots, n \}\)，第 \(k\) 為飛行員想要從第 \(i_k\) 棟大樓駕駛直升機飛到第 \(j_k\) 棟大樓，其中 \(1 \leq i_k < j_k \leq n\)。她的飛行方式如下：先從第 \(i_k\) 棟大樓向上直升至被稱為 \(x_{i_k,  j_k}\) 的高度，接著在高度不變的情況下，向街尾飛至第 \(j_k\) 大樓上方，最後降落在第 \(j_k\) 棟大樓的頂端。為了避免撞到大樓，\(x_{i_k,  j_k}\) 不應小於 \(h_{i_k} + 1\)、\(h_{i_k+1} + 1\)、\(h_{i_k+2} + 1\)、\(\ldots\)、\(h_{j_k} + 1\) 中的任一個，為了省油，應盡量小，因此我們希望 \(x_{i_k,  j_k}\) 恰為 \(h_{i_k} + 1\)、\(h_{i_k+1} + 1\)、\(h_{i_k+2} + 1\)、\(\ldots\)、\(h_{j_k} + 1\) 的最小值。

輸入格式

1. 輸入第一行為 \(n\)，第二行為 \(h_1, h_2, \ldots, h_n\)，對於每個 \(k \in \{ 1, 2, \ldots, n \}\)，第 \(k+2\) 行為 \(i_k\) 與 \(j_k\)。
2. \(2 \leq n \leq 1000000\)且 \(1\leq h_1, h_2, \ldots, h_n \leq 1000000\)。
3. 同一行的數值間以空白隔開。

輸出格式

對每個\(k \in \{ 1, 2, \ldots, n \}\)，輸出的第 \(k\) 行為\(x_{i_k,  j_k}\)。

範例輸入

8
3 2 5 7 3 1 4 5
2 5
1 4
3 8
6 7
3 6
4 5
2 7
3 5

範例輸出

3
3
2
2
2
4
2
4

提示

本題出自 2018 TOI Pre (TIOJ 2055)