You are a king and you are at war. If the enemy breaks through your frontline you lose.
Enemy can break the line only if the sum of morale of any $K$ continuous soldiers is strictly less than $M$. So, you being a motivational orator decides to boost their morale by giving a speech. On hearing it morale of a soldier multiplies by $X$ which depends on you and your speech (i.e. $X$ can be any positive value) but atmost only $K$ continuous speakers can hear your speech.
N soldiers are standing on the frontline with $A[i]$ morale. 
Determine the minimum number of speeches you need to give.

-----Input:-----
The first line contains three space seperated integers $N,K,M$.
The next line contains $N$ space integers, ith of which denotes the morale of $ith$ soldier.

-----Output:-----
Output the minimum number of speeches required. In case if it is impossible to achieve, print $-1$.

-----Constraints:-----
$1 \leq N,M \leq 10^5$
$1 \leq k \leq N$
$0 \leq Ai \leq 10^5$ 

-----Sample Input:-----
6 2 5
1 1 1 1 1 1

-----Sample Output:-----
2

-----Explanation:-----
We multiply 2nd ,3rd  and 5th,6th by 5. Resulting array will be 1 5 5 1 5 5.

Difficulty: interview

Starter code:

Solutions:
n,k,m = map(int,input().split())
ar = list(map(int,input().split()))
fsum = [ar[0]]
for i in range(1,n):
    fsum.append(fsum[i-1]+ar[i])
i = k
#print(fsum)
c = 0
while i <= n:
    if i == k:
        s = fsum[i-1]
    else:
        s = fsum[i-1]-fsum[i-k-1]
    if s == 0:
        c = -1
        break
    if s < m:
        c += 1
        if i<n:
            for j in range(i,i-k-1,-1):
                if ar[j-1] >0:
                    j += k-1
                    i = j
                    break
        if i<n:
            for j in range(i,i-k-1,-1):
                if ar[j-1] >0:
                    j += k-1
                    i = j
                    break
    i += 1
i = k
while i <= n:
    if i==k:
        s = fsum[i-1]
    else:
        s = fsum[i-1] - fsum[i-k-1]
    if s == 0 :
        c = -1
        break
    i += 1
print(c)

def main():
    n,k,m = list(map(int,input().split()))
    arr = list(map(int,input().split()))
    dp = [-1]
    for i in range(n):
        if arr[i] > 0:
            dp.append(i)
        else:
            dp.append(dp[-1])

    dp.pop(0)
    start = 0
    count = 0
    total = 0
    ans = 0
    index = -1
    rem = k
    #print(dp)
    for i in range(n):
        if index != -1:
            if i-index <= rem:
                #print('here',i,index)
                arr[i] *= m
            else:
                index = -1
                
        total += arr[i]
        count += 1
        if count == k:
            #print(total,start,i)
            count -= 1
            if total < m:
                index = dp[i]
                if index == -1 or i-index+1 > k:
                    print(-1)
                    return
                
                #print(index)
                rem = k-(i-index+1)
                #print('what',rem)
                total -= arr[index]
                arr[index] *= m
                total += arr[index]
                ans += 1
                index = i

            total -= arr[start]
            start += 1

    #print(arr)
    print(ans)

main()


N,K,M=list(map(int,input().split()))
A=list(map(int,input().split()))
tt=0
i=0
while(i<N):
    k1=-1
    j=0
    c=0
    while(j<K and i<N):
        if (A[i]!=0):
            k1=i
        c=c+A[i]
        i=i+1
        j=j+1
        
    while(c>=M and i<N):
        if (A[i]!=0):
            k1=i
        c=c+A[i]-A[i-K]
        i=i+1

    if (k1<0):
        tt=-1
        break

    elif (c<M and j==K):
        tt=tt+1
        i=k1+K
    #print(i,c)
    
print(tt)
        
    
    


nkm = list(map(int, input().split(' ')))
n = nkm[0]
k = nkm[1]
m = nkm[2]
li = list(map(int, input().split(' ')))
i = k-1
j = k-1
t = 1
c = 0
while(i<n):
	
	if(li[i]!=0):
		c+=1
		j=k-1
		i= i + 2*k - 1
	else:
		i-=1
		j-=1
		if(j<0):
			t=0
			break
			
if(t==1):
	print(c)
else:
	print("-1")