33957번 - Golden Section Search

먼 훗날, PPC는 1학기와 2학기에 한 번씩, 1년에 총 2번 열리게 되었다.

PPC 출제진은 $N$개의 문제를 미리 준비해 두었다. 각 문제는 $1$번부터 $N$번까지의 번호로 구분된다. 각 문제의 난이도 하한과 상한은 이미 정해져 있지만, 정확한 난이도는 정해져 있지 않다. $i$번 문제의 난이도 하한은 $L_i$, 난이도 상한은 $R_i$이다.

PPC 출제진은 미리 준비해 둔 $N$개의 문제를 정확히 두 부분으로 나눠 각 대회에 출제하려 한다. 전체 문제 중 앞쪽 일부를 1학기 대회에, 남은 뒷부분을 2학기 대회에 배정할 것이다. 이때 학생들이 어느 대회에 출전해야 하는지 고민하지 않도록 두 대회의 난이도를 같게 하려 한다. 대회의 난이도란 대회에 배정된 문제들의 난이도를 모두 더한 값이다.

두 대회의 난이도를 같게 하기 위해 PPC 출제진은 문제를 황금 분할하기로 했다. 구체적으로 아래와 같이 문제를 나누는 방법을 황금 분할이라 한다.

• 각 대회에 적어도 $1$문제 이상이 출제되어야 하며 각 대회에 쓰이는 문제들의 번호는 연속해야 한다. 즉, $1$ 이상 $N$ 미만의 정수 $x$에 대해 $1$번 문제부터 $x$번 문제까지는 1학기 대회에, $x+1$번 문제부터 $N$번 문제까지는 2학기 대회에 출제한다.
• 두 대회의 난이도가 같도록 각 문제의 난이도를 정할 수 있어야 한다. 즉, $\sum_{1\le i\le x}D_i=\sum_{x<i\le N}D_i$을 만족하도록 $i$번 문제의 난이도 $D_i$를 정할 수 있어야 한다. 이때 $D_i$는 $L_i$ 이상 $R_i$ 이하의 정수여야 한다.

두 황금 분할이 다름은 각 분할에서 1학기 대회에 사용되는 문제의 수가 서로 다름을 의미한다. 배정된 난이도가 달라도 $x$값이 같다면 같은 분할이다.

예를 들어 $N=3$, $L=[1,1,1]$, $R=[2,2,2]$인 경우를 생각하자. $x=1$인 경우에는 난이도를 $[2,1,1]$로, $x=2$인 경우에는 난이도를 $[1,1,2]$로 정하면 황금 분할의 조건을 만족하므로 서로 다른 황금 분할은 $2$개이다.

서로 다른 황금 분할의 개수를 구하여라.

첫 번째 줄에 문제의 수 $N$이 주어진다. ($2 \leq N \leq 100\,000$)

두 번째 줄부터 $N$개의 줄에 걸쳐, $i+1$번째 줄에 $i$번째 문제의 난이도 하한과 상한을 나타내는 두 정수 $L_i$, $R_i$가 공백으로 구분되어 주어진다. $(0 \le L_i \le R_i \le 1000)$

서로 다른 황금 분할의 개수를 구하여라.