1320 . 雙子大廈 Twintower
TopCoder
Description
地平線上有許多建築排成一列，現在我們想要在其中蓋兩座雙子星大廈。
你可以假設大廈是「插入」在兩棟建築之間，或者在地平線的最外邊
也就是說，大廈可以任意的建築在兩棟建築之間，或者最左/最右端。
不過雙子星大廈的建造是有條件的，首先，雙子星大廈必定是兩棟同高的；
再者，兩座雙子星大廈之間不能有比他們高的建築（但可以一樣高）
否則兩座「雙子星大廈」之間竟然不能彼此看見，顯然是非常愚蠢的情形；
除此以外，由於都市地平線美觀起見，我們會希望兩棟建築物之間最少相隔 $d$ 棟建築。
這個問題首先會告訴你這 $n$ 棟建築由左到右的高度是多少，再來會有 $q$ 個詢問
每個問題有個整數 $d$ 代表兩棟雙子星大廈之間至少相隔幾棟建築
你必須回答雙子星大廈的高度至少要為多少，才能滿足以上條件。
Input Format
第一行有一個整數 $n$，代表總共有幾棟建築
下一行有 $n$ 個正整數，分別代表由左到右，建築物的高度
再接著是一個整數 $q$，代表總共有多少個詢問
接下來 $q$ 行每一行有一個整數 $d$，代表兩座大廈之間需要相隔多少棟建築。
建築數目 $1 \le n \le 500,000$
詢問數目 $1 \le q \le 500,000$
建築高度 $1 \le h_i \le 100,000,000$
相隔建築 $1 \le d \le n$
Output Format
對應每一個詢問，請於輸出滿足此情況時，雙子星大廈最小的高度。
Sample Input 1
12 12 1 1 1 10 6 2 4 1 3 8 9 3 2 7 9
Sample Output 1
1 9 10
Hints
Problem Source
原 TIOJ1320 / TIOJ IOI Warmup III, 2008. Problemsetter: kelvin
2024/02/27 Update: Added $\LaTeX$ by FHVirus
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 5 |
| 2 | 1 | 5 |
| 3 | 2 | 5 |
| 4 | 3 | 5 |
| 5 | 4 | 5 |
| 6 | 5 | 5 |
| 7 | 6 | 5 |
| 8 | 7 | 5 |
| 9 | 8 | 5 |
| 10 | 9 | 5 |
| 11 | 10 | 5 |
| 12 | 11 | 5 |
| 13 | 12 | 5 |
| 14 | 13 | 5 |
| 15 | 14 | 5 |
| 16 | 15 | 5 |
| 17 | 16 | 20 |