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

N,Q = map(int,input().split())
S = str(input())
lr = [list(map(int,input().split())) for _ in range(Q)]

for l,r in lr:
  l -= 1
  print(S[l:r].count("AC"))

### FIXED CODE ###

from itertools import accumulate
N,Q = map(int,input().split())
S = str(input())
lr = [list(map(int,input().split())) for _ in range(Q)]
sl = [0]*N
for i in range(N):
  if S[i:i+2] == "AC":
    sl[i] = 1
slr = [0]+list(accumulate(sl))
ans = 0
for l,r in lr:
  ans = slr[r-1]-slr[l-1]
  print(ans)
### BUGGY CODE ###

nums = int(input())
direct = list(input())
max = 0

for i in range(nums):
    count = 0
    for x in range(nums):
        if x == i: continue
        if x < i  and direct[x] == "E":
            count += 1
        elif i < x and direct[x] == "W":
            count += 1

    if count > max:
        max = count
print(nums - max-1)

### FIXED CODE ###

nums = int(input())
direct = list(input())
ary_w = [0 for i in range(nums)]
ary_e = [0 for i in range(nums)]
count_w = 0
count_e = 0
count = 0
result = 100000000

for i in range(nums):
    if direct[i] == "W":
        count_w += 1
    elif direct[i] == "E":
        count_e += 1

    ary_w[i] = count_w
    ary_e[i] = count_e

for i in range(nums):
    w = ary_w[i-1]
    e = ary_e[-1] - ary_e[i]
    if i == 0:
        w = 0
        e = ary_e[-1]
    count = w+e
    if count < result:
        result = count
print(result)
### BUGGY CODE ###

from math import *
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
for x in range(1,n+1):
    ans = 0
    m = ceil(sqrt(x))+1
    for i in range(1, m):
        for j in range(i, m):
            for k in range(j, m):
                if i**2 + j**2 + k**2 + i*j + j*k + k*i == x:
                    if i == j == k:
                        ans += 1
                    elif i == j or j == k or k == i:
                        ans += 3
                    else:
                        ans += 6
    print(ans)

### FIXED CODE ###

from math import *
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
for x in range(1,n+1):
    ans = 0
    m = ceil(sqrt(x))+1
    for i in range(1, m):
        for j in range(i, m):
            tmp = (i+j)**2 - 4*(i**2+j**2+i*j-x)
            if tmp > (i+j)**2:
                k = ( -(i+j) + sqrt(tmp) ) // 2
                if k >= j and i**2 + j**2 + k**2 + i*j + j*k + k*i == x:
                    if i == j == k:
                        ans += 1
                    elif i == j or j == k or k == i:
                        ans += 3
                    else:
                        ans += 6
    print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import math
sys.setrecursionlimit(20000)
def update(tree,x,y,N):
    # offset
    #x += int(N/2)
    x += N - 1
    tree[x] = y
    # segment tree no update suru
    while True:
        if(x <= 0):
            break
        x = math.floor((x - 1)/2)
        left = x*2+1
        right = x*2+2
        tree[x] = min(tree[left],tree[right])

def find(tree,x,y,k,l,r):

    if (r <= x or y <= l):
        return 2**31 - 1
    # sita wo mite itte mitukatta toki (intersect)
    if ( x <= l and r <= y):
        return tree[k]
    # sita ni sagaru
    v_left = find(tree, x, y, k*2 + 1, l, int((l+r)/2))
    v_right = find(tree, x, y, k*2 + 2, int((l+r)/2), r)
    return min(v_left, v_right)

if __name__ == '__main__':
    _N,k = map(int, input().split())
    arr = list(map(int,input().split()))
    INT_MAX = 2**31 - 1
    N = 1
    res = []
    while True:
        if(N >= _N):
            break
        N *= 2
    #N = 2*N - 1 - 1
    if not (N == 1):
        A_bin_tree = [INT_MAX]*(2*N - 1)
    else:
        A_bin_tree = [INT_MAX]
    for i in range(_N):
        update(A_bin_tree,i,arr[i],N)

    for i in range(_N-k+1):
        z = find(A_bin_tree,i,i+k,0,0,N)
        res.append(z)

    print(" ".join([str(r) for r in res]))



