Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

def _11(N: int, A: list)->list:
    MOD = 10**9 + 7

    d = {}
    l, r = 0, 0
    for i, a in enumerate(A):
        if a in d:
            l, r = d[a], N-i
        else:
            d[a] = i

    c1, c2 = [1]*(N+2), [1]*(N+2)
    for i in range(N+1):
        c1[i+1] = c1[i] * (N+1-i) // (i+1)
        c2[i+1] = c2[i] * (l+r-i) // (i+1)

    return [(c1[k+1]-c2[k]+MOD) % MOD for k in range(N+1)]


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = _11(N, A)
    print('\n'.join(map(str, ans)))


### FIXED CODE ###

def mod_inv(n: int, mod: int)->int:
    b, u, v = mod, 1, 0
    while b > 0:
        t = n // b

        n -= t * b
        u -= t * v

        n, b = b, n
        u, v = v, u

    return (u+mod) % mod


def _11(N: int, A: list)->list:
    MOD = 10**9 + 7

    d = {}
    l, r = 0, 0
    for i, a in enumerate(A):
        if a in d:
            l, r = d[a], N-i
        else:
            d[a] = i

    c1, c2 = [1]*(N+2), [1]*(N+2)
    for i in range(N+1):
        c1[i+1] = (c1[i] * (N+1-i) * mod_inv(i+1, MOD)) % MOD
        c2[i+1] = (c2[i] * (l+r-i) * mod_inv(i+1, MOD)) % MOD

    return [(c1[k+1]-c2[k]+MOD) % MOD for k in range(N+1)]


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = _11(N, A)
    print('\n'.join(map(str, ans)))
### BUGGY CODE ###


l = list(map(int, input().split()))
prices = list(map(int, input().split()))

for i in range(l[1]):
    #prices.sort(reverse = True)
    x = prices.index(max(prices))
    prices[x] = int(prices[x] / 2)

print(sum(prices))


### FIXED CODE ###

import heapq

N, M = map(int, input().split())
values = list(map(int, input().split()))
sortedValues = []

for v in values:
    heapq.heappush(sortedValues, (-1)*v)

for i in range(M):
    heapq.heappush(sortedValues, int((heapq.heappop(sortedValues) * 1/2)))

print((-1) * sum([heapq.heappop(sortedValues) for i in range(len(sortedValues))]))
### BUGGY CODE ###

def jmp(h,k):
    n=len(h)
    dp=[1000000000 for i in range(n+1)]
    dp[0]=0
    dp[1]=abs(h[1]-h[0])
    for i in range(n+1):
        for j in range(i+1,i+k+1):
            if(j<n):
                dp[j]=min(dp[j],dp[i]+abs(h[i]-h[j]))
    # print(dp)
    return dp[n-1]


n,k=map(int,input().split())
l=list(map(int,input().split()))
print(jmp(l,k))

### FIXED CODE ###

def jmp(h,k):
    n=len(h)
    dp=[1000000000 for i in range(n+1)]
    dp[0]=0
    dp[1]=abs(h[1]-h[0])
    for i in range(n+1):
        for j in range(i+1,i+k+1):
            if(j<n):
                dp[j]=min(dp[j],dp[i]+abs(h[i]-h[j]))
    # print(dp)
    return dp[n-1]


n,k=map(int,input().split())
l=list(map(int,input().split()))
print(jmp(l,k))
### BUGGY CODE ###

N = 10**5
bit_prime = 0
bit_2017 = [0] * N


def pre_make_prime():
    global bit_prime
    bit_prime = (2 ** N - 1) ^ 3
    for i in range(2, N + 1):
        if (bit_prime >> i) & 1:
            for j in range(i * 2, N + 1, i):
                bit_prime &= ~(1 << j)


def pre_make_2017():
    global bit_2017
    for i in range(3, N, 2):
        if is_prime(i) and is_prime((i + 1) // 2):
            bit_2017[i] = 1


def is_prime(n):
    return bit_prime & (1 << n)


def resolve():
    pre_make_prime()
    pre_make_2017()
    global bit_2017
    Q = int(input())
    for _ in range(Q):
        L, R = [int(i) for i in input().split()]
        print(sum(bit_2017[L:R + 1]))


resolve()


### FIXED CODE ###

def pre_make_prime(N):
    is_prime = [True for _ in range(N + 1)]
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, N + 1):
        if is_prime[i]:
            for j in range(i * 2, N + 1, i):
                is_prime[j] = False
    return is_prime


