1274:Maximum and minimum

时间限制: 1 S | 内存限制: 65536 KB
Accept: 18 | Submit: 51
[提交] [状态] [讨论版]
描述

给你一个长度为 n 的数列,输入一个数字 x,你需要从区间 [1,x] 中找到一个最大值 max,从 [x,n] 区间中找到一个最小值 min,然后输出 max + min。

输入

第一行是一个正整数 n 代表数列的长度。(1 <= n <= 1e5)

第二行是 n 个正整数代表这个数列中的每一个数。(1 <= ai <= 1e5,1 <= i <= n)

接下来是一个正整数 m 代表查询的次数。(1 <= m <= 1e5)

每次查询是一个正整数 x。(1 <= x <=n)

输出
针对每一次查询,输出 max + min 的值,然后换行。
样例输入

5

2 3 1 5 4

2

3

4

样例输出

4

9


HINT

第一次查询:区间 [1,3] 的 max 是 3,区间 [3,5] 的 min 是 1,max + min = 4。

第二次查询:区间 [1,4] 的 max 是 5,区间 [4,5] 的 min 是 4,max + min = 9。

来源
TKK-ICPC Round#4