| 问题描述 |
|---|
给你一个长度为 $$n$$ 的一维矩阵，有 $$q$$ 次查询,每次查询给定一个下标 $$x$$ ，求以 $$x$$ 为左边界，你能找到的最大矩形和。 例如给你一个长度为 $$5$$ 的一维矩阵： $$\begin{bmatrix}0,1,-1,1,1\end{bmatrix}$$ ，如果以下标 $$2$$ 作为左边界，那么能够构成最大矩形和的右边界是 $$5$$，和为 $$2$$ 。（不会不包含元素）
|
| 输入描述 |
第一行先是一个正整数 $$n$$ 表示一维矩阵的长度。$$(n\le 1e5)$$ 接下去一行，包含 $$n$$ 个元素 $$a_i$$。$$(-1e5 \le a_i \le 1e5)$$ 接着是一个正整数 $$q$$ 表示查询次数 $$(q \le 1e5)$$ 然后 $$q$$ 行，每行一个值 $$x$$ ，表示询问你以下标 $$x$$ 作为左边界，能获取的最大矩形和是多少。$$(1 \le x \le n)$$
|
| 输出描述 |
针对每次查询，输出以 $$x$$ 为左边界的最大矩形和。 |
| 样例输入复制样例 |
5 0 1 -1 1 1 2 2 3 |
| 样例输出 |
2 1 |
| 相关 |