← 返回题目列表

AtCoder · tessoku_book_fa

C03. 库存查询

中文机器翻译题面 查看原题

配点: 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 。 我锻炼