### FIXED CODE ###

INTMAX = (1<<31) - 1

def ans():
    for i in range(k):
        x = i + OFS
        A[x] = arr[i]
        while True:
            if(x <= 0):
                break
            x = (x - 1)//2
            l = A[x*2+1]
            r = A[x*2+2]
            A[x] = l if l < r else r#min(tree[left],tree[right])
    res = []
    c = 0
    for i in range(_N-k):
        res.append(A[0])
        x = c + OFS
        A[x] = arr[i+k]
        while True:
            if(x <= 0):
                break
            x = (x - 1)//2
            l = A[x*2+1]
            r = A[x*2+2]
            A[x] = l if l < r else r
        c += 1
        if(c == k):
            c = 0
    res.append(A[0])
    print(*res)

_N,k = map(int, input().split())
*arr, = map(int,input().split())
if(k==1):
    print(*arr)
else:
    N = 2**(_N-1).bit_length()
    A = [INTMAX]*(2*N)
    OFS = N - 1
    ans()
### BUGGY CODE ###

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

f=1
for i in a[:k]:
  f*=i
bef=f
for (i,j)in zip(a[k:],a[:-k]):
  f*=i
  f//=j

  if bef<f:
    print("Yes")
  else:
    print("No")
  bef=f

### FIXED CODE ###

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

for (i,j)in zip(a[k:],a[:-k]):
  if j<i:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

N = int(input())
As = list(sorted(list(map(int, input().split()))))

result = 0
stored = []
while len(As)!=0:
    item = As.pop()
    is_exist = False
    if item in stored:
        continue
    for A in sorted(As):
        if item%A==0:
            is_exist = True
            break
    if not is_exist:
        result+=1
    stored.append(item)
print(result)


### FIXED CODE ###

N = int(input())
As = list(sorted(list(map(int, input().split()))))

max_num = max(As)
tfs = [0 for _ in range(max_num+1)]

for A in As:
    if tfs[A] != 0:
        tfs[A] = 2
        continue
    for j in range(A, max_num+1, A):
        tfs[j]+=1

result = 0
for A in As:
    if tfs[A] == 1:
        result+=1
print(result)
### BUGGY CODE ###

#A問題
N,M = map(int,input().split())
A = []
mod = 1000000007
for i in range(M):
    A.append(int(input()))

sta = []
for i in range(N+1):
    if i == 0:
        sta.append(1)
    elif i == 1:
        sta.append(1)
    elif i == 2:
        sta.append(2)
    else:
        sta.append(sta[i-1]+sta[i-2])

row = []
now = 1
flag = 0
for i in range(N):
    I = i+1
    if i == 0:
        if I in A:
            now = 0
            flag = 1
        else:
            now+=1
    else:
        if I in A:
            if flag == 1:
                flag = 2
                break
            else:
                row.append(now)
                now = 0
                flag = 1
        else:
            flag = 0
            now+=1

if flag == 2:
    print(0)
else:
    row.append(now)
    ans = 1
    for r in row:
        ans*=sta[r-1]
        ans%=mod
    print(ans%mod)

### FIXED CODE ###

#C問題
mod = 10**9+7
N,M = map(int,input().split())

step = []
for i in range(N+2):
    if i <= 1:
        step.append(1)
    elif i == 2:
        step.append(1)
    else:
        step.append(step[i-1]+step[i-2])
    
A = []
for j in range(M):
    A.append(int(input()))

stairs = []
flag = 0
old = -1
for a in A:
    if a-old == 1:
        flag = 1
        break
    else:
        stairs.append(a-old-1)
        old = a
stairs.append(N-old)

if flag == 1:
    print(0)
else:
    #print(stairs)
    ans = 1
    for s in stairs:
        ans*=step[s]
        
    print(ans%mod)
### BUGGY CODE ###

#import math
#import numpy as np
#import torch
#import torch.nn as nn
#import matplotlib.pyplot as plt
#from decimal import Decimal
#import itertools


