수열의 아름다움

영선이는 나무 $N$그루를 일렬로 심었다. 나무에는 $0$번부터 $N-1$번까지 번호가 붙어 있다. $i$번 나무가 다 자라면 높이는 $low_i$ 이상 $high_i$ 이하의 정수가 되고, 이 범위에 속한 각 정수가 나올 확률은 모두 같다. 나무의 높이는 서로 독립으로 정해진다.

영선이는 교차 수열을 좋아한다. 교차 수열의 정의는 다음과 같다.

• 길이가 $1$인 수열은 교차 수열이다.
• 길이가 $2$인 수열 $(A, B)$는 $A \ne B$이면 교차 수열이다.
• 길이가 $3$인 수열 $(A, B, C)$는 $A < B$이면서 $B > C$이거나, $A > B$이면서 $B < C$이면 교차 수열이다.
• 길이가 $L > 3$인 수열 $(A_0, A_1, \dots, A_{L-1})$은 연속한 세 원소로 이루어진 $(A_0, A_1, A_2)$, $(A_1, A_2, A_3)$, $\dots$, $(A_{L-3}, A_{L-2}, A_{L-1})$이 모두 교차 수열일 때 교차 수열이다.

수열의 아름다움은 인접한 두 원소의 차이의 절댓값을 모두 더한 값이다. 즉 $(A_0, A_1, \dots, A_{L-1})$의 아름다움은 $|A_0 - A_1| + |A_1 - A_2| + \dots + |A_{L-2} - A_{L-1}|$이다. 길이가 $1$인 수열의 아름다움은 $0$이다.

나무가 다 자란 뒤에 영선이는 $0$번 나무부터 $N-1$번 나무까지의 높이를 순서대로 공책에 적는다. 적은 수열이 교차 수열이면 그대로 둔다. 교차 수열이 아니면 수를 몇 개 지워서 교차 수열로 만든다. 남는 수는 원래 순서를 지킨다. 교차 수열을 만드는 방법이 여럿이면 아름다움이 가장 큰 쪽을 고른다. 이렇게 얻은 수열을 결과 수열이라고 한다.

결과 수열의 아름다움의 기댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 나무의 수 $N$이 주어진다. ($1 \le N \le 50$)

둘째 줄부터 $N$개의 줄에 걸쳐 $i$번 나무의 $low_i$와 $high_i$가 공백으로 구분되어 주어진다. ($1 \le low_i \le high_i \le 100000$)

결과 수열의 아름다움의 기댓값을 소수점 아래 여섯째 자리까지 출력한다. 소수점 아래 일곱째 자리에서 반올림하고, 자리가 남으면 $0$으로 채워 여섯 자리를 정확히 맞춘다. 예를 들어 답이 $8$이면 8.000000을 출력한다.

나무가 $3$그루이고 세 나무의 높이 범위가 모두 $1$ 이상 $2$ 이하이면 다 자란 결과는 $8$가지다.

• $(1, 1, 1)$과 $(2, 2, 2)$는 수를 두 개 지워야 교차 수열이 되고, 아름다움은 $0$이다.
• $(1, 1, 2)$, $(2, 2, 1)$, $(1, 2, 2)$, $(2, 1, 1)$은 가운데 수를 지우면 되고, 아름다움은 $1$이다.
• $(1, 2, 1)$과 $(2, 1, 2)$는 지울 필요가 없고, 아름다움은 $2$이다.

따라서 기댓값은 $\frac{4}{8} \times 1 + \frac{2}{8} \times 2 = 1$이다.