CF1942F Farmer John's Favorite Function

[ΩΩPARTS - Camellia](https://soundcloud.com/user-838515264/camellia-parts-ooparts) ⠀ 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.

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.

For each update, output an integer, $ \lfloor f(n) \rfloor $ , on a new line.

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 $ .