Sadə ədədlərlə azaltma

Giriş

Birinci sətirdə bir tam ədəd $t$ ( $1 \leq t \leq 1 0^{4}$ 1 \le t \le 10^4) — test hallarının sayı verilir.

Hər test halının birinci sətrində iki tam ədəd $n$ və $q$ ( $1 \leq n, q \leq 5 \cdot 1 0^{5}$ 1 \le n, q \le 5 \cdot 10^5) — massivin ölçüsü və yeniləmələrin sayı verilir.

İkinci sətirdə $n$ tam ədəd $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \dots, a_n ( $1 \leq a_{i} \leq 1 0^{7}$ 1 \le a_i \le 10^7) — massivin ilkin elementləri verilir.

Sonra $q$ sətir gəlir. Hər sətirdə yeniləməni təsvir edən iki tam ədəd $i d x$ və $x$ ( $1 \leq i d x \leq n$ 1 \le idx \le n, $1 \leq x \leq 1 0^{7}$ 1 \le x \le 10^7) verilir.

Bütün test hallarında $n$ -lərin cəminin $5 \cdot 1 0^{5}$ 5 \cdot 10^5-i, $q$ -ların cəminin isə $5 \cdot 1 0^{5}$ 5 \cdot 10^5-i aşmayacağı təmin edilir.

Çıxış

Hər test halı üçün $q$ sətir çıxarın. $j$ -ci sətirdə bir tam ədəd — $j$ -ci yeniləmədən sonra massivin bütün elementlərini $1$ -ə bərabər etmək üçün Fadiyə lazım olan minimum əməliyyat sayı olmalıdır.

Nümunələr

Nümunə 1

Loading

Qeyd

Birinci test halında ilkin massiv $a = [12, 6, 12, 2]$ a = [12, 6, 12, 2]-dir.

Birinci yeniləmədən sonra massiv $a = [12, 1, 12, 2]$ a = [12, 1, 12, 2] olur. Minimum əməliyyat sayı $6$ -dır:

$a_{1}$ a_1-ə $3$ əməliyyat tətbiq edilir ( $p \in {2, 2, 3}$ p \in \{2, 2, 3\}).
$[3, 4]$ alt parçasına $3$ əməliyyat tətbiq edilir. $p = 2$ p=2 əməliyyatı eyni anda həm $a_{3}$ a_3-ə, həm də $a_{4}$ a_4-ə tətbiq olunur, $p \in {2, 3}$ p \in \{2, 3\} olan əməliyyatlar isə yalnız $a_{3}$ a_3-ə tətbiq olunur.

İkinci yeniləmədən sonra massiv $a = [12, 1, 2, 2]$ a = [12, 1, 2, 2] olur. Minimum əməliyyat sayı $4$ -dür:

$a_{1}$ a_1-ə $3$ əməliyyat tətbiq edilir ( $p \in {2, 2, 3}$ p \in \{2, 2, 3\}).
$[3, 4]$ alt parçasına $1$ əməliyyat tətbiq edilir ( $p = 2$ p=2).

İkinci test halında massiv ilkin olaraq $a = [30, 30, 30]$ a = [30, 30, 30]-dur. Birinci yeniləmədən sonra o, $a = [30, 1, 30]$ a = [30, 1, 30] olur. $a_{2} = 1$ a_2 = 1 olduğuna görə qalan elementlər əməliyyatları bölüşə bilmir. $a_{1}$ a_1-ə $3$ əməliyyat ( $p \in {2, 3, 5}$ p \in \{2, 3, 5\}) və $a_{3}$ a_3-ə $3$ əməliyyat tətbiq edirik, ümumilikdə $6$ əməliyyat.

Bal hesablama

Altməsələ $1$ ( $100$ bal): $\sum n \leq 2000$ \sum n \le 2000 və $\sum q \leq 2000$ \sum q \le 2000.
Altməsələ $2$ ( $100$ bal): $1 \leq a_{i}, x \leq 1000$ 1 \le a_i, x \le 1000.
Altməsələ $3$ ( $200$ bal): Əlavə məhdudiyyət yoxdur.