def resolve():
    N = 10**5
    is_prime = pre_make_prime(N)

    arr_2017 = [0] * (N + 2)
    for i in range(1, N, 2):
        arr_2017[i + 2] = arr_2017[i] + \
            (1 if is_prime[i] and is_prime[(i + 1) // 2] else 0)

    Q = int(input())
    for _ in range(Q):
        L, R = [int(i) for i in input().split()]
        print(arr_2017[R + 2] - arr_2017[L])


resolve()
### BUGGY CODE ###

n,m=map(int,input().split())
lst=list(map(int,input().split()))
lst.sort(reverse=True)
for i in range(m):
    lst.sort(reverse=True)
    lst[0]=int(lst[0]/2)
print(sum(lst))    

### FIXED CODE ###

import heapq
import math
n,m=map(int,input().split())
a=list(map(lambda x:int(x)*(-1),input().split()))
heapq.heapify(a)
for i in range(m):
    heapq.heappush(a,math.ceil(heapq.heappop(a)/2))
   
    
    
print(-1*sum(a))
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())  # 迷路の縦、横の長さ
maze = [input() for iiii in range(H)]

# print(maze)
dist = [[-1] * W for iii in range(H)]  # スタートからの距離
check_que = deque()

for i in range(H):
    for j in range(W):
        if maze[i][j] == "#":
            dist[i][j] = 0
            check_que.append((i, j))
# print(dist)


def bfs(initial_d):  # distを編集する関数
    #print("{},{}".format(tate, yoko))
    while check_que:

        h, w = check_que.popleft()
        d = dist[h][w]
        for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            h_prime, w_prime = h + dh, w + dw

            if 0 > h_prime or h_prime >= H or 0 > w_prime or w_prime >= W:
                continue
            if dist[h_prime][w_prime] == -1:
                dist[h_prime][w_prime] = d + 1
                check_que.append((h_prime, w_prime))

    return d


dis = bfs(0)
# print(dist)
print(dis)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())  # 迷路の縦、横の長さ
maze = []
for _ in range(H):
    maze.append(input())
# print(maze)
dist = [[-1] * W for iii in range(H)]  # スタートからの距離
check_que = deque()

d = 0

for i in range(H):
    for j in range(W):
        if maze[i][j] == "#":
            dist[i][j] = 0
            check_que.append((i, j))
# print(dist)


def bfs(initial_d):  # distを編集する関数
    dis = 0
    #print("{},{}".format(tate, yoko))
    while len(check_que) != 0:

        h, w = check_que.popleft()
        d = dist[h][w]
        for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            h_prime, w_prime = h + dh, w + dw

            if 0 <= h_prime <= H - 1 and 0 <= w_prime <= W - 1:
                if dist[h_prime][w_prime] == -1:
                    dist[h_prime][w_prime] = d + 1
                    check_que.append((h_prime, w_prime))
                    if d + 1 > dis:
                        dis = d+1
    return dis


dis = bfs(0)
# print(dist)
print(dis)
### BUGGY CODE ###

N, M = map(int, input().split())
group = []
tf = []

for i in range(M):
  A, B = map(int, input().split())
  if A not in tf and B not in tf:
    tf.append(A)
    tf.append(B)
    group.append([A,B])
  else:
    if A in tf and B in tf:
      a, b = 0, 0
      for j in range(len(group)):
        if A in group[j]:
          a = j
          if b!=0:
            break
        elif B in group[j]:
          b = j
          if a!=0:
            break
      group[a].extend(group[b])
      del group[b]
    elif A not in tf:
      tf.append(A)
      for j in range(len(group)):
        if B in group[j]:
          group[j].append(A)
          break
    elif B not in tf:
      tf.append(B)
      for j in range(len(group)):
        if A in group[j]:
          group[j].append(B)
          break
num = N - len(tf) 
print(len(group)+num-1)

### FIXED CODE ###

# Connect Cities
# Union Findデータ構造（素集合データ構造）
 
#入力:N,M(int:整数)
def input2():
	return map(int,input().split())
 
#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))
 
class UnionFind():
	"""docstring for UnionFind"""
	def __init__(self, n):
		self.parents = [-1]*n
 
	def find(self,x):
		if self.parents[x] < 0: #自分が親である時
			return x
		else: #自分が子供である時
			self.parents[x]=self.find(self.parents[x])
			return self.parents[x]
 
	def union(self,x,y):
		# 各要素の親要素を返す
		x=self.find(x)
		y=self.find(y)
 
		if x==y:
			return
		if self.parents[x] > self.parents[y]:
			x,y=y,x
 

		self.parents[y]=x

