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

N,K = map(int,input().split())
A = list(map(int,input().split()))
B = []

def product(array):
  a = 1
  for k in array:
    a *= k
  return a

for i in range(N-K+1):
  B.append(product(A[i:i+K]))
  
count = 0
for b in B:
  if count == 0:
    b_old = b
  else:
    if b > b_old:
      print('Yes')
    else:
      print('No')
  b_old = b
  count += 1

### FIXED CODE ###

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

for i in range(N-K):
  if A[i] < A[i+K]:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Jun 23 21:04:33 2020

@author: naoki
"""

N = int(input()) # input the row A length "N" 
A = list(map(int,input().split())) # input the row of A 
Q = int(input()) # input the number of trying operation 
BC = [list(map(int,input().split())) for i in range(Q)]

for i in range(Q):
    S = 0 # Sum of all conponents of the row "A"
    for j in range(N):
        if A[j] == BC[i][0]:
            A[j] = BC[i][1]
        S +=A[j]
    print(S)



### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Jun 23 21:04:33 2020

@author: naoki
"""

N = int(input()) # input the row A length "N" 
A = list(map(int,input().split())) # input the row of A 
Q = int(input()) # input the number of trying operation 
BC = [list(map(int,input().split())) for i in range(Q)]
S = 0
num = [0 for i in range(100001)] 
for i in A:
    S += i # Sum of all conponents of the row "A"
    num[i]+=1 

for B,C in BC:
    S = S + (C - B) * num[B]
    num[C] += num[B]
    num[B] = 0 
    print(S)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
 
n, k, q =map(int, input().split())
a = []
m = [k]*n
for i in range(q):
  a = int(input())
  m[a-1]+=1
  for j in range(n):
    m[j]-=1

for i in range(n):
  if m[i]>0:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

# -*- coding: utf-8 -*-
 
n, k, q =map(int, input().split())
a = [int(input()) for i in range(q)]

p = [0]*(n+1)

for i in range(q):
  p[a[i]] += 1
  

for i in range(1,n+1):
  if p[i]>q-k:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

import bisect
n=int(input())
a=[int(input())]
for i in range(n-1):
    t=int(input())
    b=bisect.bisect_left(a[::-1], t)
    if b==0:
        a.append(t)
    else:
        a[-b]=t
print(len(a))

### FIXED CODE ###

import bisect
from collections import deque
n=int(input())
a=deque([int(input())])
for i in range(n-1):
    t=int(input())
    b=bisect.bisect_left(a, t)
    if b==0:
        a.appendleft(t)
    else:
        a[b-1]=t
    #print(a)
print(len(a))
### BUGGY CODE ###

L, R = (int(x) for x in input().split())

min = 2020

for i in range(L, R):
    for j in range(i + 1, R + 1):
        i_ = i % 2019
        j_ = j % 2019
        mod_ij = i * j % 2019
        if min > mod_ij:
            min = mod_ij

print(min)



### FIXED CODE ###

L, R = (int(x) for x in input().split())
 
min = 2020

counter1 = 0
counter2 = 0

for i in range(L, R):
    counter1 += 1
    if counter1 > 20190:
        break
    for j in range(i + 1, R + 1):
        counter2 += 1
        if counter2 > 20190:
            break
        i_ = i % 2019
        j_ = j % 2019
        mod_ij = i_ * j_ % 2019
        if min > mod_ij:
            min = mod_ij
        
 
print(min)
### BUGGY CODE ###

N, Q = map(int, input().split())

S = input()
items = []
for i in range(Q):
    t, d = input().split()
    items.append((t, d))

left_ok = -1
left_ng = N

while left_ng - left_ok > 1:
    mid = (left_ok + left_ng) // 2
    flag = False
    tmp = mid
    for t, d in items:
        if t == S[tmp]:
            if d == "L":
                if tmp - 1 == -1:
                    flag = True
                    break
                tmp -= 1
            else:
                if tmp + 1 >= N:
                    break
                tmp += 1

    if flag:
        left_ok = mid
    else:
        left_ng = mid


right_ok = N
right_ng = -1

