Description:
Farmer John has an array $$$a$$$ of length $$$n$$$. He also has a function $$$f$$$ with the following recurrence:
- $$$f(1) = \sqrt{a_1}$$$;
- For all $$$i > 1$$$, $$$f(i) = \sqrt{f(i-1)+a_i}$$$.
Note that $$$f(i)$$$ is not necessarily an integer.
He plans to do $$$q$$$ updates to the array. Each update, he gives you two integers $$$k$$$ and $$$x$$$ and he wants you to set $$$a_k = x$$$. After each update, he wants to know $$$\lfloor f(n) \rfloor$$$, where $$$\lfloor t \rfloor$$$ denotes the value of $$$t$$$ rounded down to the nearest integer.
Input Format:
The first line contains $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 2 \cdot 10^5$$$), the length of $$$a$$$ and the number of updates he will perform.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^{18}$$$).
The next $$$q$$$ lines each contain two integers $$$k$$$ and $$$x$$$ ($$$1 \leq k \leq n$$$, $$$0 \leq x \leq 10^{18}$$$), the index of the update and the element he will replace $$$a_k$$$ with.
Output Format:
For each update, output an integer, $$$\lfloor f(n) \rfloor$$$, on a new line.
Note:
In the first test case, the array after the first update is $$$[4, 14, 0, 7, 6]$$$. The values of $$$f$$$ are:
- $$$f(1)=2$$$;
- $$$f(2)=4$$$;
- $$$f(3)=2$$$;
- $$$f(4)=3$$$;
- $$$f(5)=3$$$.
Since $$$\lfloor f(5) \rfloor = 3$$$, we output $$$3$$$.
The array after the second update is $$$[3, 14, 0, 7, 6]$$$. The values of $$$f$$$, rounded to $$$6$$$ decimal places, are:
- $$$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$$$.
Since $$$\lfloor f(5) \rfloor = 2$$$, we output $$$2$$$.