Background

fuwa↑ fuwa↑ fuwa↑ fuwa↑.

Herta starts using the trendy chat app BassLine, and of course the first step is to add friends. Adding friends requires both confirming that you and the other person share common interests, and being able to add enough friends. Herta abstracts this into the following problem and asks you to solve it.

Problem Description

In this problem, an interval $[l,r]$ refers to the set of all integers that are greater than or equal to $l$ and less than or equal to $r$. For example, $[3,3]$ represents $\{3\}$, and $[3,7]$ represents $\{3,4,5,6,7\}$.

You are given $n$ intervals. The $i$-th interval is $[l_i,r_i]$.

You need to choose two integers $x \le y$ such that:

• For every interval $[l_i,r_i]$ ($1 \le i \le n$), one of the following two conditions holds:
  1. $[x,y]$ is contained in $[l_i,r_i]$. In other words, $[x,y]\cap[l_i,r_i]=[x,y]$.
  2. $[x,y]$ is disjoint from $[l_i,r_i]$. In other words, $[x,y]\cap[l_i,r_i]=\varnothing$.

If there are $k$ intervals that satisfy condition 1, then your score is $k(y-x)$. Output the maximum possible score.

Input Format

The first line contains a positive integer $n$.

The next $n$ lines each contain two numbers $l_i, r_i$, describing an interval.

Output Format

Output one non-negative integer representing the answer.

4
1 3
4 7
5 9
7 10

2

Hint

Sample Explanation

For the sample, $[5,6]$ is one of the optimal intervals. It is contained in $[4,7]$ and $[5,9]$, and is disjoint from $[1,3]$ and $[7,10]$. In this case $k=2$, so the answer is $2\times(6-5)=2$. $[1,3]$ is also an optimal interval.

$[5,7]$ is not a valid interval because it intersects with $[7,10]$ and is not contained in $[7,10]$ either.

Constraints

For all testdata, it is guaranteed that $1 \le n \le 3 \times {10}^5$ and $1 \le l_i \le r_i \le 3 \times {10}^5$.

• Subtask 1 (20 points): $n,l_i,r_i \le 10$.
• Subtask 2 (20 points): $n \le {10}^3$.
• Subtask 3 (20 points): $l_i, r_i \le {10}^3$.
• Subtask 4 (40 points): No special constraints.

Translated by ChatGPT 5