n,m=input2()
AB=[input_array() for _ in range(m)]
 
uf = UnionFind(n)
for ab in AB:
	a=ab[0]
	b=ab[1]
	uf.union(a-1,b-1)

ans=0
for i in uf.parents:
	if i < 0:
		ans+=1

print(ans-1)
### BUGGY CODE ###

from itertools import product
import copy
H,W,K = list(map(int, input().split()))
A = []
for i in range(H):
  A.append(list(map(int, input())))

#SM = [np.cumsum(A[i]) for i in range(H)]

ANS = []
for pat in product(['0','1'], repeat = H-1):
  res = []
  cnt = 0
  now = copy.copy(A[0])
  for i in range(1,H):
    p = pat[i-1]
    if p == '1':
      res.append(now)
      now = copy.copy(A[i])
      cnt += 1
    else:
      for j in range(W):
        now[j] += A[i][j]
  res.append(now)
  
  """  
  print("---")
  print(pat)
  print(res)
  print(cnt)
  """  
  wk2 = [0] * len(res)
  cnt2 = 0
  flg = True
  for x in range(W):
    for j in range(len(res)):
      if res[j][x] > K:
        # 横に割った段階で、すでに最小単位がKを超えてたら実現不可能
        flg = False
        break
      if wk2[j] + res[j][x] > K:
        cnt2 += 1
        wk2 = [0] * len(res)
        break
    for j in range(len(res)):
      wk2[j] += res[j][x]
    if not flg:
      break
      
  if flg:
    ANS.append(cnt + cnt2)
    #print(pat, cnt, cnt2)
print(min(ANS))


### FIXED CODE ###

from itertools import product
import copy
H,W,K = list(map(int, input().split()))
A = []
for i in range(H):
  A.append(list(map(int, input())))

#SM = [np.cumsum(A[i]) for i in range(H)]

ANS = []
for pat in product(['0','1'], repeat = H-1):
  res = []
  cnt = 0
  now = copy.copy(A[0])
  for i in range(1,H):
    p = pat[i-1]
    if p == '1':
      res.append(now)
      now = copy.copy(A[i])
      cnt += 1
    else:
      for j in range(W):
        now[j] += A[i][j]
  res.append(now)
  
  """  
  print("---")
  print(pat)
  print(res)
  print(cnt)
  """  
  wk2 = [0] * len(res)
  cnt2 = 0
  flg = True
  for x in range(W):
    for j in range(len(res)):
      if res[j][x] > K:
        # 横に割った段階で、すでに最小単位がKを超えてたら実現不可能
        flg = False
        break
      if wk2[j] + res[j][x] > K:
        cnt2 += 1
        wk2 = [0] * len(res)
        break
    for j in range(len(res)):
      wk2[j] += res[j][x]
    if not flg:
      break
      
  if flg:
    ANS.append(cnt + cnt2)
    #print(pat, cnt, cnt2)
print(min(ANS))
### BUGGY CODE ###

import sys
from collections import deque
input = sys.stdin.readline
H, W = map(int, input().split())
G = [[0]*(H*W) for _ in range(H*W)]
edge = []
S = [list(input()) for i in range(H)]
for i in range(H*W) :
    h = i//W
    w = i%W
    if S[h][w] != "#" :
        if h > 1 and S[h-1][w] == "." :
            j = (h-1)*W + w
            edge.append([i, j])
            G[i][j] = G[j][i] = 1
        if h < H-1 and S[h+1][w] == "." :
            j = (h+1)*W + w
            edge.append([i, j])
            G[i][j] = G[j][i] = 1
        if w > 1 and S[h][w-1] == "." :
            j = h*W + w-1
            edge.append([i, j])
            G[i][j] = G[j][i] = 1
        if w < W-1 and S[h][w+1] == "." :
            j = h*W + w+1
            edge.append([i, j])
            G[i][j] = G[j][i] = 1

def bfs(s) :
    q = deque([s])
    dist[s] = 0
    while q :
        now = q.popleft()
        for i in range(H*W) :
            if G[now][i] == 1 :
                if dist[i] != -1 :
                    continue
                else :
                    dist[i] = dist[now] + 1
                    q.append(i)
    return max(dist)

