60036 블록 쌓기 Platinum II

문제

블록을 쌓는 놀이를 하고 있다. 블록을 위로 쌓을 수 있는 칸들이 총 $N$개 있으며, $1$번 칸부터 $N$번 칸까지 순서대로 붙어 있다.

현재 $i$번 칸에는 $A_i$개의 블록이 쌓여 있다. 현재 블록들이 쌓인 모양이 난잡하다고 생각해, 다음과 같은 조건들을 만족하도록 블록들을 옮기려고 한다.

• 각 칸에 쌓인 블록의 개수는 $L$ 이상 $R$ 이하이다.
• 각 칸에 쌓인 블록의 개수는 단조증가한다: $1 ≤ i ≤ N - 1$에 대해 $i$번 칸에 쌓인 블록의 개수는 $i + 1$번 칸에 쌓인 블록의 개수 이하이다.

여러분은 어떠한 칸의 블록을 인접한 칸으로 옮기는 것을 반복해 목표를 달성하려고 한다. 목표를 달성하는 것이 가능한지 판별하고, 가능한 경우 블록을 옮기는 횟수의 최솟값을 구해야 한다.

입력

첫 번째 줄에 $N$, $L$, $R$이 공백으로 구분되어 주어진다.

두 번째 줄에 $A_1$, $\dots$, $A_N$이 공백으로 구분되어 주어진다.

출력

목표를 달성하는 것이 불가능하다면 $-1$을 출력한다. 목표를 달성하는 것이 가능하다면 블록을 옮기는 횟수의 최솟값을 출력한다.

제한

• $1 ≤ N ≤ 100$
• $0 ≤ L ≤ R ≤ 10^9$
• $R - L ≤ 100$
• $0 ≤ A_i ≤ 10^9$ ($1 ≤ i ≤ N$)
• 주어지는 수는 모두 정수이다.

서브태스크

번호	배점	제한
1	7	$N ≤ 50$, $R - L ≤ 1$
2	6	$N ≤ 4$, $R - L ≤ 50$
3	11	$N ≤ 10$, $A_1 + \cdots + A_N ≤ 10$
4	11	$N ≤ 50$, $A_1 + \cdots + A_N ≤ 50$
5	30	$N ≤ 50$, $R ≤ 50$
6	10	$N ≤ 50$, $R - L ≤ 50$
7	25	추가 제약 조건 없음.

5 3 5
2 0 9 1 4

7

10 3 8
2 7 9 10 2 2 2 8 3 8

25

10 6 7
10 7 5 4 4 3 9 4 9 7

20

3 2 3
1 1 1

-1