Problem Description

AtColor Inc. has decided to sell gray paint with 1,000,001 shades ranging from $0$ (the darkest) to $1,000,000$ (the lightest).

However, given the vast number of shades, it was discovered that consumers cannot distinguish between subtle differences. Realizing this, AtColor Inc. decided to stop producing shades that do not sell well and instead sell only the most popular shade.

To achieve this, AtColor Inc. conducted a survey to find out how many consumers would buy the most popular shade. They asked consumers about the range of shades they would be willing to purchase, and received $n$ responses in the form of "I would buy any shade $x$ such that $a \leq x \leq b$."

Your task is to write a program that, based on this information, outputs the number of consumers who would buy the most popular shade of paint.

Input Format

The input is given from the standard input in the following format:

$n$ $a_{1}\ b_{1}$ $a_{2}\ b_{2}$ : $a_{n}\ b_{n}$

• The first line contains the number of survey responses $n\ (1 \leq n \leq 100,000)$.
• The following $n$ lines each contain two integers $a_i, b_i\ (0 \leq a_i \leq b_i \leq 1,000,000)$, representing the lower and upper bounds (inclusive) of the shade range for the $i$-th survey response, separated by a space.

Output Format

Output a single line with the number of consumers who would buy the most popular shade of paint. End the output with a newline.

Sample Input and Output

Sample Input #1

4
0 2
2 3
2 4
5 6

Sample Output #1

3

Sample Input #2

4
1000000 1000000
1000000 1000000
0 1000000
1 1000000

Sample Output #2

4

Notes/Hints

Partial Points

This problem has two datasets, each with partial points assigned:

• For the dataset 1 where $1 \leq n \leq 2,000$, a correct solution will earn 30 points.
• For the dataset 2 with no additional constraints, a correct solution will earn an additional 70 points.

Sample Explanation 1

• Shades $0, 1, 4, 5, 6$ can be purchased by 1 consumer each.
• Shade $2$ can be purchased by 3 consumers.
• Shade $3$ can be purchased by 2 consumers.
• No other shades can be purchased by anyone. Therefore, output $3$.

见题面 Input 部分

见题面 Output 部分