31807번 - 주기 함수 (Hard)

문제

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

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

주기 함수는 정적분을 계산할 때 용이하다. 주기만큼 적분 구간을 바꾸어도 그 값은 동일하기 때문이다. 예를 들어 $\sin$ 함수의 경우 주기가 2ドル\pi$이므로 $\displaystyle\int_0^\pi \sin x dx = \int_{2\pi}^{3\pi} \sin x dx$이다.

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

입력

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

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

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

출력

$\displaystyle\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$보다 작거나 같다.
• 모든 입력은 정수이다.
• 주기의 길이는 $\displaystyle\frac{L}{2}$ 이하의 정수임이 보장된다.

힌트