Untitled

mail@pastecode.io avatar
unknown
python
2 years ago
1.2 kB
4
Indexable
Never
add = []
end = []
res = []
beginIndex = []


def func(a: list[int]):
    for index, val in enumerate(a):
        beginIndex.append(max(index - val + 1, 0))
    e = 0
    for i in range(len(a)):
        while e + 1 < len(beginIndex) and beginIndex[e + 1] <= i:
            e += 1
        res.append(a[i:e + 1])
        end.append(e)
        add.append(e - i + 1)


n = int(input().strip())
a = [int(i) for i in input().split()]
num = int(input().strip())
func(a)
# print(add)
for _ in range(num):
    p, x = [int(i) for i in input().split()]
    tmpBegin = max(p - 1 - x + 1, 0)
    prevBegin = beginIndex[p - 1]
    beg = beginIndex[:]
    beg[p - 1] = tmpBegin
    endd = end[:]
    if prevBegin < tmpBegin:
        for i in range(prevBegin, tmpBegin):
            if end[i] >= p - 1:
                endd[i] = max(0, p - 2)
    else:
        for i in range(tmpBegin, prevBegin):
            e = endd[i]
            while e + 1 < len(beg) and beg[e + 1] <= i:
                e += 1
            endd[i] = e
    # print(end)
    # print(endd)
    # print(beginIndex)
    # print(beg)
    add1 = [v - k + 1 for k, v in enumerate(endd)]
    print(sum(add1))