Vova had a pretty weird sleeping schedule. There are $h$ hours in a day. Vova will sleep exactly $n$ times. The $i$-th time he will sleep exactly after $a_i$ hours from the time he woke up. You can assume that Vova woke up exactly at the beginning of this story (the initial time is $0$). Each time Vova sleeps exactly one day (in other words, $h$ hours).

Vova thinks that the $i$-th sleeping time is good if he starts to sleep between hours $l$ and $r$ inclusive.

Vova can control himself and before the $i$-th time can choose between two options: go to sleep after $a_i$ hours or after $a_i - 1$ hours.

Your task is to say the maximum number of good sleeping times Vova can obtain if he acts optimally.


-----Input-----

The first line of the input contains four integers $n, h, l$ and $r$ ($1 \le n \le 2000, 3 \le h \le 2000, 0 \le l \le r < h$) — the number of times Vova goes to sleep, the number of hours in a day and the segment of the good sleeping time.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i < h$), where $a_i$ is the number of hours after which Vova goes to sleep the $i$-th time.


-----Output-----

Print one integer — the maximum number of good sleeping times Vova can obtain if he acts optimally.


-----Example-----
Input
7 24 21 23
16 17 14 20 20 11 22

Output
3



-----Note-----

The maximum number of good times in the example is $3$.

The story starts from $t=0$. Then Vova goes to sleep after $a_1 - 1$ hours, now the time is $15$. This time is not good. Then Vova goes to sleep after $a_2 - 1$ hours, now the time is $15 + 16 = 7$. This time is also not good. Then Vova goes to sleep after $a_3$ hours, now the time is $7 + 14 = 21$. This time is good. Then Vova goes to sleep after $a_4 - 1$ hours, now the time is $21 + 19 = 16$. This time is not good. Then Vova goes to sleep after $a_5$ hours, now the time is $16 + 20 = 12$. This time is not good. Then Vova goes to sleep after $a_6$ hours, now the time is $12 + 11 = 23$. This time is good. Then Vova goes to sleep after $a_7$ hours, now the time is $23 + 22 = 21$. This time is also good.

Difficulty: introductory

Starter code:

Solutions:
def main():
    import sys
    input = sys.stdin.readline

    N, H, L, R = list(map(int, input().split()))
    A = list(map(int, input().split()))

    dp = [[-1] * H for _ in range(N+1)]
    dp[0][0] = 0
    for i, a in enumerate(A):
        for t in range(H):
            if dp[i][t] >= 0:
                dp[i+1][(t+a)%H] = max(dp[i+1][(t+a)%H], dp[i][t] + int(L <= (t+a)%H <= R))
                dp[i + 1][(t + a-1) % H] = max(dp[i + 1][(t + a-1) % H], dp[i][t] + int(L <= (t + a-1) % H <= R))
    print(max(dp[-1]))



def __starting_point():
    main()

__starting_point()

#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n, h, l, r = map(int, input().split())
a = [int(item) for item in input().split()]
dp = [[-1] * h for _ in range(n + 1)]
dp[0][0] = 0

for i, item in enumerate(a):
    for j in range(h):
        if dp[i][j] == -1:
            continue
        # Sleep early
        nt = (j + item) % h
        if l <= nt <= r:
            dp[i+1][nt] = max(dp[i+1][nt], dp[i][j] + 1)
        else:
            dp[i+1][nt] = max(dp[i+1][nt], dp[i][j])
        # Sleep normaly
        nt = (j + item - 1 + h) % h
        if l <= nt <= r:
            dp[i+1][nt] = max(dp[i+1][nt], dp[i][j] + 1)
        else:
            dp[i+1][nt] = max(dp[i+1][nt], dp[i][j])
print(max(dp[-1]))

