Count Median

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.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq B_i \leq 10^9
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N A_1 B_1 A_2 B_2 : A_N B_N

Output

Print the answer.

Examples

Input

2 1 2 2 3

Output

3

Input

3 100 100 10 10000 1 1000000000

Output

9991

inputFormat

input are integers.

Input

Input is given from Standard Input in the following format:

N A_1 B_1 A_2 B_2 : A_N B_N

outputFormat

Output

Print the answer.

Examples

Input

2 1 2 2 3

Output

3

Input

3 100 100 10 10000 1 1000000000

Output

9991

样例

3
100 100
10 10000
1 1000000000

9991