Intuidiff II

Intuidiff는 diff를 대신하는 프로그램으로, 원본 문서와 수정본 문서 사이에서 글이 어디로 옮겨졌는지 보여준다.

전처리를 마치면 원본 문서는 서로 겹치지 않는 여러 부분 문자열로 나뉘고, 각 부분 문자열에 서로 다른 색을 칠한다. 수정본 문서에도 같은 색을 칠하면 긴 부분 문자열이 어디로 옮겨갔는지 보인다. 한 색이 수정본 문서에는 여러 번 나올 수 있지만, 원본 문서에는 한 번만 나온다.

그림 I.1: Intuidiff가 만든 전체 색칠.

수정본 문서의 모든 글자에 색을 칠하면 오히려 눈에 거슬리므로, 색칠한 부분 문자열 중 일부만 강조해서 남긴다. 강조하지 않은 부분 문자열의 글자는 색 없이 그대로 둔다. 수정본 문서를 왼쪽부터 읽었을 때 강조하지 않은 글자의 순서가 원본 문서에서의 순서와 같아야 한다.

다시 말해 강조하지 않기로 한 부분 문자열을 수정본 문서에 나온 순서대로 늘어놓으면, 원본 문서에서의 구간이 뒤로 갈수록 커져야 한다. 앞의 부분 문자열이 원본 문서의 구간 $[a, b]$를 차지하고 그다음 부분 문자열이 구간 $[c, d]$를 차지한다면 $b < c$이다.

그림 I.2: Intuidiff가 만들어야 하는 색칠.

강조하지 않은 글자 수를 최대로 하고, 그 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 수정본 문서에서 색칠한 부분 문자열의 개수 $n$ ($1 \le n \le 100000$)이 주어진다. 다음 $n$개 줄에는 두 정수 $a$와 $b$ ($0 \le a \le b \le 10^9$)가 주어진다. 이 중 $i$번째 줄은 수정본 문서를 왼쪽부터 읽었을 때 $i$번째로 나오는 부분 문자열을 나타내고, 이 부분 문자열은 원본 문서의 인덱스 $a$부터 $b$까지의 글자로 이루어진다.

두 부분 문자열이 일부만 겹치는 경우는 없다. 두 부분 문자열이 같은 인덱스를 하나라도 포함하면 두 부분 문자열은 완전히 같다.

수정본 문서에서 강조하지 않은 글자 수의 최댓값을 출력한다.

첫 번째 예제는 그림 I.1의 "After" 문단이다. 강조하지 않은 글자 154개는 그림 I.2에 나와 있다.