Score : 500 points
There are N integers X_1, X_2, \cdots, X_N, and we know that A_i \leq X_i \leq B_i. Find the number of different values that the median of X_1, X_2, \cdots, X_N can take.
The median of X_1, X_2, \cdots, X_N is defined as follows. Let x_1, x_2, \cdots, x_N be the result of sorting X_1, X_2, \cdots, X_N in ascending order.
Input is given from Standard Input in the following format:
N A_1 B_1 A_2 B_2 : A_N B_N
Print the answer.
2 1 2 2 3
3
If X_1 = 1 and X_2 = 2, the median is \frac{3}{2};
if X_1 = 1 and X_2 = 3, the median is 2;
if X_1 = 2 and X_2 = 2, the median is 2;
if X_1 = 2 and X_2 = 3, the median is \frac{5}{2}.
Thus, the median can take three values: \frac{3}{2}, 2, and \frac{5}{2}.
3 100 100 10 10000 1 1000000000
9991