while right_ok - right_ng > 1:
    mid = (right_ok + right_ng) // 2
    flag = False
    tmp = mid
    for t, d in items:
        if t == S[tmp]:
            if d == "R":
                if tmp + 1 == N:
                    flag = True
                    break
                tmp += 1
            else:
                if tmp - 1 == -1:
                    break
                tmp -= 1

    if flag:
        right_ok = mid
    else:
        right_ng = mid
ans = N
if left_ok != -1:
    ans -= left_ok + 1

if right_ok != N:
    ans -= N - right_ok

if left_ok >= right_ok:
    ans = 0

print(ans)


### FIXED CODE ###

N, Q = map(int, input().split())

S = input()
items = []
for i in range(Q):
    t, d = input().split()
    items.append((t, d))

left_ok = -1
left_ng = N

while left_ng - left_ok > 1:
    mid = (left_ok + left_ng) // 2
    flag = False
    start = S[mid]
    tmp = mid
    for t, d in items:
        if t == start:
            if d == "L":
                if tmp - 1 == -1:
                    flag = True
                    break
                start = S[tmp - 1]
                tmp -= 1
            else:
                if tmp + 1 >= N:
                    break
                start = S[tmp + 1]
                tmp += 1

    if flag:
        left_ok = mid
    else:
        left_ng = mid


right_ok = N
right_ng = -1

while right_ok - right_ng > 1:
    mid = (right_ok + right_ng) // 2
    flag = False
    start = S[mid]
    tmp = mid
    for t, d in items:
        if t == start:
            if d == "R":
                if tmp + 1 == N:
                    flag = True
                    break
                start = S[tmp + 1]
                tmp += 1
            else:
                if tmp - 1 == -1:
                    break
                start = S[tmp - 1]
                tmp -= 1

    if flag:
        right_ok = mid
    else:
        right_ng = mid
ans = N
if left_ok != -1:
    ans -= left_ok + 1

if right_ok != N:
    ans -= N - right_ok

if left_ok >= right_ok:
    ans = 0

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

def BFS(Bs,del_idx,result):
    if Bs==[1]:
        return result
    
    if del_idx!=None:
        del Bs[del_idx]

    for i,b in enumerate(Bs):
        if i+1==b:
            DBs=Bs.copy()
            result.append(i+1)
            out=BFS(DBs,i,result)
            if out:
                return out
            else:
                del result[-1]

    return None


def Solve():
    output=[]
    N=int(input())
    Bs=[int(x) for x in input().split()]
    return BFS(Bs,None,[])
        

        
result=Solve()
if result:
    result.reverse()
    for r in result:
        print(r)
else:
    print(-1)


### FIXED CODE ###

def BFS(Bs,del_idx,result):
    if Bs==[1]:
        return result
    
    if del_idx!=None:
        del Bs[del_idx]


    for i,b in enumerate(Bs):
        if b>i+1:
            return None
        
    for i,b in enumerate(Bs):
        if i+1==b:
            DBs=Bs.copy()
            result.append(i+1)
            out=BFS(DBs,i,result)
            if out:
                return out
            else:
                del result[-1]

    return None


def Solve():
    output=[]
    N=int(input())
    Bs=[int(x) for x in input().split()]
    return BFS(Bs,None,[])
        

        
result=Solve()
if result:
    result.reverse()
    for r in result:
        print(r)
else:
    print(-1)
### BUGGY CODE ###

def main():
    N, W = map(int, input().split())
    VN = []
    WN = []
    for i in range(N):
        w, v = map(int, input().split())
        WN.append(w)
        VN.append(v)

    ans = 0
    mask = 0
    while mask < 1<<N:
        i = 0
        w = []
        v = []
        while i < N:
            if mask & 1<<i:
                w.append(WN[i])
                v.append(VN[i])
            i += 1
        if sum(w) <= W:
            ans = max(ans, sum(v))
        mask += 1

    print(ans)

main()


### FIXED CODE ###