N=int(input())
#N,K = map(int,input().split())
#B,W = map(int,input().split())
#T=int(input())
A = list(map(int,input().split()))
#S=str(input())
#A=[p for p in range(2*10**5)]
Q=int(input())
l=[]
for i in range(Q):
    #print(A)
    B,C = map(int,input().split())
    a=True
    while a==True:
        if B==C:
            a=False
        try:
            ind=A.index(B)
            A[ind]=C
            #print(A)
        except:
            a=False
    #print(A)
    l.append(sum(A))
for i in l:
    print(i)

### FIXED CODE ###

#import math
#import numpy as np
#import torch
#import torch.nn as nn
#import matplotlib.pyplot as plt
#from decimal import Decimal
#import itertools
import collections

N=int(input())
#N,K = map(int,input().split())
#B,W = map(int,input().split())
#T=int(input())
A = list(map(int,input().split()))
#S=str(input())
#A=[p for p in range(2*10**5)]
Q=int(input())
c=collections.Counter(A)
s=sum(A)
for i in range(Q):
    #print(A)
    B,C = map(int,input().split())
    if c[B]:
        s += (C-B)*c[B]
        c[C] += c[B]
        c[B] = 0

    print(s)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc077/tasks/arc084_a

"""
import sys
from sys import stdin
from bisect import bisect_left, bisect_right
from functools import lru_cache
input = stdin.readline


@lru_cache(maxsize=None)
def calc(i):
    ans = 0
    for b in B[i:]:
        j = lut_B[b]
        if j == N:
            break
        ans += (N - j)
    return ans


lut_B = {}
B = []
N = 0
def main(args):
    global lut_B
    global B
    global N
    N = int(input())
    A = [int(x) for x in input().split()]
    B = [int(x) for x in input().split()]
    C = [int(x) for x in input().split()]
    A.sort()
    B.sort()
    C.sort()

    lut_A = {a:bisect_right(B, a) for a in A}
    lut_B = {b:bisect_right(C, b) for b in B}

    ans = 0
    for a in A:
        i = lut_A[a]
        if i == N:
            break
        ans += calc(i)

    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc077/tasks/arc084_a

"""
import sys
from sys import stdin
from bisect import bisect_left, bisect_right
input = stdin.readline


def main(args):
    N = int(input())
    A = [int(x) for x in input().split()]
    B = [int(x) for x in input().split()]
    C = [int(x) for x in input().split()]
    A.sort()
    B.sort()
    C.sort()

    lut_A = {}
    lut_C = {}
    for b in B:
        i = bisect_left(A, b)
        lut_A[b] = i
        j = bisect_right(C, b)
        lut_C[b] = N - j


    ans = 0
    for b in B:
        i = lut_A[b]
        j = lut_C[b]
        ans += i * j

    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

N=int(input())
A = [list(map(int, input().split())) for i in range(N)]
result=0
flag=True
for m in range(N-1):
    for n in range(m+1,N):
        list_t=list(range(N))
        list_t.remove(m)
        list_t.remove(n)
        for t in list_t:
            if A[m][n]>A[m][t]+A[t][n]:
                result=-1
            elif A[m][n]==A[m][t]+A[t][n] and result!=-1:
                flag=False
        if flag and result!=-1:
            result+=A[m][n]
        else:
            flag=True
print(result)

### FIXED CODE ###

N=int(input())
A = [list(map(int, input().split())) for i in range(N)]
result=0
flag=True
isbreak=False
for m in range(N-1):
    for n in range(m+1,N):
        list_t=list(range(N))
        list_t.remove(m)
        list_t.remove(n)
        for t in list_t:
            if A[m][n]>A[m][t]+A[t][n]:
                result=-1                
                isbreak=True
                break
            elif A[m][n]==A[m][t]+A[t][n] and result!=-1:
                flag=False
                break
        if flag and result!=-1:
            result+=A[m][n]
        else:
            flag=True
        if isbreak:
            break
    if isbreak:
        break
print(result)
### BUGGY CODE ###

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

### FIXED CODE ###

