English · Original
Chinese · Translation
Formal · Original
Nastya likes reading and even spends whole days in a library sometimes. Today she found a chronicle of Byteland in the library, and it stated that there lived shamans long time ago. It is known that at every moment there was exactly one shaman in Byteland, and there were _n_ shamans in total enumerated with integers from 1 to _n_ in the order they lived. Also, each shaman had a magic power which can now be expressed as an integer.
The chronicle includes a list of powers of the _n_ shamans. Also, some shamans can be king-shamans, if they gathered all the power of their predecessors, i.e. their power is exactly the sum of powers of all previous shamans. Nastya is interested in whether there was at least one king-shaman in Byteland.
Unfortunately many of the powers are unreadable in the list, so Nastya is doing the following:
* Initially she supposes some power for each shaman.
* After that she changes the power of some shaman _q_ times (the shamans can differ) and after that wants to check if there is at least one king-shaman in the list. If yes, she wants to know the index of any king-shaman.
Unfortunately the list is too large and Nastya wants you to help her.
## Input
The first line contains two integers _n_ and _q_ (1 ≤ _n_, _q_ ≤ 2·105).
The second line contains _n_ integers _a_1, ..., _a__n_ (0 ≤ _a__i_ ≤ 109), where _a__i_ is the magic power of the _i_\-th shaman.
After that _q_ lines follow, the _i_\-th of them contains two integers _p__i_ and _x__i_ (1 ≤ _p__i_ ≤ _n_, 0 ≤ _x__i_ ≤ 109) that mean that the new power of the _p__i_\-th shaman is _x__i_.
## Output
Print _q_ lines, the _i_\-th of them should contain - 1, if after the _i_\-th change there are no shaman-kings, and otherwise a single integer _j_, where _j_ is an index of some king-shaman after the _i_\-th change.
If there are multiple king-shamans after each change, print the index of any of them.
[samples]
## Note
In the first example powers of shamans after the first change are equal to (2, 3). The answer equals - 1, because the sum of powers of shamans before the first shaman is equal to 0, and before the second is equal to 2.
In the second example after the first change the powers are equal to (1, 2, 3). The answer is equal to 3, because the power of the third shaman is equal to 3, and the sum of powers of the first and the second shaman is also 1 + 2 = 3. After the second change the powers become equal to (2, 2, 3), where the answer equals 2. After the third change the powers become equal to (2, 4, 3), where the answer equals - 1. After the fourth change the powers become equal to (2, 4, 6), where the answer equals 3.
Nastya 喜欢阅读，有时甚至整天待在图书馆里。今天她在图书馆里发现了一份比特兰的编年史，其中记载很久以前曾有萨满存在。已知在任何时刻，比特兰都恰好有一位萨满，总共有 #cf_span[n] 位萨满，按其生活顺序用整数从 #cf_span[1] 到 #cf_span[n] 编号。每位萨满都拥有一个魔法力量，现在可以用一个整数表示。
编年史中列出了 #cf_span[n] 位萨满的力量值。此外，某些萨满可能是“王萨满”，当且仅当他们的力量恰好等于其所有前任萨满力量之和。Nastya 想知道比特兰是否至少存在一位王萨满。
不幸的是，列表中许多力量值已无法辨认，因此 Nastya 进行了以下操作：
不幸的是，列表过于庞大，Nastya 希望你帮助她。
第一行包含两个整数 #cf_span[n] 和 #cf_span[q] (#cf_span[1 ≤ n, q ≤ 2·105])。
第二行包含 #cf_span[n] 个整数 #cf_span[a1, ..., an] (#cf_span[0 ≤ ai ≤ 109])，其中 #cf_span[ai] 表示第 #cf_span[i] 位萨满的魔法力量。
接下来 #cf_span[q] 行，第 #cf_span[i] 行包含两个整数 #cf_span[pi] 和 #cf_span[xi] (#cf_span[1 ≤ pi ≤ n], #cf_span[0 ≤ xi ≤ 109])，表示第 #cf_span[pi] 位萨满的新力量为 #cf_span[xi]。
请输出 #cf_span[q] 行，第 #cf_span[i] 行应包含 #cf_span[ - 1]，表示在第 #cf_span[i] 次修改后不存在王萨满；否则输出一个整数 #cf_span[j]，表示在第 #cf_span[i] 次修改后某位王萨满的索引。
如果每次修改后存在多个王萨满，请输出其中任意一个的索引。
在第一个例子中，第一次修改后萨满的力量为 #cf_span[(2, 3)]。答案为 #cf_span[ - 1]，因为第一位萨满之前的力量和为 #cf_span[0]，第二位萨满之前的力量和为 #cf_span[2]。
在第二个例子中，第一次修改后力量为 #cf_span[(1, 2, 3)]。答案为 #cf_span[3]，因为第三位萨满的力量为 #cf_span[3]，而前两位萨满的力量和为 #cf_span[1 + 2 = 3]。第二次修改后力量变为 #cf_span[(2, 2, 3)]，答案为 #cf_span[2]。第三次修改后力量变为 #cf_span[(2, 4, 3)]，答案为 #cf_span[ - 1]。第四次修改后力量变为 #cf_span[(2, 4, 6)]，答案为 #cf_span[3]。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[q] (#cf_span[1 ≤ n, q ≤ 2·105])。第二行包含 #cf_span[n] 个整数 #cf_span[a1, ..., an] (#cf_span[0 ≤ ai ≤ 109])，其中 #cf_span[ai] 表示第 #cf_span[i] 位萨满的魔法力量。接下来 #cf_span[q] 行，第 #cf_span[i] 行包含两个整数 #cf_span[pi] 和 #cf_span[xi] (#cf_span[1 ≤ pi ≤ n], #cf_span[0 ≤ xi ≤ 109])，表示第 #cf_span[pi] 位萨满的新力量为 #cf_span[xi]。
## Output
请输出 #cf_span[q] 行，第 #cf_span[i] 行应包含 #cf_span[ - 1]，表示在第 #cf_span[i] 次修改后不存在王萨满；否则输出一个整数 #cf_span[j]，表示在第 #cf_span[i] 次修改后某位王萨满的索引。如果每次修改后存在多个王萨满，请输出其中任意一个的索引。
[samples]
## Note
在第一个例子中，第一次修改后萨满的力量为 #cf_span[(2, 3)]。答案为 #cf_span[ - 1]，因为第一位萨满之前的力量和为 #cf_span[0]，第二位萨满之前的力量和为 #cf_span[2]。
在第二个例子中，第一次修改后力量为 #cf_span[(1, 2, 3)]。答案为 #cf_span[3]，因为第三位萨满的力量为 #cf_span[3]，而前两位萨满的力量和为 #cf_span[1 + 2 = 3]。第二次修改后力量变为 #cf_span[(2, 2, 3)]，答案为 #cf_span[2]。第三次修改后力量变为 #cf_span[(2, 4, 3)]，答案为 #cf_span[ - 1]。第四次修改后力量变为 #cf_span[(2, 4, 6)]，答案为 #cf_span[3]。
**Definitions:**
- Let $ a = (a_1, a_2, \dots, a_n) $ be a sequence of non-negative integers representing the magic powers of $ n $ shamans, indexed from 1 to $ n $.
- For each $ i \in \{1, 2, \dots, n\} $, define the prefix sum $ S_i = \sum_{j=1}^{i-1} a_j $ (i.e., sum of powers of all shamans before the $ i $-th).
- A shaman at index $ i $ is a **king-shaman** if $ a_i = S_i $.
**Given:**
- Initial sequence $ a = (a_1, \dots, a_n) $, with $ 1 \leq n, q \leq 2 \cdot 10^5 $, $ 0 \leq a_i \leq 10^9 $.
- $ q $ updates: each update is a pair $ (p_i, x_i) $, meaning $ a_{p_i} \leftarrow x_i $.
**Objective:**
After each update, output:
- $ -1 $ if no king-shaman exists,
- Otherwise, output any index $ j \in \{1, \dots, n\} $ such that $ a_j = \sum_{k=1}^{j-1} a_k $.
**Constraints:**
- All operations must be performed dynamically after each update.
- The prefix sums must be maintained efficiently.
---
**Formal Problem Statement:**
Let $ a \in \mathbb{Z}_{\geq 0}^n $, and define $ S_i = \sum_{j=1}^{i-1} a_j $ for $ i = 1, \dots, n $, with $ S_1 = 0 $.
A position $ i \in [n] $ is **valid** if $ a_i = S_i $.
Given an initial array $ a $ and $ q $ point updates $ (p_i, x_i) $, after each update, determine whether the set $ \{ i \in [n] : a_i = S_i \} $ is non-empty. If yes, output any such $ i $; otherwise, output $ -1 $.
---
**Mathematical Condition for King-Shaman at Index $ i $:**
$$
a_i = \sum_{j=1}^{i-1} a_j
$$
Equivalently:
$$
a_i = S_i \quad \text{where} \quad S_i = \sum_{j=1}^{i-1} a_j
$$
Note: $ S_i $ is the prefix sum up to index $ i-1 $, and changes dynamically with updates.
API Response (JSON)
{
"problem": {
"name": "E. Nastya and King-Shamans",
"description": {
"content": "Nastya likes reading and even spends whole days in a library sometimes. Today she found a chronicle of Byteland in the library, and it stated that there lived shamans long time ago. It is known that a",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 3000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF992E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Nastya likes reading and even spends whole days in a library sometimes. Today she found a chronicle of Byteland in the library, and it stated that there lived shamans long time ago. It is known that a...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Nastya 喜欢阅读，有时甚至整天待在图书馆里。今天她在图书馆里发现了一份比特兰的编年史，其中记载很久以前曾有萨满存在。已知在任何时刻，比特兰都恰好有一位萨满，总共有 #cf_span[n] 位萨满，按其生活顺序用整数从 #cf_span[1] 到 #cf_span[n] 编号。每位萨满都拥有一个魔法力量，现在可以用一个整数表示。\n\n编年史中列出了 #cf_span[n] 位萨满的力量值。此外，...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions:**\n\n- Let $ a = (a_1, a_2, \\dots, a_n) $ be a sequence of non-negative integers representing the magic powers of $ n $ shamans, indexed from 1 to $ n $.\n- For each $ i \\in \\{1, 2, \\dots,...",
"is_translate": false,
"language": "Formal"
}
]
}