Beauty of the sequence

Yeongseon planted $N$ trees in a row. The trees are numbered $0$ through $N-1$. When tree $i$ is fully grown its height is an integer between $low_i$ and $high_i$, inclusive, and every integer in that range is equally likely. The heights of different trees are chosen independently.

Yeongseon likes zigzag sequences. A zigzag sequence is defined as follows.

• Every sequence of length $1$ is a zigzag sequence.
• A sequence $(A, B)$ of length $2$ is a zigzag sequence if $A \ne B$.
• A sequence $(A, B, C)$ of length $3$ is a zigzag sequence if $A < B$ and $B > C$, or if $A > B$ and $B < C$.
• A sequence $(A_0, A_1, \dots, A_{L-1})$ of length $L > 3$ is a zigzag sequence if each of the triples $(A_0, A_1, A_2)$, $(A_1, A_2, A_3)$, $\dots$, $(A_{L-3}, A_{L-2}, A_{L-1})$ is a zigzag sequence.

The beauty of a sequence is the sum of the absolute differences of adjacent elements, so the beauty of $(A_0, A_1, \dots, A_{L-1})$ is $|A_0 - A_1| + |A_1 - A_2| + \dots + |A_{L-2} - A_{L-1}|$. A sequence of length $1$ has beauty $0$.

Once the trees are fully grown, Yeongseon writes down the heights of trees $0$ through $N-1$ in order. If the written sequence is a zigzag sequence she leaves it alone. Otherwise she erases some of the numbers so that what remains is a zigzag sequence. The remaining numbers keep their original order. When several ways of erasing produce a zigzag sequence, she picks one whose beauty is largest. The sequence she ends up with is called the result sequence.

Write a program that computes the expected beauty of the result sequence.

The first line contains the number of trees $N$. ($1 \le N \le 50$)

Each of the next $N$ lines contains $low_i$ and $high_i$ for tree $i$, separated by a space. ($1 \le low_i \le high_i \le 100000$)

Print the expected beauty of the result sequence with exactly six digits after the decimal point. Round at the seventh digit after the decimal point, rounding a half up, and pad with zeros so that six digits are always present. For example, if the answer is $8$, print 8.000000.

Suppose there are $3$ trees and all three height ranges are $1$ to $2$. Then there are $8$ possible outcomes.

• $(1, 1, 1)$ and $(2, 2, 2)$ need two numbers erased before they become zigzag sequences, and the beauty is $0$.
• $(1, 1, 2)$, $(2, 2, 1)$, $(1, 2, 2)$ and $(2, 1, 1)$ only need the middle number erased, and the beauty is $1$.
• $(1, 2, 1)$ and $(2, 1, 2)$ need nothing erased, and the beauty is $2$.

The expected value is therefore $\frac{4}{8} \times 1 + \frac{2}{8} \times 2 = 1$.