QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 125 MB Total points: 100
[+5]

# 7491. 纵使日薄西山

Statistics

题目描述

珂朵莉想让你维护一个长度为 n 的正整数序列 a1,a2,,an,支持修改序列中某个位置的值。

每次修改后问对序列重复进行以下操作,需要进行几次操作才能使序列变为全 0(询问后序列和询问前相同,不会变为全 0):

选出序列中最大值的出现位置,若有多个最大值则选位置标号最小的一个,设位置为 x,则将 ax1,ax,ax+1 的值减 1,如果序列中存在小于 0 的数,则把对应的数改为 0

输入格式

第一行一个整数 n

接下来 n 行,每行一个整数 ai

接下来一行一个整数 q

接下来 q 行,每行两个用空格分隔的整数 xi,yi,表示把 axi 修改为 yi

输出格式

q 行,每行一个整数表示答案。

样例 #1

样例输入 #1

4
3
6
6
4
3
4 4
3 5
1 8

样例输出 #1

10
10
13

提示

Idea:ccz181078,Solution:ccz181078,Code:ccz181078,Data:ccz181078

1n,q1051xin1ai,yi109