새 급여
면접 대비시간 제한2초메모리 제한512 MB
포함 관계인 닫힌 구간에서 급여를 무작위로 뽑을 때 쌍별 급여 차이의 총합 기댓값을 구해 N의 제곱으로 나눈 값을 출력합니다.
문제
이런! 최근 선거로 "무작위 법률"당이 정권을 잡았다. 부르주아 씨의 회사에 나쁜 결과가 생길 참이다. 회사는 방금 새 급여를 계산하는 방식을 승인했다. 회사에는 N명의 직원이 있고, 직원 i의 급여는 구간 [Li, Ri]에서 균등하게 뽑은 수로 정해진다. 회사는 이미 어느 직원이 가장 효율적인지 파악했으므로, 각 i ∈ [2, N]에 대해 Li−1 ≤ Li이고 Ri−1 ≤ Ri임을 안다. 다만 우연에 따라 직원 i − 1이 직원 i보다 더 큰 급여를 받게 될 수도 있다.
새 정부는 동료보다 적은 급여를 받은 직원은 그 차액만큼 회사를 고소할 수 있다는 법을 만들었다. 더 심한 것은, 더 많은 급여를 받은 모든 직원을 상대로 고소할 수 있다는 점이다. 예를 들어 앨리스, 밥, 찰리가 각각 1, 3, 7 코인의 급여를 받았다면, 밥은 찰리를 상대로 4 코인을 고소할 수 있고, 앨리스는 밥 때문에 2 코인, 찰리 때문에 6 코인을 고소할 수 있다. 회사가 배상해야 할 총액은 12이다.
정확한 급여는 아직 알려지지 않았지만, 부르주아 씨는 회사가 배상해야 할 금액의 기댓값을 알고 싶어 한다. 답이 매우 클 수 있으므로, 답을 N2로 나눈 값을 출력하라.
입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100 000) 다음 N개 줄에 각각 두 실수 Li와 Ri가 주어진다. (1 ≤ Li ≤Ri ≤ 106) 입력의 모든 실수는 소수점 아래 자리가 최대 6자리이다.
출력
기댓값을 N2로 나눈 값을 한 개 출력한다. 절대 오차 또는 상대 오차가 10−4보다 작으면 정답으로 인정된다.