Ami có một dãy số, là một người thích sự mới lạ, cậu sẽ thay đổi giá trị của 1 phần tử bất kì trong dãy q lần. Với mỗi lần thay đổi như thế, Ami muốn tính toán phần tử trung vị hiện tại là bao nhiêu, các bạn hãy tính toán xem nhé.
Phần tử trung vị của một dãy số độ dài n là phần tử ở vị trí (n+1) div 2 sau khi sắp xếp dãy số tăng dần (dãy số được đánh số từ 1).
Dữ liệu vào
Dòng đầu tiên là 2 số nguyên dương n và q (n,q <= 3*105) lần lượt là độ dài dãy số và số truy vấn.
Dòng tiếp theo là n số nguyên dương ai (ai <= 3*105) là dãy số được cho.
Dữ liệu ra
Gồm một dòng gồm q số, số thứ i là phần tử trung vị của dãy số sau i truy vấn đầu tiền.
Input
5 3
1 2 3 4 5
1 2
2 3
3 4
Output
3 3 4
Giải thích
Ở lần thay đổi đầu tiên, dãy số mới là 2 2 3 4 5. Phần tử trung vị là 3.
Ở lần thay đổi tiếp theo, dãy số mới là 2 3 3 4 5. Phần tử trung vị là 3.
Ở lần thay đổi cuối, dãy số mới là 2 3 4 4 5. Phần tử trung vị là 4.