주기 함수 (Hard)

이 문제는 [주기 함수 (Easy)] 문제와 입력 조건이 다르다.

주기 함수(週期函數, 영어: periodic function)는 함숫값이 일정 주기마다 되풀이되는 함수이다. 구체적으로, 모든 $x$에 대해 $f(x+p)=f(x)$인 양수 $p$가 존재하면 함수 $f(x)$를 주기 함수라 하고, $p$를 주기라 한다. 같은 함수라도 주기는 여러 값을 가질 수 있다. 예를 들어 $f(x) = \sin x$인 경우 모든 양의 정수 $n$에 대해 $2n\pi$가 주기가 될 수 있다.

주기 함수는 정적분을 계산할 때 편리하다. 주기만큼 적분 구간을 옮겨도 값이 같기 때문이다. 예를 들어 $\sin$ 함수의 주기는 $2\pi$이므로 $\int_0^\pi \sin x\,dx = \int_{2\pi}^{3\pi} \sin x\,dx$이다.

두영이는 매일 이안이가 모르는 주기 함수를 가져와서, 임의의 구간의 적분값을 주고 주어진 다른 구간의 적분값을 찾아 달라고 한다. 매일 문제를 푸느라 지친 이안이는 답을 자동으로 구해 주는 프로그램을 만들고자 한다.

첫 번째 줄에 적분값이 주어질 구간의 길이 $L$이 주어진다.

두 번째 줄에 구간의 적분값 $L$개가 공백으로 구분되어 주어진다. $1 \le i \le L$인 정수 $i$에 대해 $i$번째 수는 $\int_{i-1}^i f(x)\,dx$를 나타낸다.

세 번째 줄에 구하고자 하는 구간의 위치 $a$와 $b$가 공백으로 구분되어 주어진다.

$\int_a^b f(x)\,dx$의 값을 한 줄에 출력한다.

• $2 \le L \le 3\times 10^5$
• $-10^9 \le a \le b \le 10^9$
• 모든 적분값의 절댓값은 $10^9$보다 작거나 같다.
• 모든 입력은 정수이다.
• 주기의 길이는 $\frac{L}{2}$ 이하의 정수임이 보장된다.