출하 묶음의 후보 수

문제

한 공장 생산 라인은 짧은 작업 구간마다 완성된 부품을 상자에 담는다. 오늘은 N개의 작업 구간이 있었고, i번째 작업 구간에서 완성된 부품 수는 A_i개이다. 각 작업 구간에서는 적어도 한 개의 부품이 완성된다. 상자에는 작업 구간 번호가 붙어 있으며, 상자들은 생산된 순서대로 한 줄에 놓여 있다. 출하 담당자는 이 중 연속한 몇 개의 상자를 하나의 출하 묶음으로 지정하려고 한다. 상자를 고를 때는 시작 번호 l과 끝 번호 r을 정하고, l번부터 r번까지의 모든 상자를 빠짐없이 포함해야 한다. 상자의 순서를 바꾸거나 중간 상자를 건너뛸 수 없으며, 상자 하나에 담긴 부품을 나누어 일부만 포함할 수도 없다. 상자 하나만 고르는 것도 가능하지만 아무 상자도 고르지 않는 것은 허용하지 않는다. 운송 장비에는 한 묶음에 담을 수 있는 부품 수의 기준이 있다. 묶음에 포함된 전체 부품 수가 L개 이상이고 U개 이하이면 출하 가능한 후보로 인정한다. 두 경계값은 모두 허용된다. 조건을 만족하더라도 담당자는 지금 실제로 출하할 묶음을 정하지 않으며, 가능한 모든 후보의 수만 확인하려고 한다. 두 후보의 시작 번호나 끝 번호 중 하나라도 다르면 서로 다른 후보이다. 포함된 부품 수가 같더라도 고른 상자의 위치가 다르면 각각 센다. 서로 다른 후보끼리는 상자가 겹쳐도 되며, 여러 후보를 동시에 선택할 수 있는지는 따지지 않는다. 주어진 생산 기록에서 출하 가능한 후보가 몇 개인지 구해야 한다. 조건을 만족하는 연속 구간이 하나도 없으면 후보 수는 0이다. 후보 수는 32비트 부호 있는 정수의 범위를 넘을 수 있다.

입력

첫째 줄에 N, L, U가 공백으로 구분되어 주어진다. 둘째 줄에 생산 순서대로 N개의 부품 수 A_1, A_2, …, A_N이 주어진다. 모든 입력값은 정수이며, 1≤N≤100,000, 1≤L≤U≤1,000,000,000, 1≤A_i≤9이다.

출력

부품 수의 합이 L 이상 U 이하인 비어 있지 않은 연속 구간의 수를 한 줄에 정수로 출력한다. 해당 구간이 없으면 0을 출력한다.

5 4 6
2 1 3 2 4

6

4 1 2
3 3 3 3

0

4 2 3
1 1 1 1

5

출처: Devin.KR 자체 제작