Demonstrations

This Sunday, Bytetown celebrates The Byte Day, one of the most important annual Bytelandian holidays. This year it will not stay a quiet village fete.

Bytetown citizens are sharply divided over one question. Some believe that by tradition a byte must always be eight bits. Progress supporters would rather have roomier 16 bit bytes. Others take a much stiffer line and want to declare that a byte has only four bits. There are also smaller subversive movements whose members argue that the number of bits in a byte must not be a power of two, or that it need not even be an even number. Every one of these societies plans its own demonstration to win the citizens over.

Many citizens worry that so many demonstrations will disturb The Byte Day celebrations. The Lord Mayor decided that banning some of the demonstrations would win him wide public support. Such decisions cause controversy, so he will cancel at most two demonstrations, and he wants to pick them so that the total time during which a demonstration is going on somewhere in the city becomes as short as possible. Time when several demonstrations overlap counts once. Tell the Lord Mayor by how much that total time can drop.

The first line contains one integer $n$ ($2 \le n \le 500\,000$), the number of planned demonstrations. Each of the next $n$ lines describes one demonstration. The $i$-th of those lines contains two integers $a_i$ and $b_i$ ($0 \le a_i < b_i \le 10^9$), which mean that the $i$-th demonstration begins $a_i$ byteminutes after sunrise and ends $b_i$ byteminutes after sunrise.

Print exactly one non-negative integer, the largest amount of time the demonstrations can be shortened by when the Lord Mayor cancels at most two of them.

In the example the Lord Mayor should refuse permits for the first and the fourth demonstration.