TopCoder

User's AC Ratio

83.3% (10/12)

Submission's AC Ratio

53.6% (15/28)

Description

地平線上有許多建築排成一列,現在我們想要在其中蓋兩座雙子星大廈。
你可以假設大廈是「插入」在兩棟建築之間,或者在地平線的最外邊
也就是說,大廈可以任意的建築在兩棟建築之間,或者最左/最右端。

不過雙子星大廈的建造是有條件的,首先,雙子星大廈必定是兩棟同高的;
再者,兩座雙子星大廈之間不能有比他們高的建築 (但可以一樣高)
否則兩座「雙子星大廈」之間竟然不能彼此看見,顯然是非常愚蠢的情形;
除此以外,由於都市地平線美觀起見,我們會希望兩棟建築物之間最少相隔d棟建築。

這個問題首先會告訴你這n棟建築由左到右的高度是多少,再來會有q個詢問
每個問題有個整數d代表兩棟雙子星大廈之間至少相隔幾棟建築
你必須回答雙子星大廈的高度至少要為多少,才能滿足以上條件。

Input Format

第一行有一個整數n,代表總共有幾棟建築
下一行有n個正整數,分別代表由左到右,建築物的高度
再接著是一個整數q,代表總共有多少個詢問
接下來q行每一行有一個整數d,代表兩座大廈之間需要相隔多少棟建築。

建築數目1<=n<=500,000
詢問數目1<=q<=500,000
建築高度1<=hi<=100,000,000
相隔建築1<=d<=n

Output Format

對應每一個詢問,請於輸出滿足此情況時,雙子星大廈最小的高度。

Sample Input

12
12 1 1 1 10 6 2 4 1 3 8 9
3
2
7
9

Sample Output

1
9
10

Hints

Problem Source

原TIOJ1320 / TIOJ IOI Warmup III, 2008. Problemsetter: kelvin

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 (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