def main():
    N, W = map(int, input().split())
    w1 = [0, 0]
    w2 = [0, 0]
    w3 = [0, 0]
    w4 = [0, 0]
    v1 = []
    v2 = []
    v3 = []
    v4 = []
    i = 0
    while i < N:
        w, v = map(int, input().split())
        if i == 0 or w == w1[0]:
            w1[0] = w
            w1[1] += 1
            v1.append(v)
        elif w == w1[0] + 1:
            w2[0] = w
            w2[1] += 1
            v2.append(v)
        elif w == w1[0] + 2:
            w3[0] = w
            w3[1] += 1
            v3.append(v)
        elif w == w1[0] + 3:
            w4[0] = w
            w4[1] += 1
            v4.append(v)
        i += 1

    v1.sort(reverse=True)
    v2.sort(reverse=True)
    v3.sort(reverse=True)
    v4.sort(reverse=True)

    ans = []
    for i in range(w1[1] + 1):
        for j in range(w2[1] + 1):
            for k in range(w3[1] + 1):
                for l in range(w4[1] + 1):
                    w = w1[0] * i + w2[0] * j + w3[0] * k + w4[0] * l
                    v = sum(v1[:i] + v2[:j] + v3[:k] + v4[:l])
                    if w <= W:
                        ans.append(v)

    print(max(ans))

main()
### BUGGY CODE ###

n = int(input())
A = list(map(int,input().split()))
ans = float('inf')
for i in range(1, n):
    x = A[:i]
    y = A[i:]
    sum_x = sum(x)
    sum_y = sum(y)
    ans = min(ans, abs(sum_x - sum_y))
print(ans)

### FIXED CODE ###

import numpy as np
import bisect
n = int(input())
A = list(map(int,input().split()))
cs = np.cumsum(A).tolist()
mid = sum(A)//2
idx = bisect.bisect_left(cs, mid)
ans = float('inf')
for i in range(max(1, idx-1), min(idx+2, n)):
    x = A[:i]
    y = A[i:]
    sum_x = sum(x)
    sum_y = sum(y)
    ans = min(ans, abs(sum_x - sum_y))
print(ans)
### BUGGY CODE ###

import sys

n = int(sys.stdin.readline().rstrip())
a = list(map(int, sys.stdin.readline().rstrip().split()))
a.sort()
# print(a)
ans = 0
for i in range(n):
    a = a[1:]
    a = a[:-1]
    ans += a[-1]
    a = a[:-1]
print(ans)

### FIXED CODE ###

import sys

n = int(sys.stdin.readline().rstrip())
a = list(map(int, sys.stdin.readline().rstrip().split()))
a.sort()