import sys
input = sys.stdin.readline
N=int(input())
L=list(map(int,input().split()))
L.sort()
ans=0
for i in range(N-2):
 mid =i+1
 l=0
 r=i+2
 while r<N:
  if L[r]-L[l]<L[mid]:
   ans+=(mid-l)
   r+=1
  else:
   if l==mid-1:
    r+=1
   else:
    l+=1
print(ans)
### BUGGY CODE ###

def list_up_next_games(players):
    games = set()
    for p in players:
        if A[p]:
            opponent = A[p][-1] - 1
            if A[opponent][-1] - 1 == p:
                if p < opponent:
                    games.add((p, opponent))
                else:
                    games.add((opponent, p))
    return(set(games))


N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
for i in range(N):
    A[i].reverse()

remain_games = []
for i in range(N):
    for j in range(i+1,N):
        remain_games.append((i,j))

games = list_up_next_games(list(range(N)))

days = 0
while games:
    days += 1
    players = []
    for game in games:
        remain_games.remove(game)
        A[game[0]].pop()
        A[game[1]].pop()
        players.append(game[0])
        players.append(game[1])
    games = list_up_next_games(players)
if remain_games:
    print(-1)
else:
    print(days)

### FIXED CODE ###

def list_up_next_games(players):
    games = set()
    for p in players:
        if A[p]:
            opponent = A[p][-1] - 1
            if A[opponent][-1] - 1 == p:
                if p < opponent:
                    games.add((p, opponent))
                else:
                    games.add((opponent, p))
    return(games)

N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
for i in range(N):
    A[i].reverse()

games = list_up_next_games(list(range(N)))

done_games = []
days = 0
while games:
    days += 1
    players = []
    for game in games:
        done_games.append(game)
        A[game[0]].pop()
        A[game[1]].pop()
        players.append(game[0])
        players.append(game[1])
    games = list_up_next_games(players)

if len(done_games) == N*(N-1)//2:
    print(days)
else:
    print(-1)
### BUGGY CODE ###

import copy
N=int(input())
X=list(map(int,input().split()))
l=copy.copy(X)
for i in range(N):
    X.remove(l[i])
    X.sort(reverse=True)
    print(X[int((N-2)/2)])
    X.insert(i,l[i])

### FIXED CODE ###

