차이 제한 수열 조정

길이가 $N$인 정수 수열 $A_1, A_2, \cdots, A_N$이 주어진다. 각 $i=2, 3, \cdots, N$에 대해 정수 $L_i$, $R_i$도 주어진다.

길이가 $N$인 정수 수열 $X_1, X_2, \cdots, X_N$을 다음 조건을 만족하도록 정하려고 한다.
\[ L_i \le X_i-X_{i-1} \le R_i \qquad (2 \le i \le N). \]

$\sum_{i=1}^N \lvert X_i-A_i \rvert$의 최솟값을 구해 보자.

첫 번째 줄에 정수 $N$이 주어진다. $(1 \le N \le 200\,000)$

두 번째 줄에 수열의 원소 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(-10^9 \le A_i \le 10^9)$

세 번째 줄부터 $N-1$개의 줄에 걸쳐 $i=2, 3, \cdots, N$의 순서로 두 정수 $L_i$, $R_i$가 공백으로 구분되어 주어진다. $(-10^6 \le L_i \le R_i \le 10^6)$

$\sum_{i=1}^N \lvert X_i-A_i \rvert$의 최솟값을 출력한다.

첫 번째 예제에서는 $X_1=0$, $X_2=1$, $X_3=0$으로 정하면 합이 $4$이며, 이보다 작게 만들 수 없다.