F. Любимая функция Фермера Джона
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
ΩΩPARTS - Camellia
⠀

У Фермера Джона есть массив $$$a$$$ длины $$$n$$$. У него также есть функция $$$f$$$ со следующим рекуррентным соотношением:

  • $$$f(1) = \sqrt{a_1}$$$;
  • Для всех $$$i > 1$$$, $$$f(i) = \sqrt{f(i-1)+a_i}$$$.

Обратите внимание, что $$$f(i)$$$ не обязательно является целым числом.

Он планирует сделать $$$q$$$ обновлений массива. При каждом обновлении он дает вам два целых числа $$$k$$$ и $$$x$$$ и хочет, чтобы вы установили $$$a_k = x$$$. После каждого обновления он хочет узнать $$$\lfloor f(n) \rfloor$$$, где $$$\lfloor t \rfloor$$$ обозначает значение $$$t$$$, округленное вниз до ближайшего целого числа.

Входные данные

Первая строка содержит $$$n$$$ и $$$q$$$ ($$$1 \leq n, q \leq 2 \cdot 10^5$$$) — длину $$$a$$$ и количество обновлений, которые он будет выполнять.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^{18}$$$).

Следующие $$$q$$$ строк содержат по два целых числа $$$k$$$ и $$$x$$$ ($$$1 \leq k \leq n$$$, $$$0 \leq x \leq 10^{18}$$$) — индекс обновления и элемент, на который он заменит $$$a_k$$$.

Выходные данные

После каждого обновления выведите целое число $$$\lfloor f(n) \rfloor$$$ в отдельной строке.

Примеры
Входные данные
5 6
0 14 0 7 6
1 4
1 3
2 15
4 1
5 2
5 8
Выходные данные
3
2
3
2
1
3
Входные данные
15 10
3364 1623 5435 7 6232 245 7903 3880 9738 577 4598 1868 1112 8066 199
14 4284
14 8066
6 92
6 245
2 925
2 1623
5 176
5 6232
3 1157
3 5435
Выходные данные
16
17
16
17
16
17
16
17
16
17
Входные данные
2 2
386056082462833225 923951085408043421
1 386056082462833225
1 386056082462833224
Выходные данные
961223744
961223743
Входные данные
13 10
31487697732100 446330174221392699 283918145228010533 619870471872432389 11918456891794188 247842810542459080 140542974216802552 698742782599365547 533363381213535498 92488084424940128 401887157851719898 128798321287952855 137376848358184069
3 283918145228010532
3 283918145228010533
1 2183728930312
13 1000000000000000000
10 1000000000000000000
9 1000000000000000000
8 1000000000000000000
7 1000000000000000000
6 1000000000000000000
5 1000000000000000000
Выходные данные
370643829
370643830
370643829
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
Примечание

В первом примере массив после первого обновления имеет вид $$$[4, 14, 0, 7, 6]$$$. Значения $$$f$$$ следующие:

  • $$$f(1)=2$$$;
  • $$$f(2)=4$$$;
  • $$$f(3)=2$$$;
  • $$$f(4)=3$$$;
  • $$$f(5)=3$$$.

Поскольку $$$\lfloor f(5) \rfloor = 3$$$, ответом будет $$$3$$$.

Массив после второго обновления имеет вид $$$[3, 14, 0, 7, 6]$$$. Значения $$$f$$$, округленные до $$$6$$$ знаков после запятой, таковы:

  • $$$f(1)\approx 1.732051$$$;
  • $$$f(2)\approx 3.966365$$$;
  • $$$f(3)\approx 1.991573$$$;
  • $$$f(4)\approx 2.998595$$$;
  • $$$f(5)\approx 2.999766$$$.

Поскольку $$$\lfloor f(5) \rfloor = 2$$$, ответом будет $$$2$$$.