N=int(input())
X=list(map(int,input().split()))
y=sorted(X,reverse=True)
for i in X:
    if i<y[(N-2)//2]:
        print(y[(N-2)//2])
    else:
        print(y[N//2])
### BUGGY CODE ###

import math
N,K=map(int,input().split())
import heapq
A=list(map(int,input().split()))

h=[(-A[i],1) for i in range(len(A))]
heapq.heapify(h)
for i in range(K):
  a=heapq.heappop(h)
  b=a[0]
  c=a[1]
  heapq.heappush(h,(c*b/(c+1),c+1))


ans=heapq.heappop(h)
print(math.ceil(-ans[0]))


### FIXED CODE ###

import math
N,K=map(int,input().split())
import heapq
A=list(map(int,input().split()))

def isok(x):
  c=0
  for i in range(N):
    c+=math.ceil(A[i]/x)-1
  if c<=K:
    return True
  else:
    return False
start=0
end=max(A)
mid=(start+end)//2
while end-start>1:
  mid=(start+end)//2
  if isok(mid)==True:
    end=mid
  else:
    start=mid
print(end)
### BUGGY CODE ###

import math

n = int(input())
A = [None]*n
A = input().split()
T = 1
for i in A:
    T *= int(i)
if T > pow(10,18):
    print(-1)
else:
    print(T)

### FIXED CODE ###

n = int(input())
res = 1
a = list(map(int,input().split()))
if 0 in a:
    print(0)
else:
    for i in range(n):
        res *= a[i]
        if res > 10**18:
            print(-1)
            quit()
    print(res)
### BUGGY CODE ###

N, K = map(int, input().split())
A = [int(x) for x in input().split()]
for _ in range(K):
    imos = [0] * (N+1)
    for i in range(N):
        left = max(0, i-A[i])
        right = min(N-1, i+A[i])+1
        imos[left] += 1
        imos[right] += -1

    next_A = [0] * N
    next_A[0] = imos[0]
    for i in range(1, N):
        next_A[i] = next_A[i-1] + imos[i]
    A = next_A

    is_all_max = True
    for i in range(N):
        if A[i] != N:
            is_all_max = False
            break
    if is_all_max:
        break
print(" ".join([str(x) for x in A]))


### FIXED CODE ###

from numba import jit


@jit
def solve(N, K, A):
    for _ in range(K):
        imos = [0] * (N+1)
        for i in range(N):
            left = max(0, i-A[i])
            right = min(N-1, i+A[i])+1
            imos[left] += 1
            imos[right] += -1

        next_A = [0] * N
        next_A[0] = imos[0]
        for i in range(1, N):
            next_A[i] = next_A[i-1] + imos[i]

        if A == next_A:
            return A
        A = next_A
    return A


N, K = map(int, input().split())
A = [int(x) for x in input().split()]
print(" ".join([str(x) for x in solve(N, K, A)]))
### BUGGY CODE ###

n = int(input())
a = [0 for _ in range(n)]
for i in range(n):
	a[i] = int(input())
for i in range(n):
	b = [a[j] for j in range(n)]
	b[i] = 0
	print(max(b))

### FIXED CODE ###

n = int(input())
a = [0 for _ in range(n)]
for i in range(n):
	a[i] = int(input())
maxa = max(a)
basho = a.index(maxa)
a[basho] = 0
for i in range(n):
	if i != basho:
		print(maxa)
	else:
		print(max(a))
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
for i in range(q):
    l,r=map(int,input().split())
    t=s[l-1:r]
    print(t.count('AC'))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
c=[0]
t=0
for i in range(1,n):
    t+=1 if (s[i-1]=='A' and s[i]=='C') else 0
    c.append(t)
for i in range(q):
    l,r=map(int,input().split())
    print(c[r-1]-c[l-1])
### BUGGY CODE ###

import numpy as np
n,k = map(int, input().split())
As = list(map(int, input().split()))

def f(x):
    # サイズxで切る
    cnt = 0
    for a in As:
        # 斬らなければイケない本数
        cnt += int(np.ceil(a/x))-1
    # 斬らなければいけない本数がk本以下
    return cnt <= k

l = 10**-6
r = 10**9
while r-l > 10**-1:
    # print(l,r)
    m = (l+r)/2
    if f(m):
        r = m
    else:
        l = m
print(int(np.ceil(l)))

### FIXED CODE ###

n,k = map(int, input().split())
As = list(map(int, input().split()))

def f(x):
    # サイズxで切る
    cnt = 0
    for a in As:
        # 斬らなければイケない本数
        cnt += int((a-0.01)/x)
        if cnt > k:
            return False
    # 斬らなければいけない本数がk本以下
    return cnt <= k

l = 10**-2
r = 10**9
while r-l > 10**-1:
    m = (l*r)**0.5
    if f(m):
        r = m
    else:
        l = m
print(int(l)+1)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
t = S.count('AC')
L = []
R = []
for i in range(N):
    L.append(S[:i].count('AC'))
    R.append(S[i:].count('AC'))
for i in range(Q):
    l, r = map(int, input().split())
    print(t-L[l]-R[r-1])


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = S.count('AC')
L = [0]
R = [0]
for i in range(N-1):
    L.append(L[i]+1 if S[i:i+2] == 'AC' else L[i])
    R.append(R[i]+1 if S[N-i-2:N-i] == 'AC' else R[i])
R.reverse()
for i in range(Q):
    l, r = map(int, input().split())
    print(t-L[l-1]-R[r-1])
### BUGGY CODE ###

n = int(input())

time = [0]+list(map(int,input().split()))+[0]
v = [0] + list(map(int,input().split()))+[0]

lines = []
t = 0
lines.append((-1,0,0))
for i in range(1,n+1):
    lines.append((t,t+time[i],v[i]))
    t+=time[i]

lines.append((t,t+1,0))
def ff(p,x):
    x1,x2,vv = p
    if x<x1:
        return vv+x1-x
    elif x>x2:
        return vv+x-x2
    else:
        return vv
def f(x):
    speed = 10**18
    for line in lines:
        speed = min(speed,ff(line,x))
    return speed
dp = [0]*(2*t)
for i in range(2*t):
    dp[i] = f(i/2)
dp.append(0)
res = 0
for a in range(2*t):
    res += 0.25*(dp[a]+dp[a+1])
print(res)


### FIXED CODE ###

n = int(input())

time = [0]+list(map(int,input().split()))+[0]
v = [0] + list(map(int,input().split()))+[0]

lines = []
t = 0
lines.append((-1,0,0))
for i in range(1,n+1):
    lines.append((t,t+time[i],v[i]))
    t+=time[i]
lines.append((t,t+1,0))
def f(x):
    speed = 10**18
    for x1,x2,vv in lines:
        if x<x1:
            speed = min(speed,vv+x1-x)
        elif x>x2:
            speed = min(speed,vv+x-x2)
        else:
            speed = min(speed,vv)
    return speed
dp = [0]*(2*t)
for i in range(2*t):
    dp[i] = f(i/2)
dp.append(0)
res = 0
res = sum(dp)*2-dp[0]-dp[-1]
print(res*0.25)
### BUGGY CODE ###

import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

def calc(i,j):
    d = defaultdict(lambda:defaultdict(int))
    ret = -float('inf')
    if j==0:
        return 0
    if (N-i+1)//2 < j:
        return ret
    else:
        if i <= N-1:
            if d[i+2][j-1]:
                ret = max(ret,d[i+2][j-1])
            else:
                ret = max(ret,A[i]+calc(i+2,j-1))
        if i+1 <= N-1:
            if d[i+3][j-1]:
                ret = max(ret,d[i+3][j-1])
            else:
                ret = max(ret,A[i+1]+calc(i+3,j-1))
        d[i][j] = ret
        return ret


N = I()
A = LI()


if N%2 == 0:
    print(calc(0,N//2))
else:
    a1 = calc(0,N//2)
    n = 0
    for i in range(2,N,2):
        n += A[i]
    print(max(a1,n))


### FIXED CODE ###

import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
A = LI()


if N%2 == 0:
    d = defaultdict(lambda:defaultdict(lambda:-float('inf')))
    d[0][1] = A[0]
    d[1][1] = max(A[0],A[1])
    for i in range(2,N):
        if i%2 == 0:
            for j in [i//2,i//2+1]:
                d[i][j] = max(d[i-2][j-1]+A[i],d[i-1][j])
        else:
            for j in [(i+1)//2]:
                d[i][j] = max(d[i-2][j-1]+A[i],d[i-1][j])
    print(d[N-1][N//2])
else:
    d = defaultdict(lambda:defaultdict(lambda:-float('inf')))
    d[0][1] = A[0]
    d[1][1] = max(A[0],A[1])
    for i in range(2,N):
        if i%2 == 0:
            for j in [i//2,i//2+1]:
                d[i][j] = max(d[i-2][j-1]+A[i],d[i-1][j])
        else:
            for j in [i//2,i//2+1]:
                d[i][j] = max(d[i-2][j-1]+A[i],d[i-1][j])
    a1 = d[N-1][N//2]
    n = 0
    for i in range(2,N,2):
        n += A[i]
    print(max(n,a1))
### BUGGY CODE ###

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

dp = [0] * (S + 1)

ans = 0
for a in A:
    dp[0] += 1
    for s in range(S + 1)[::-1]:
        if s + a <= S:
            dp[s + a] = (dp[s + a] + dp[s]) % MOD
    ans += dp[S]
    ans %= MOD

print(ans)


### FIXED CODE ###

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

dp = [0] * (S + 1)
ans = 0

for i, a in enumerate(A):
    for s in range(S + 1)[:: -1]:
        if s + a <= S:
            dp[s + a] += dp[s]
    if a <= S:
        dp[a] += (i + 1)
    ans += dp[S]

print(ans % MOD)