CF992E Nastya and King-Shamans

Nastya 喜欢阅读，有时甚至会在图书馆里待上一整天。今天她在图书馆里发现了 Byteland 的编年史，上面记载着很久以前这里住着萨满。据悉，在任何时刻 Byteland 里恰好有一位萨满，总共有 $n$ 位萨满，按照他们生活的顺序用 $1$ 到 $n$ 的整数编号。同时，每位萨满都有一个可以用整数表示的魔法力量。 编年史中包含了这 $n$ 位萨满的力量列表。此外，有些萨满可以成为“王萨满”，如果他们的力量恰好等于所有前任萨满力量之和，即他们的力量等于之前所有萨满力量的总和。Nastya 想知道 Byteland 是否至少有一位王萨满。 不幸的是，列表中许多力量已经无法辨认，所以 Nastya 采取了如下操作： - 她会为每位萨满假定一个初始力量。 - 之后她会对某些萨满的力量进行 $q$ 次修改（每次修改的萨满可以不同），每次修改后她都想检查列表中是否存在至少一位王萨满。如果存在，她想知道任意一位王萨满的编号。 然而列表太大，Nastya 希望你能帮她完成这个任务。

第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 2 \cdot 10^{5}$）。 第二行包含 $n$ 个整数 $a_1, \ldots, a_n$（$0 \leq a_i \leq 10^9$），其中 $a_i$ 表示第 $i$ 位萨满的魔法力量。 接下来 $q$ 行，每行包含两个整数 $p_i$ 和 $x_i$（$1 \leq p_i \leq n$，$0 \leq x_i \leq 10^9$），表示将第 $p_i$ 位萨满的力量修改为 $x_i$。

输出 $q$ 行，第 $i$ 行输出 $-1$，如果第 $i$ 次修改后没有王萨满；否则输出一个整数 $j$，表示第 $i$ 次修改后任意一位王萨满的编号。 如果每次修改后存在多个王萨满，可以输出其中任意一个的编号。

在第一个样例中，第一次修改后萨满的力量变为 $(2,3)$。答案为 $-1$，因为第一位萨满之前的力量和为 $0$，第二位萨满之前的力量和为 $2$，都没有满足条件的王萨满。 在第二个样例中，第一次修改后力量为 $(1,2,3)$。答案为 $3$，因为第三位萨满的力量为 $3$，而前两位萨满的力量和也是 $1+2=3$。第二次修改后力量为 $(2,2,3)$，答案为 $2$。第三次修改后力量为 $(2,4,3)$，答案为 $-1$。第四次修改后力量为 $(2,4,6)$，答案为 $3$。 由 ChatGPT 4.1 翻译