配点: 1000 点
問題文
KYOPRO-MARKET 有限公司自上市以来已上市。 D 天过去了。1 当日股价为 X 是日元, 关于i = 2,3, ... ,D , 当我输入i 当日股价较前一日上涨。 A_i 只贵了日元( 如果A_i 是负数,则表示更便宜)。
「S_j 当日股价和 T_j 当天哪支股票价格较高? ” 表格中的问题 Q 问题,因此请编写一个程序来回答每个问题。
计算量为 优选 O(D + Q) 。
制約
- 所有输入均为整数
- 2 \leqq D \leqq 2 \times 10^5
- 1 \leqq X \leqq 10^9
- -5\,000 \leqq A_i \leqq 5\,000 (2 \leqq i \leqq D)
- 1 \leqq Q \leqq 2 \times 10^5
- 1 \leqq S_j < T_j \leqq D (1 \leqq j \leqq Q)
- 上市以来任意一日股价 请输出 1 就这样 请输出超过
入力
输入是按以下格式从标准输入给出的。
D X A_2 \vdots A_D Q S_1 T_1 \vdots S_Q T_Q
出力
到标准输出 输出 Q 行。 列出j 行中,j 问题的答案,如下所示。
- S_j 日的股价为 T_j 如果高于当日股价,S_j 的值。
- T_j 日的股价为 S_j 如果高于当日股价,T_j 的值。
- S_j 当日股价和 T_j 如果当天股价相等,
Same。
入力例 1
5 30 -10 20 -10 20 3 1 2 3 5 1 4
出力例 1
1 5 Same
5 每日股价如下。
- 1 当日股价为 X = 30。
- 2 当日股价为 30 - 10 = 20。
- 3 当日股价为 20 + 20 = 40。
- 4 当日股价为 40 - 10 = 30。
- 5 当日股价为 30 + 20 = 50。
3 每个问题的答案如下:
- 1 当日股价为 2 高于当日股价。因此,1 在线 1 。 我锻炼
- 5 当日股价为 3 高于当日股价。因此,2 在线 5 。 我锻炼
- 1 当日股价和 4 第一天的股价相同。因此,3 在线
Same。 我锻炼