# print(a)
ans = 0
a = a[n:]
a.reverse()
print(sum(a[1::2]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
MOD = 1000000007
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

S = input()
X,Y=LI()

while S and S[0] == 'F':
    S = S[1:]
    X -= 1

isX = True
cur = 0
xs = []
ys = []
for i in range(len(S)):
    if S[i] == 'T':
        if cur:
            if isX:
                xs.append(cur)
            else:
                ys.append(cur)
        isX = not isX
        cur = 0
    elif S[i] == 'F':
        cur += 1

if cur:
    if isX:
        xs.append(cur)
    else:
        ys.append(cur)

memo1 = {}
def dp1(x, i):
    if i < 0: return x == 0
    if (x, i) in memo1: return memo1[(x,i)]
    res = dp1(x - xs[i], i-1) or dp1(x + xs[i], i-1)
    memo1[(x,i)] = res
    return res

memo2 = {}
def dp2(x, i):
    if i < 0: return x == 0
    if (x, i) in memo2: return memo2[(x,i)]
    res = dp2(x - ys[i], i-1) or dp2(x + ys[i], i-1)
    memo2[(x,i)] = res
    return res


# print(xs, ys)
print('Yes' if dp1(X, len(xs)-1) and dp2(Y, len(ys)-1) else 'No')


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
MOD = 1000000007
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

S = input()
X,Y=LI()

while S and S[0] == 'F':
    S = S[1:]
    X -= 1

isX = True
cur = 0
xs = []
ys = []
for i in range(len(S)):
    if S[i] == 'T':
        if cur:
            if isX:
                xs.append(cur)
            else:
                ys.append(cur)
        isX = not isX
        cur = 0
    elif S[i] == 'F':
        cur += 1

if cur:
    if isX:
        xs.append(cur)
    else:
        ys.append(cur)

X=abs(X)
Y=abs(Y)
xs.sort()
ys.sort()
xss = [0]
yss = [0]
for i in xs:
    xss.append(xss[-1]+i)
for i in ys:
    yss.append(yss[-1]+i)

memo1 = {}
def dp1(x, i):
    if abs(x) > xss[i+1]: return False
    if i < 0: return x == 0
    if (x, i) in memo1: return memo1[(x,i)]
    res = dp1(x - xs[i], i-1) or dp1(x + xs[i], i-1)
    memo1[(x,i)] = res
    return res

memo2 = {}
def dp2(x, i):
    if abs(x) > yss[i+1]: return False
    if i < 0: return x == 0
    if (x, i) in memo2: return memo2[(x,i)]
    res = dp2(x - ys[i], i-1) or dp2(x + ys[i], i-1)
    memo2[(x,i)] = res
    return res


# print(xs, ys)
print('Yes' if dp1(X, len(xs)-1) and dp2(Y, len(ys)-1) else 'No')
### BUGGY CODE ###

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

def calc_exp(n):
    exp=1+(n-1)*0.5
    return exp

mx=0
for i in range(n-k+1):
    tmp=sum(p[i:i+k])
    if mx<tmp:
        ind=i
        mx=tmp
        
ans=0
for i in range(k):
    ans+=calc_exp(p[ind+i])
    
print(ans)

### FIXED CODE ###

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

def calc_exp(n):
    exp=1+(n-1)*0.5
    return exp

tmp=sum(p[:k])
mx=tmp
ind=0
for i in range(1,n-k+1):
    # tmp=sum(p[i:i+k])
    tmp-=p[i-1]
    tmp+=p[i+k-1]
    if mx<tmp:
        ind=i
        mx=tmp
        
ans=0
for i in range(k):
    ans+=1+(p[ind+i]-1)*0.5
    
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
a,c=[],[]
for _ in range(m):
  a.append(list(map(int,input().split()))[0])
  c.append(sum((1<<(int(i)-1)) for i in input().split()))
inf=float('inf')
dp=[inf]*(1<<n)
dp[0]=0
for i in range(2**n):
  for j in range(m):
    dp[i|c[j]]=min(dp[i|c[j]],dp[i]+a[j])
print(dp[-1] if inf!=dp[-1] else-1)


### FIXED CODE ###

n,m=map(int,input().split())
a,c=[],[]
for _ in range(m):
  a.append(list(map(int,input().split()))[0])
  c.append(sum((1<<(int(i)-1)) for i in input().split()))
inf=float('inf')
# dp[i]: 状態がbin(i)の時のの費用の最小値
# bin(i)のj桁が1: j番目の宝箱を開けることが可能
dp=[inf]*(1<<n)
dp[0]=0
for i in range(2**n):
  for j in range(m):
    dp[i|c[j]]=min(dp[i|c[j]],dp[i]+a[j])
print(dp[-1] if inf!=dp[-1] else-1)
### BUGGY CODE ###

D, G = map(int, input().split())
ncs = [list(map(int, input().split())) for _ in range(D)]
ns = [x[0] for x in ncs]
cs = [x[1] for x in ncs]

def f(i, rn, rp):
    if i == 0:
        if ns[0] < rn:
            return False
        rp -= 100 * rn
        if ns[0] == rn:
            rp -= cs[0]
        return rp <= 0
    if rn < min(ns[:i+1]):
        for j in range(i, -1, -1):
            n = min((ns[j], rn))
            rp -= (j + 1) * 100 * n
            rn -= n
            if rn == 0:
                break
        return rp <= 0
    for n in range(min((ns[i], rn)) + 1):
        p = (i + 1) * 100 * n
        if n == ns[i]:
            p += cs[i]
        if n == rn:
            return p >= rp
        if p >= rp:
            return True
        if f(i - 1, rn - n, rp - p):
            return True
    return False

mn = 1
mx = sum(ns)
while mn < mx:
    x = mn + ((mx - mn) // 2)
    if f(D - 1, x, G):
        mx = x
    else:
        mn = x + 1
print(mn)


### FIXED CODE ###

import functools
D, G = map(int, input().split())
G = G // 100
sumn = 0
ns = [0] * (D + 1)
cs = [0] * (D + 1)
for i in range(1, D + 1):
    n, c = map(int, input().split())
    ns[i] = n
    cs[i] = c // 100
    sumn += n

minn = [0] * (D + 1)
for i in range(1, D + 1):
    minn[i] = min(ns[1:i+1])

@functools.lru_cache(maxsize=None)
def f(i, rn):
    if i == 1:
        if ns[1] < rn:
            return -1
        p = rn
        if ns[1] == rn:
            p += cs[1]
        return p
    if rn < minn[i]:
        p = 0
        for j in range(i, 0, -1):
            n = min((ns[j], rn))
            p += j * n
            if n == rn:
                break
            rn -= n
        return p
    maxp = 0
    for n in range(min((ns[i], rn)) + 1):
        p = i * n
        if n == ns[i]:
            p += cs[i]
        np = f(i - 1, rn - n)
        if np >= 0:
            p += np
            if maxp < p:
                maxp = p
    return maxp

mn = 1
mx = sumn
while mn < mx:
    x = mn + ((mx - mn) // 2)
    if G <= f(D, x):
        mx = x
    else:
        mn = x + 1
print(mn)
### BUGGY CODE ###

N = int(input())
S = list(input())

a = []
ans = 0

for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            t = S[i]+S[j]+S[k]
            if not t in a:
                a.append(t)
                ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = list(input())

ans = 0

for i in range(1000):
    t = str(i)
    t = t.zfill(3)
    now = t[0]
    count = 0
    for j in S:
        if count == 0 and now == j:
            now = t[1]
            count += 1
            continue
        if count == 1 and now == j:
            now = t[2]
            count += 1
            continue
        if count == 2 and now == j:
            ans += 1
            break

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

# C - Fennec vs Monster

n,k = map(int,input().split())
h = list(map(int,input().split()))
h.sort(reverse=True)
if k >= n:
    k = n
for i in range(k):
    del h[0]

print(sum(h))


### FIXED CODE ###

# C - Fennec vs Monster

n,k = map(int,input().split())
h = list(map(int,input().split()))
h.sort(reverse=True)
if k >= n:
    k = n
h2 = h[k:]

print(sum(h2))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

N = int(input())

T,A = map(int, input().split())

for i in range(N-1):
    t,a = map(int, input().split())
    tmp1,tmp2 = t,a
    # 比はそのままで、あり得る投票数まで値を増やす
    while t < T or a < A:
        t += tmp1
        a += tmp2
    T = t
    A = a

print(T + A)

### FIXED CODE ###

# -*- coding: utf-8 -*-

N = int(input())

T,A = map(int, input().split())

for i in range(N-1):
    t,a = map(int, input().split())
    tmp1,tmp2 = 1,1
    # ループで足していくより、1回で出せる方法にする
    if t < T:
        # 切り上げはmath.ceilより演算子のみのが速い
        tmp1 = -(-T // t)
    if a < A:
        tmp2 = -(-A // a)
    # 多く増やす必要のある方に合わせて、同じ比で両方増やす
    T = t * max(tmp1,tmp2)
    A = a * max(tmp1,tmp2)

print(T + A)
### BUGGY CODE ###

H, W = list(map(int, input().split()))
grid = []
for _ in range(H):
    grid.append(list(input()))
dist_grid = [[-1 for _ in range(W)] for __ in range(H)]

queue = [(0, 0, 1)]
while queue:
    h, w, cnt = queue.pop(0)
    dist_grid[h][w] = cnt
    nexts = [(h+1, w, cnt+1), (h-1, w, cnt+1), (h, w+1, cnt+1), (h, w-1, cnt+1)]
    for y, x, c in nexts:
        if 0 <= y and y < H and 0 <= x and x < W:
            if dist_grid[y][x] == -1 and grid[y][x] != '#':
                queue.append((y, x, c))
            
sharp_num = 0
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            sharp_num += 1

if dist_grid[-1][-1] == -1:
    print(-1)
else:
    print(H * W - dist_grid[-1][-1] - sharp_num)





### FIXED CODE ###

import sys
from collections import deque
 
h,w = map(int, sys.stdin.readline().split())
maze = [list(sys.stdin.readline()) for _ in range(h)]
dis = [[-1 for _ in range(w)] for _ in range(h)]
 
que = deque()
que.append((0,0))
dis[0][0] = 1
 
while que:
    y,x = que.popleft()
    for dx, dy in ((1,0), (0,1), (-1, 0), (0, -1)):
        nx = x + dx
        ny = y + dy
        if (nx < 0) or (nx > w-1) or (ny < 0) or (ny > h-1): continue
        if (maze[ny][nx] == '.') and (dis[ny][nx] == -1):
            dis[ny][nx] = dis[y][x] + 1
            que.append((ny, nx))
 
ans = 0
black_num = 0
for m in maze:
    black_num += m.count('#')
 
if dis[h-1][w-1] == -1:
    ans = -1
else:
    ans = w*h - black_num - dis[h-1][w-1]
 
print(ans)
### BUGGY CODE ###

def op2(f, c):
  if r == 0:
    if f == "1":
      return (c + S)
    elif f == "2":
      return (S + c)

  if r == 1:
    if f == "2":
      return (c + S)
    elif f == "1":
      return (S + c)

S = input()
Q = int(input())
v = [list(input().split()) for i in range(Q)]
r = 0

for val in v:
  if val[0] == "1":
    if r == 0:
      r = 1
    elif r == 1:
      r = 0
  elif val[0] == "2":
    S = op2(val[1], val[2])
    
if r == 0:
  print(S)
else:
  print(S[::-1])

### FIXED CODE ###

def op2(f, c, r):
  if r == 0:
    if f == "1":
      left.append(c)
    elif f == "2":
      right.append(c)

  if r == 1:
    if f == "1":
      right.append(c)
    elif f == "2":
      left.append(c)

S = input()
Q = int(input())
v = [list(input().split()) for i in range(Q)]
rev = 0
left = []
right = []

for val in v:
  if val[0] == "1":
    if rev == 0:
      rev = 1
    elif rev == 1:
      rev = 0
  elif val[0] == "2":
    op2(val[1], val[2], rev)

nleft = left[::-1]
ans = "".join(nleft + [S] + right)

if rev == 0:
  print(ans)
else:
  print(ans[::-1])
### BUGGY CODE ###

N = int(input())
S = input()
Q = int(input())
ks = list(map(int,input().split()))

for k in ks:
    d = m = 0
    dm = dmc = 0
    for i in range(N):
        if i >= k:
            if S[i-k] == 'D':
                d -= 1
                dm -= m
            elif S[i-k] == 'M':
                m -= 1
        if S[i] == 'D':
            d += 1
        elif S[i] == 'M':
            m += 1
            dm += d
        elif S[i] == 'C':
            dmc += dm
    print(dmc)

### FIXED CODE ###

import sys
rl = sys.stdin.readline
N = int(rl())
S = rl()
Q = int(rl())
ks = list(map(int,rl().split()))

ans = []
for k in ks:
    d = m = 0
    dm = dmc = 0
    for i in range(N):
        if i >= k:
            if S[i-k] == 'D':
                d -= 1
                dm -= m
            elif S[i-k] == 'M':
                m -= 1
        if S[i] == 'D':
            d += 1
        elif S[i] == 'M':
            m += 1
            dm += d
        elif S[i] == 'C':
            dmc += dm
    ans.append(dmc)

print(*ans,sep='\n')
### BUGGY CODE ###

N = int(input())
L = [int(i) for i in input().split()]

L_len = len(L)

L.sort(reverse=True)

count = 0
for i in range(0, L_len - 2):
    for j in range(i + 1, L_len - 1):
        left = j + 1
        right = L_len - 1
        length = L[i] - L[j]
        index = -1
        while right >= left  :
            center = int((left + right + 1)/2)
            if L[center] > length:
                index = 0
                left = center
                if left == right:
                    break

            else:
                right = center - 1
            

        if index != -1:
            count += right - j

print(count)

### FIXED CODE ###

N = int(input())
L = [int(i) for i in input().split()]

from bisect import bisect_left

L.sort()

count = 0
for i in range(0, N - 2):
    for j in range(i + 1, N - 1):
        length = L[i] + L[j]
        idx = bisect_left(L, length)
        count += idx - j - 1

print(count)