Marking All Items on a Circular Spinner

Consider a circular spinner with (n) items arranged in a circle, numbered from (1) to (n). Each item (i) appears at time (T_i). At time (0), you may choose any item as a starting position (s_0). Then, if at time (i) you have chosen item (s_i), at time (i+1) you are allowed to either remain at the current item or move to the next item in the circle (if (s_i = n), the next item is (1); otherwise, it is (s_i+1)). At every time step (including time (0)), if the item you choose has already appeared (i.e. if the current time (i) is at least its appearance time (T_{s_i})), then you mark that item. Under an optimal strategy, your goal is to mark all (n) items as early as possible.

However, the twist is that the appearance times (T_i) may change over time. There are (m) modifications; in each modification, the appearance time of one item is updated. After every update, you are required to compute the minimum time by which it is possible to mark all items if you choose your moves optimally.

Formally, for a fixed starting position (r) ((1 \leq r \leq n)), define a function (f(r)) as follows:

[ \begin{aligned} \text{Let } t_0 &= \max(0, T_r). \ \text{For } j &= 1,2,\ldots,n-1, \quad t_j = \max(t_{j-1}+1, T_{((r+j-1) \mod n)+1}). \end{aligned} ]

The answer for the current appearance times is (\min_{1 \leq r \leq n} f(r)).

You are given the initial (T_i) for (i=1,\ldots,n). Then, you are given (m) modifications. Each modification consists of two integers (i) and (newTime), meaning that (T_i) is updated to (newTime). After each modification, output the minimum time needed to mark all items under an optimal strategy.

Note: All formulas are written in (\LaTeX) format.

inputFormat

The first line contains two integers (n) and (m) separated by a space, indicating the number of items and the number of modifications respectively. The second line contains (n) space-separated integers (T_1, T_2, \ldots, T_n), the initial appearance times of the items. Then (m) lines follow. Each of these lines contains two integers (i) and (newTime), indicating that the appearance time of item (i) is updated to (newTime). (1 \le i \le n).

outputFormat

For each modification, output a line containing one integer: the minimum time by which all items can be marked under an optimal strategy after applying that modification.

sample

3 3
3 1 4
2 2
3 1
1 0

5
4
3