,3,10]). Median of the array [1,5,8,1] is 1 (i.e.At first, you're given an empty sequence. There are N operations. The i-th operation contains two integers. into the sequence. After each operation, you need to find the median of the sequence.
Let median of some array be the number which would stand in the middle of this array if it was sorted beforehand. If the array has even length let median be smallest of of two middle elements. For example, median of the array [10,3,2,3,2] is 3 (i.e. [2,2,underline{3},3,10] [2,2, 3 ,3,10]). Median of the array [1,5,8,1] is 1 (i.e. [1,underline{1},5,8] [1, 1 ,5,8]). At first, you're given an empty sequence. There are N operations. The i-th operation contains two integers L_i L i and R_i R i . This means that adding R_i-L_i+1 R i −L i +1 integers L_i, L_i+1, ... , R_i L i ,L i +1,...,R i into the sequence. After each operation, you need to find the median of the sequence.