ans = 0
for i in range(H*W) :
    if S[i//W][i%W] != "#" :
        dist = [-1 for _ in range(H*W)]
        ans = max(ans, bfs(i))

print(ans)


### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
H, W = map(int, input().split())
G = [[0]*(H*W) for _ in range(H*W)]
edge = []
S = [list(input()) for i in range(H)]
for i in range(H*W) :
    h = i//W
    w = i%W
    if S[h][w] != "#" :
        if h > 1 and S[h-1][w] == "." :
            j = (h-1)*W + w
            edge.append([i, j])
            G[i][j] = G[j][i] = 1
        if h < H-1 and S[h+1][w] == "." :
            j = (h+1)*W + w
            edge.append([i, j])
            G[i][j] = G[j][i] = 1
        if w > 1 and S[h][w-1] == "." :
            j = h*W + w-1
            edge.append([i, j])
            G[i][j] = G[j][i] = 1
        if w < W-1 and S[h][w+1] == "." :
            j = h*W + w+1
            edge.append([i, j])
            G[i][j] = G[j][i] = 1

def bfs(s) :
    q = deque([s])
    dist[s] = 0
    while q :
        now = q.popleft()
        for i in range(H*W) :
            if G[now][i] == 1 :
                if dist[i] != -1 :
                    continue
                else :
                    dist[i] = dist[now] + 1
                    q.append(i)
    return max(dist)

ans = 0
for i in range(H*W) :
    if S[i//W][i%W] != "#" :
        dist = [-1 for _ in range(H*W)]
        ans = max(ans, bfs(i))

print(ans)
### BUGGY CODE ###

N = int(input().strip())
A = list(map(int, input().strip().split()))

ans = A[0]
for i in range(1,N):
  ans *= A[i]

if ans > 10**18: ans = -1

print(ans)

### FIXED CODE ###

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

limit = 10 ** 18
A.sort()
result = A[0]
for a in A[1:]:
    result *= a
    if result > limit:
        print(-1)
        exit()
print(result)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

# なんこか入力
n,m = map(int, input().split())

# 空白区切りの数列をリストに代入
a = [int(i) for i in input().split()]
b = [0]*(n+1)
bb=0

for i in range(0,n) :
    b[i+1] = bb = ( bb+a[i] ) % m
    
answer = 0
for r in range(1,n+1) :
    for l in range(0,r) :
        if (b[r] - b[l] ) % m == 0:
            answer += 1

print(answer)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

# なんこか入力
n,m = map(int, input().split())

# 空白区切りの数列をリストに代入
a = [int(i) for i in input().split()]
b = [0]*(n)
c ={0:1}
bb=0
for i in range(0,n) :
    bb = ( bb+a[i] ) % m
    c[bb] = c.get(bb,0) + 1
    
    
answer = 0
#print(c)

for i,j in c.items():
    if j > 1:
        answer +=  (j * (j-1) // 2 )

print(answer)
### BUGGY CODE ###

import sys
from itertools import count, accumulate
from operator import mul
from functools import reduce
lines = sys.stdin.readlines()

positions = [int(i) for i in lines[1].split(' ')]

distances = [ j - i for i, j in zip(positions, positions[1:])]

n = len(distances)
factorials = [1] + list(accumulate(range(1,n + 1), mul))

combinations = dict()
def combination(i, j):
    if (i, j) in combinations:
        return combinations((i, j))
    else:
        return factorials[i] // (factorials [j] * factorials[i - j])

permutations = dict()
def permutation(i, j):
    if (i, j) in permutations:
        return permutations((i, j))
    else:
        return reduce(mul, range(j, i+1))

s = 0
result = 0
for d, i in zip(distances, count(1)):
    lt = i - 1
    gt = n - i
    t = factorials[lt] * combination(n, gt) * factorials[gt]
    s += t
    result += d * s

print(int(result % (pow(10,9) + 7)))

### FIXED CODE ###

import sys
from itertools import count, accumulate
from operator import mul
from functools import reduce
lines = sys.stdin.readlines()

positions = [int(i) for i in lines[1].split(' ')]

distances = [ j - i for i, j in zip(positions, positions[1:])]

n = len(distances)
p = pow(10,9) + 7

factorials = [1] + list(accumulate(range(1,n + 1), lambda x, y: (x * y) % p))

combinations = dict()
def combination(i, j):
    j = min(j, i - j)
    if (i, j) in combinations:
        return combinations((i, j))
    else:
        return factorials[i] // (factorials [j] * factorials[i - j])

permutations = dict()
def permutation(i, j):
    if (i, j) in permutations:
        return permutations((i, j))
    else:
        return reduce(mul, range(j, i+1))

def modpow(a, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n = n >> 1
    return res

s = 0
result = 0
for d, i in zip(distances, count(1)):
    lt = i - 1
    gt = n - i
    i_inv = modpow(i, p-2, p)
    t = factorials[n] * i_inv
    s += t
    result += d * s

print(int(result % (pow(10,9) + 7)))
### BUGGY CODE ###

from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix


n,m = map(int,input().split())
g = csr_matrix((n,n),dtype=int)
for i in range(m):
    ai,bi = map(int,input().split())
    g[ai-1,bi-1] = 1
    g[bi-1,ai-1] = 1
r = connected_components(g,return_labels=False)
print(r-1)

### FIXED CODE ###

class UnionFind:
    def __init__(self, n: int) -> None:
        self.forest = [-1] * n

    def union(self, x: int, y: int) -> None:
        x = self.findRoot(x)
        y = self.findRoot(y)
        if x == y:
            return
        if self.forest[x] > self.forest[y]:
            x,y = y,x
        self.forest[x] += self.forest[y]
        self.forest[y] = x
        return

    def findRoot(self, x: int) -> int:
        if self.forest[x] < 0:
            return x
        else:
            self.forest[x] = self.findRoot(self.forest[x])
            return self.forest[x]

    def issame(self, x: int, y: int) -> bool:
        return self.findRoot(x) == self.findRoot(y)

    def size(self,x: int) -> int:
        return -self.forest[self.findRoot(x)]


n,m = map(int,input().split())
uf = UnionFind(n)
s = set()
for i in range(m):
    ai,bi = map(int,input().split())
    uf.union(ai-1,bi-1)

for i in range(n):
    s.add(uf.findRoot(i))
print(len(s)-1)
### BUGGY CODE ###

import copy
def main():
    [N,W]=input().split(" ")
    '''read from keyboard and put all the item to box'''
    N=int(N)
    W=int(W)
    box=[]
    for i in range(N):
        [vi,wi]=input().split(" ")
        box.append([float(vi),float(wi)])
        
    assemblebox=[]
    '''creat a set of full permutation of input. using recursion'''
    assemblebox=permutations(N,box,assemblebox,[])

    maximum=0
    '''optimization'''
    for i in range(len(assemblebox)):
        weight=0
        value=0
        for j in range(N):
            weight=weight+assemblebox[i][j][1]
            if(weight>W):
                break
            value=value+assemblebox[i][j][0]
        if(maximum<value):
            maximum=value
            
    print(int(maximum))
    '''output'''
        

    return 0

def permutations(N,box,assemblebox,record):
    for i in range(N):
        Np=N
        boxp=copy.deepcopy(box)
        recordp=copy.deepcopy(record)
        recordp.append(box[i])
        boxp.pop(i)
        Np=Np-1
        if(Np==0):
            assemblebox.append(recordp)
        else:
            result=permutations(Np,boxp,assemblebox,recordp)
    return assemblebox

main()

### FIXED CODE ###

def main():
    [N,W]=input().split(" ")
    N=int(N)
    W=int(W)
    inputset=[]
    for i in range(N):
        [vi,wi]=input().split(" ")
        inputset.append([int(vi),int(wi)])

    graph=[]
    for i in range(N+1):
        graph.append([])
        for j in range(W+1):
            graph[i].append(0)

    for i in range(N):
        for j in range(W+1):
            if(inputset[i][1]>j):
                graph[i+1][j]=graph[i][j]
            else:
                rest=j-inputset[i][1]
                choosevalue=graph[i][rest]+inputset[i][0]
                nonchoosevalue=graph[i][j]
                if(choosevalue>nonchoosevalue):
                    graph[i+1][j]=choosevalue
                else:
                    graph[i+1][j]=nonchoosevalue

    print(graph[N][W])

main()
### BUGGY CODE ###

n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353
ans=0
for l in range(n):
  dp=[[1]+[0]*3000 for _ in range(n+1)]
  for i in range(l,n):
    for j in range(3001):
        dp[i+1][j]=dp[i][j]
        if j-a[i]>=0:
            dp[i+1][j]+=dp[i][j-a[i]]
        dp[i+1][j]%=mod
    #print(dp[i+1][:10])
    ans+=dp[i+1][s]
    ans%=mod
print(ans)

### FIXED CODE ###

import numpy as np
n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353
f=np.zeros(3001,int)

ans=0
for ai in a:
  ff=np.zeros(3001,int)
  ff+=f
  ff[ai:]+=f[:-ai]
  ff[0]+=1
  ff[ai]+=1
  f=ff
  f%=mod
  ans+=f[s]
  ans%=mod
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
t=[[0 for i in range(n)] for j in range(64)]
for i in range(64):
    for j in range(n):
        if i == 0:
            t[i][j]=a[j]
        else:
            t[i][j]=t[i-1][t[i-1][j]-1]
ans=1
for i in range(64):
    r = k%2
    k = k//2
    if r == 1:
        ans = t[i][ans-1]
    if k == 0:
        print(ans)
        exit()

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
dic = {1:1}
his=[1]
p=1
s=0
g=0
step=1
for i in range(k):
    t=a[p-1]
    if (t in dic and dic[t]==1):
        s=t
        g=a[t-1]
        break
    else:
        dic[t]=1
    step+=1
    his.append(t)
    p=t
x=his.index(t)
o=step-x
lp=his[x:]
k-=x
#print(x,o,his,lp)
#print(dic)
print(lp[k%o])
### BUGGY CODE ###

def resolve():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [0] * n
    dp[0] = 0
    dp[1] = abs(h[1] - h[0])
    for i in range(2, n):
        dp[i] = min([dp[i - j] + abs(h[i - j] - h[i]) for j in range(1, min(k + 1, i + 1))])
    print(dp[-1])


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [10 ** 9] * n
    dp[0] = 0
    dp[1] = abs(h[1] - h[0])
    for i in range(2, n):
        for j in range(1, min(k + 1, i + 1)):
            dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]))
    print(dp[-1])


if __name__ == "__main__":
    resolve()
### BUGGY CODE ###

#!/usr/bin/env python3
N, K = map(int, input().split())
a = list(map(int, input().split()))

pl = [(x if (x > 0) else 0) for x in a]
ans = 0
if lambda x: x > 0 in a:
    for i in range(N - K + 1):
        ans = max(ans, max(0, sum(a[i:K + i])) + sum(pl[:i]) + sum(pl[K + i:]))
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
N, K = map(int, input().split())
a = list(map(int, input().split()))

pl = [(x if (x > 0) else 0) for x in a]
s = sum(pl)
sk_a = [sum(a[:K])]
sk_pl = [sum(pl[:K])]
for i in range(1, N - K + 1):
    sk_a.append(sk_a[-1] - a[i - 1] + a[K + i - 1])
    sk_pl.append(sk_pl[-1] - pl[i - 1] + pl[K + i - 1])

ans = 0
if lambda x: x > 0 in a:
    for i in range(N - K + 1):
        ans = max(ans, s - sk_pl[i] + max(0, sk_a[i]))

print(ans)
### BUGGY CODE ###

N=int(input())
L=list(map(int, input().split()))
a=0
for i in range(0,N-2,1):
  for j in range(i+1,N-1,1):
    for q in range(j+1,N,1):
        if L[i]<L[j]+L[q] and L[j]<L[i]+L[q] and L[q]<L[i]+L[j]:
          a+=1
print(a)

### FIXED CODE ###

from bisect import bisect_left
N=int(input())
L=list(map(int,input().split()))

L.sort()
a=0
for i in range(N-2):
    for j in range(i+1,N-1):
        a+=bisect_left(L,L[i]+L[j])-j-1
print(a)
### BUGGY CODE ###

N,Q = (int(_) for _ in input().split())
S = input()
P = []
for i in range(Q):
    P.append((int(_) for _ in input().split()))

for i in range(Q):
    l,r = P[i]
    print(S.count('AC',l-1,r))


### FIXED CODE ###

def countAC(s):
    counter = 0
    index = [0]
    for i in range(1,N):
        if s[i-1] == 'A':
            if s[i] == 'C':
                counter += 1
                index.append(counter)
                continue
        index.append(counter)
    return index

N,Q = (int(_) for _ in input().split())
S = input()
SIndex = countAC(S)
out = 0
for i in range(Q):
    l,r = (int(_) for _ in input().split())
    print(SIndex[r-1] - SIndex[l-1])