Median Duration after Performance Swaps

You are organizing a festival with n performances, each having a unique duration. After each swap of durations between two performances, you are required to compute the median duration of all performances. The median is defined as follows:

If there are an odd number of elements, the median is the middle element of the sorted list. If there are an even number of elements, the median is given by the formula: \(\frac{d_{\frac{n}{2}} + d_{\frac{n}{2}+1}}{2}\).

Each query permanently swaps the durations, and the updated list is used for subsequent queries.

inputFormat

The first line of input contains two integers n and m, representing the number of performances and the number of queries, respectively. The second line contains n integers representing the durations of the performances. Each of the next m lines contains two integers a and b (1-indexed) which specify that the durations at positions a and b should be swapped.

outputFormat

Output m lines, each representing the median duration after performing the corresponding swap. For an odd number of durations, output the middle element. For an even number of durations, output (\frac{d_{\frac{n}{2}}+d_{\frac{n}{2}+1}}{2}).## sample

5 3
1 3 5 7 9
1 5
3 4
2 5

5
5
5