Description

Young gardener didn’t visit his garden for a long time, and now it’s not very pleasant there: n caterpillars have appeared on the ground.

Kirill decided to use this opportunity to have some fun and organized a competition — “caterpillar crawl-race.”

At Kirill’s command all caterpillars start crawling from the ground to the top of a tree. But they get tired PRetty fast. After crawling ti$t_i$ cm i-th caterpillar needs to rest for ti$t_i$ minutes. During that time it slides down a bit. Crawling speed of a caterpillar is 1 cm/minute, sliding speed — also 1 cm/minute.

Kirill is very much interested to find out how high on the tree is the leading caterpillar at different moments in time.

Input

First line contains one integer n — the number of caterpillars (1 ≤ n ≤ 106).

Second line contains n integers ti$t_i$ — characteristics of caterpillars (1≤ti≤109$1/le t_i /le 10^9$).

In the third line there is a number q — number of moments in time, which Kirill finds interesting (1≤q≤106$1/le q/le 10^6$).

Remaining q lines contain one query from Kirill each. A query is described by xi$x_i$ — number of minutes since the start of the competition (1≤xi≤106$1/le x_i /le 10^6$).

Output

For every query print in a separate line one integer, that describes how high is the highest caterpillar at the given moment of time.

題意

給定 n 只毛毛蟲，及 n 個(gè)數(shù) ti$t_i$ 。對(duì)于每只毛毛蟲，它們均從 0 時(shí)刻以高度 0 向上攀爬，以 1 cm/min 的速度上爬 ti$t_i$ 分鐘，再以 1cm/min 的速度下滑 ti$t_i$ 分鐘，再以 1 cm/min 的速度上爬 ti$t_i$ 分鐘，如此往復(fù)。

之后有 q 個(gè)詢問(wèn)，每個(gè)詢問(wèn)輸入一個(gè) x ，問(wèn)對(duì)每個(gè)詢問(wèn)給出 n 只毛毛蟲在 x 時(shí)刻最高的那只毛毛蟲的高度。

分析

此題可進(jìn)行暴力的預(yù)處理。

由于詢問(wèn)的 x 最大為 106$10^6$ ，因此只需預(yù)處理出 [1,106]$[1, 10^6]$ 區(qū)間每個(gè)時(shí)刻的最高高度。

首先可以確定對(duì)于毛毛蟲 i ，ti,3ti,5ti,...$t_i, 3t_i, 5t_i, ...$ 時(shí)刻它必定處在最高點(diǎn)，因此暴力處理每只毛毛蟲在 ti,3ti,5ti,...$t_i, 3t_i, 5t_i, ...$ 時(shí)刻的高度計(jì)為 ti$t_i$ ，始終求最大值保存在 ans[ x ] 。

對(duì)于其余時(shí)刻，可視作最高點(diǎn)向兩邊的擴(kuò)展，作二維坐標(biāo)即斜率為 1 或 -1 。正反向分別掃描，ans[ x ] = max(ans[x], ans[x-1] -1) ， ans[ x ] = max(ans[x], ans[x+1] - 1)。

需要注意的是，對(duì)于106$10^6$ 時(shí)刻這個(gè)截止點(diǎn)，必須額外處理，否則可能在邊界出錯(cuò)。

此處不得不提及神奇的 ios::sync_with_stdio(0); 否則會(huì)被卡時(shí)間。

代碼