Dynamic Median Updates

You are given a sequence of n integers. You are also given q queries. Each query consists of two integers i and x. For each query, update the element at index i of the sequence with x, and then compute the median of the new sequence.

The median is defined as follows:

If the sequence sorted in non-decreasing order is \(a_1, a_2, \dots, a_n\), then:

• If \(n\) is odd, the median is \(a_{\lceil n/2 \rceil}\).
• If \(n\) is even, the median is \(\frac{a_{n/2} + a_{(n/2)+1}}{2}\).

Note: The indexing of the sequence is 0-based.

inputFormat

The input is read from standard input (stdin) and has the following format:

<n> <q>
<a1> <a2> ... <an>
<i1> <x1>
<i2> <x2>
... (q queries in total)

Here, n is the number of elements, q is the number of queries, and for each query, i is the 0-based index of the element to update with value x.

outputFormat

For each query, output the median of the updated sequence on a new line to standard output (stdout). If the median is an integer, output it without any decimal point; otherwise, output the floating point number.

## sample

5 1
1 3 5 7 9
2 4

4

</p>