TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

90.3% (28/31)

Submission's AC Ratio

61.7% (66/107)

Tags

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 65536 262144 1
1 2000 65536 262144 2
2 2000 65536 262144 3
3 2000 65536 262144 4
4 2000 65536 262144 5
5 2000 65536 262144 6
6 2000 65536 262144 7
7 2000 65536 262144 8
8 2000 65536 262144 9
9 2000 65536 262144 10
10 2000 65536 262144 11
11 2000 65536 262144 12
12 2000 65536 262144 13
13 2000 65536 262144 14
14 2000 65536 262144 15
15 2000 65536 262144 16
16 2000 65536 262144 17