n,h,l,r = map(int, input().split())
a = list(map(int, input().split()))
dp = [[-1]*h for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
    for j in range(h):
        if dp[i][j] < 0: continue
        dp[i+1][(j+a[i])%h] = max(dp[i+1][(j+a[i])%h], dp[i][j] + (l <= (j+a[i])%h <= r))
        dp[i+1][(j+a[i]-1)%h] = max(dp[i+1][(j+a[i]-1)%h], dp[i][j] + (l <= (j+a[i]-1)%h <= r))
print(max(dp[-1]))

def go():
    n, h, l, r = list(map(int, input().split()))
    # n = int(input())
    a = list(map(int, input().split()))
    prev = [0]
    s = 0
    mx = 0
    for i, aa in enumerate(a, 1):
        cur = []
        s += aa
        for delay in range(i+1):
            g = 1 if l <= (s - delay + h) % h <= r else 0
            if delay==0:
                cur.append(prev[delay]+g)
            elif delay==i:
                cur.append(prev[delay-1] + g)
            else:
                cur.append(max(prev[delay],prev[delay-1])+g)
        prev = cur
        mx = max(mx,max(cur))
    return mx


# t = int(input())
for _ in range(1):
    print(go())


import sys

def solve():
    input = sys.stdin.readline
    N, H, L, R = map(int, input().split())
    A = [int(a) for a in input().split()]
    DP = [[-1] * H for _ in range(N)]
    DP[0][A[0]] = (1 if L <= A[0] <= R else 0)
    DP[0][A[0] - 1] = (1 if L <= A[0] - 1 <= R else 0)
    for i in range(1, N):
        for h in range(H):
            add = (1 if L <= h <= R else 0)
            if DP[i-1][(h - A[i]) % H] > -1: DP[i][h] = max(DP[i][h], DP[i-1][(h - A[i]) % H] + add)
            if DP[i-1][(h - A[i] + 1) % H] > -1: DP[i][h] = max(DP[i][h], DP[i-1][(h - A[i] + 1) % H] + add)
    print(max(DP[N-1]))
    return 0

def __starting_point():
    solve()
__starting_point()


n,h,l,r = list(map(int,input().split()))
N = n

a = list(map(int,input().split()))

flag = True
i = -1
lis = [float("-inf")] * h
lis[0] = 0
ans = 0

for i in range(N):

    nlis = [float("-inf")] * h

    na = a[i]
    for j in range(h):

        if l <= (j+na)%h <= r:
            nlis[(j+na) % h] = max(nlis[(j+na) % h] , lis[j] + 1)
        else:
            nlis[(j+na) % h] = max(nlis[(j+na) % h] , lis[j])

        

        if l <= (j+na-1)%h <= r:
            nlis[(j+na-1) % h] = max(nlis[(j+na-1) % h] , lis[j] + 1)
        else:
            nlis[(j+na-1) % h] = max(nlis[(j+na-1) % h] , lis[j])

            

    lis = nlis
    #print (lis)
    
print(max(0,max(lis)))


from itertools import accumulate
n,h,l,r = map(int,input().split())
a = list(map(int,input().split()))
acc = [0]+list(accumulate(a))
dp = [[0 for i in range(n+1)] for j in range(n+1)]
for i in range(1,n+1):
  for j in range(i+1):
    x = (acc[i]-j)%h
    if j == 0:
      if l<=x<=r:
        dp[i][j] = dp[i-1][j]+1
      else:
        dp[i][j] = dp[i-1][j]
    else:
      if l<=x<=r:
        dp[i][j] = max(dp[i-1][j-1],dp[i-1][j])+1
      else:
        dp[i][j] = max(dp[i-1][j-1],dp[i-1][j])
print(max(dp[n]))

import sys
input = sys.stdin.readline

n,h,l,r=list(map(int,input().split()))
A=list(map(int,input().split()))

DP=[-1]*h
DP[0]=0

for a in A:
    NDP=[-1]*h
    for k in range(h):
        if DP[k]==-1:
            continue
        if l<=(a+k)%h<=r:
            NDP[(a+k)%h]=max(NDP[(a+k)%h],DP[k]+1)
        else:
            NDP[(a+k)%h]=max(NDP[(a+k)%h],DP[k])
            
        if l<=(a+k-1)%h<=r:
            NDP[(a+k-1)%h]=max(NDP[(a+k-1)%h],DP[k]+1)
        else:
            NDP[(a+k-1)%h]=max(NDP[(a+k-1)%h],DP[k])
            
    DP=NDP

print(max(DP))
        
    



import copy
n,h,l,r=map(int,input().split())
A=list(map(int,input().split()))
V=[0]*h
V[0]=1
G=[0]*h
for i in range(n):
    R=[0]*h
    RG=[0]*h
    for j in range(h):
        if V[j]==1:
            X=(j+A[i])%h
            Y=(j+A[i]+h-1)%h
            R[X]=R[Y]=1
            if l<=X<=r: RG[X]=max(RG[X],1+G[j])
            else: RG[X]=max(RG[X],G[j])
            if l<=Y<=r: RG[Y]=max(RG[Y],1+G[j])
            else: RG[Y]=max(RG[Y],G[j])
    V=R
    G=RG
print(max(G))