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

import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    iS = input().rstrip()

    S = []
    for i in range(N-1):
        S.append(abs(int(iS[i])-int(iS[i+1])))
    N -= 1

    f = FactorialUtils(N)
    n1 = n2 = 0
    for i in range(N):
        t = f.choose(N-1,i)
        #print(t,S[i])
        if S[i] == 1: n1 += t
        elif S[i] == 2: n2 += t
    if n1&1 and n2&1: print(1)
    elif n1&1: print(1)
    elif n2&1: print(2)
    else: print(0)
    #print(n1,n2)

class FactorialUtils:
    def __init__(self, n):
        self.fac = [1] * (n+1)
        for i in range(2, n+1): self.fac[i] = self.fac[i-1] * i

    def choose(self, n, r):
        if r < 0 or r > n: return 0
        return (self.fac[n] // self.fac[n-r]) // self.fac[r]

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    iS = input().rstrip()

    S = []
    for i in range(N-1):
        S.append(abs(int(iS[i])-int(iS[i+1])))
    N -= 1

    f = FactorialUtils(N)
    n1 = n2 = 0
    for i in range(N):
        t = f.choose(N-1,i)
        #print(t,S[i])
        if S[i] == 1: n1 += t
        elif S[i] == 2: n2 += t
    if n1&1 and n2&1: print(1)
    elif n1&1: print(1)
    elif n2&1 and n1==0: print(2)
    else: print(0)
    #print(n1,n2)

class FactorialUtils:
    def __init__(self, n):
        self.fac = [1] * (n+1)
        for i in range(2, n+1): self.fac[i] = self.fac[i-1] + (i&(-i)).bit_length()

    def choose(self, n, r):
        if r < 0 or r > n: return 0
        return 2 if (self.fac[n] - self.fac[n-r] - self.fac[r]) > 0 else 1

if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
s = input()
count = 0
num_list = [str(i).zfill(3) for i in range(1000)]
for i in range(len(num_list)):
    a = b = -1
    i100 = num_list[i][0]
    i10 = num_list[i][1]
    i1 = num_list[i][2]
    for j in range(len(s)-2):
        if s[j] == i100:
            a = j
            break
    if a != -1:
        for j in range(a+1,len(s)-1):
            if s[j] == i10:
                b = j
                break
    if b != -1:
        for j in range(b+1,len(s)):
            if s[j] == i1:
                count += 1
                break
print(count)


### FIXED CODE ###

import bisect
n = int(input())
s = input()
count = 0
num_ind_list = []
for i in range(10):
    num_ind_list.append([0])
for i in range(n):
    num_ind_list[int(s[i])].append(i)
for i in range(10):
    num_ind_list[i].append(30000)
for i in range(10):
    if len(num_ind_list[i]) != 2:
        for j in range(10):
            b = bisect.bisect_right(num_ind_list[j], num_ind_list[i][1])
            if num_ind_list[j][b] != 30000:
                for k in range(10):
                    c = bisect.bisect_right(num_ind_list[k], num_ind_list[j][b])
                    if num_ind_list[k][c] != 30000: count += 1
print(count)
### BUGGY CODE ###

#!/usr/bin/python3

s = input()
head = 1 #1:forward, -1: reverse

q = int(input())
sl = [ s[i] for i in range(len(s)) ]

for i in range(q):
    ql = input()
    if ql[0] == '1':
        head *= -1
    elif ql[0] == '2':
        (op, f, c) = ql.split()
        ht = 1
        if f == '1':
            ht = head
        else:
            #f == '2':
            ht = head * -1

        if ht == 1:
            sl.insert(0, c)
        else:
            sl.append(c)


if head == 1:
    print(''.join(sl))
else:
    print(''.join(reversed(sl)))


### FIXED CODE ###

#!/usr/bin/python3
from collections import deque

s = input()
head = 1 #1:forward, -1: reverse

q = int(input())
sl = [ s[i] for i in range(len(s)) ]
sq = deque(sl)


for i in range(q):
    ql = input()
    if ql[0] == '1':
        head *= -1
    elif ql[0] == '2':
        (op, f, c) = ql.split()
        ht = 1
        if f == '1':
            ht = head
        else:
            #f == '2':
            ht = head * -1

        if ht == 1:
            sq.appendleft(c)
        else:
            sq.append(c)


if head == 1:
    print(''.join(sq))
else:
    print(''.join(reversed(sq)))
### BUGGY CODE ###

# ABC143E - Travel by Car
def floyd_warshall(dist):
    """
    Compute the shortest paths of all pairs and modify dist.
    """
    V = len(dist)
    for i in range(V):  # intermediate point
        for j, c2 in enumerate(dist[j][i] for j in range(V)):  #  source
            for k, (c1, c3) in enumerate(zip(dist[j], dist[i])):  # target
                if c2 + c3 < c1:
                    dist[j][k] = c2 + c3


def main():
    # FW -> once more FW to edges <= L
    N, M, L, *X = map(int, open(0).read().split())
    ABC, ST = X[: 3 * M], X[3 * M + 1 :]
    INF = 1 << 60
    dist = [[INF] * (N + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        dist[i][i] = 0
    for v, u, cost in zip(*[iter(ABC)] * 3):
        dist[v][u] = dist[u][v] = cost
    floyd_warshall(dist)

    # assume distance within L as 1 and compute the number of fueling
    modified_dist = [[1 if x <= L else INF for x in d] for d in dist]
    floyd_warshall(modified_dist)
    ans = [
        modified_dist[s][t] - 1 if modified_dist[s][t] < INF else -1
        for s, t in zip(*[iter(ST)] * 2)
    ]
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()


### FIXED CODE ###

# ABC143E - Travel by Car
import numpy as np

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall


def main():
    # FW -> once more FW to edges <= L
    global L, G, dist, ancestors
    N, M, L, *X = map(int, open(0).read().split())
    ABC, ST = X[: 3 * M], X[3 * M + 1 :]
    A, B, C, S, T = ABC[::3], ABC[1::3], ABC[2::3], ST[::2], ST[1::2]

    G = csr_matrix((C, (A, B)), (N + 1, N + 1))
    dist = floyd_warshall(G, directed=0)

    modified_G = np.full((N + 1, N + 1), np.inf)
    np.fill_diagonal(modified_G, 0)
    modified_G[dist <= L] = 1
    modified_dist = floyd_warshall(modified_G, directed=0)
    modified_dist[modified_dist == np.inf] = 0
    modified_dist = (modified_dist).astype(int)
    
    ans = modified_dist[S, T] - 1
    print("\n".join(ans.astype(str)))


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

s=str(input())
t=str(input())
n,m=len(s),len(t)
ans=''
dp=[[0]*(m+1) for _ in range(n+1)]
for i in range(n):
  for j in range(m):
    if s[i]==t[j]:
      dp[i+1][j+1]=max(dp[i][j]+1,dp[i+1][j+1])
    else:
      dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
while m>0 and n>0:
  if s[n-1]==t[m-1]:ans=s[n-1]+ans;n-=1;m-=1
  elif dp[n][m]==dp[n-1][m]:n-=1
  else:m-=1
print(ans)

### FIXED CODE ###

s=str(input())
t=str(input())
n,m=len(s),len(t)
ans=''
dp=[[0]*(m+1) for _ in range(n+1)]
for i in range(n):
  for j in range(m):
    if s[i]==t[j]:
      dp[i+1][j+1]=max(dp[i][j]+1,dp[i+1][j+1])
    else:
      dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
while m>0 and n>0:
  if s[n-1]==t[m-1]:ans=s[n-1]+ans;n-=1;m-=1
  elif dp[n][m]==dp[n-1][m]:n-=1
  else:m-=1
print(ans)
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

ab = []

for i in a:
    for j in b:
        ab.append(i+j)
ab.sort(reverse=True)
ab = ab[:k]
c = c[:k]
abc = []
for i in ab:
    for j in c:
        abc.append(i+j)
abc.sort(reverse=True)

print(*abc[:k],sep="\n")

### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

ab = sorted(x+y for x in a for y in b)[:-k-1:-1]
abc = sorted(x+y for x in ab[:k] for y in c)[:-k-1:-1]
print(*abc, sep='\n')
### BUGGY CODE ###

import sys
n,m=map(int,input().split())

a=[]
b=[]

for i in range(m):
    c=[int(i) for i in input().split()]
    a.append(c[0])
    b.append(c[1])

l=[]

for i in range(m):
    if a[i]==1 or b[i]==1:
        l.append(a[i]*b[i])

for i in range(m):
    if a[i] in l and b[i]==n:
        print("POSSIBLE")
        sys.exit()
    if b[i] in l and a[i]==n:
        print("POSSIBLE")
        sys.exit()

print("IMPOSSIBLE")

### FIXED CODE ###

import sys
n,m=map(int,input().split())

a=[]
b=[]
l1=[False for i in range(n)]
ln=[False for i in range(n)]

for i in range(m):
    c=[int(i) for i in input().split()]
    a.append(c[0])
    b.append(c[1])
    if c[0]==1 or c[1]==1:
        l1[c[0]*c[1]]=True
    if c[0]==n or c[1]==n:
        ln[c[0]*c[1]//n]=True

for i in range(n):
    if l1[i] and ln[i]:
        print("POSSIBLE")
        sys.exit()

print("IMPOSSIBLE")
### BUGGY CODE ###

import random
from collections import defaultdict
from itertools import accumulate
n = int(input())
s = input()
mod = (1<<61)-1
base = 1000+random.randint(0,100)
power = [1]
for i in range(1,n):
	power.append((power[-1]*base)%mod)
hvalue = [0]
for i in range(n):
	hvalue.append((hvalue[-1]+(ord(s[i])*power[i]))%mod)
def rollinghash(l,r):
	return ((hvalue[r]-hvalue[l])*power[n-r])%mod
ans = 0
for i in range(1,n//2+1):
	dc = defaultdict((int))
	for j in range(n-i+1):
		x = rollinghash(j,i+j)
		if dc[x]:
			rg = dc[x]
			if rg<=j:
				ans = max(ans,i)
		else:
			dc[x] = i+j
print(ans)

### FIXED CODE ###

import random
from collections import defaultdict
from itertools import accumulate
import sys
input = sys.stdin.readline
n = int(input())
s = input().rstrip()
mod = (1<<61)-1
base = 1000+random.randint(0,100)
power = [1]
for i in range(1,n):
  power.append((power[-1]*base)%mod)
hvalue = [0]
for i in range(n):
  hvalue.append((hvalue[-1]+(ord(s[i])*power[i]))%mod)
def rollinghash(l,r):
  return ((hvalue[r]-hvalue[l])*power[n-r])%mod
def pun(i):
  dc = defaultdict(int)
  if i>n//2:
    return False
  for j in range(n-i+1):
    x = rollinghash(j,i+j)
    if dc[x]:
      rg =dc[x]
      if rg<=j:
        return True
    else:
      dc[x] = i+j
  return False
l=0
r=n//2+1
while l+1<r:
  mi=(l+r)//2
  if pun(mi):
    l=mi
  else:
    r=mi
print(l)
### BUGGY CODE ###

N,M = map(int,input().split())
a = [int(input()) for _ in range(M)]

if 1 in a:
  fibs = [1,0]
else:
  fibs = [1,1]

for i in range(2,N+1):
  if i in a:
    fibs[0] = fibs[1]
    fibs[1] = 0
  else:
    next = (fibs[1] + fibs[0]) % 1000000007
    fibs[0] = fibs[1]
    fibs[1] = next

print(fibs[-1])

### FIXED CODE ###

N,M = map(int,input().split())
a = [int(input()) for _ in range(M)]
a.sort(reverse=True)

if 1 in a:
  a.pop()
  fibs = [1,0]
else:
  fibs = [1,1]

for i in range(2,N+1):
  if len(a) > 0 and i == a[-1]:
    a.pop()
    fibs[0] = fibs[1]
    fibs[1] = 0
  else:
    next = fibs[1] + fibs[0]
    if next > 1000000007:
      next -= 1000000007
    fibs[0] = fibs[1]
    fibs[1] = next

print(fibs[-1])
### BUGGY CODE ###

H,W=map(int,input().split())
S=[input() for i in range(H)]

ans=0
tate=[]

for i in range(W):
    c=0
    ad=[]
    while(c<H):
        ad.append(S[c][i])
        c+=1
    tate.append(ad)

left=[]
right=[]
up=[]
down=[]

for i in range(H):
    tmp=S[i]
    cnt=0
    al = [0 for _ in range(W)]
    for j in range(W):
        if tmp[j]==".":
            cnt+=1
            al[j]=cnt
        else:
            cnt=0
    left.append(al)

for i in range(H):
    tmp = S[i]
    tmp=tmp[::-1]
    cnt = 0
    ar = [0 for _ in range(W)]
    for j in range(W):
        if tmp[j] == ".":
            cnt += 1
            ar[j] = cnt
        else:
            cnt = 0
    ar=ar[::-1]
    right.append(ar)

for j in range(W):
    tt=tate[j]
    cnt=0
    bl=[0 for i in range(H)]
    for k in range(H):
        if tt[k]==".":
            cnt+=1
            bl[k]=cnt
        else:
            cnt=0
    up.append(bl)

for j in range(W):
    tt=tate[j]
    tt=tt[::-1]
    cnt=0
    br=[0 for i in range(H)]
    for k in range(H):
        if tt[k]==".":
            cnt+=1
            br[k]=cnt
        else:
            cnt=0
    br=br[::-1]
    down.append(br)

for i in range(H):
    for j in range(W):
        gh=left[i][j]+right[i][j]+up[j][i]+down[j][i]-3
        ans=max(gh,ans)

print(ans)






### FIXED CODE ###

H,W=map(int,input().split())
S=[input() for i in range(H)]

ans=0
tate=[]

for i in range(W):
    c=0
    ad=[]
    while(c<H):
        ad.append(S[c][i])
        c+=1
    tate.append(ad)

left=[]
right=[]
up=[]
down=[]

for i in range(H):
    tmp=S[i]
    cnt=0
    al = [0 for _ in range(W)]
    for j in range(W):
        if tmp[j]==".":
            cnt+=1
            al[j]=cnt
        else:
            cnt=0
    left.append(al)

for i in range(H):
    tmp = S[i]
    tmp=tmp[::-1]
    cnt = 0
    ar = [0 for _ in range(W)]
    for j in range(W):
        if tmp[j] == ".":
            cnt += 1
            ar[j] = cnt
        else:
            cnt = 0
    ar=ar[::-1]
    right.append(ar)

for j in range(W):
    tt=tate[j]
    cnt=0
    bl=[0 for i in range(H)]
    for k in range(H):
        if tt[k]==".":
            cnt+=1
            bl[k]=cnt
        else:
            cnt=0
    up.append(bl)

for j in range(W):
    tt=tate[j]
    tt=tt[::-1]
    cnt=0
    br=[0 for i in range(H)]
    for k in range(H):
        if tt[k]==".":
            cnt+=1
            br[k]=cnt
        else:
            cnt=0
    br=br[::-1]
    down.append(br)

for i in range(H):
    for j in range(W):
        gh=left[i][j]+right[i][j]+up[j][i]+down[j][i]-3
        ans=max(gh,ans)

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

s=list(input())
q=int(input())
rev=0
for i in range(q):
    t=list(input().split())
    if t[0]=="1":
        rev=rev+1
    else:
        if t[1]=="1":
            if rev%2==0:
                s.insert(0,t[2])
            else:
                s.append(t[2])
        else:
            if rev%2==0:
                s.append(t[2])
            else:
                s.insert(0,t[2])
if rev%2==0:
    print("".join(s))
else:
    s.reverse()
    print("".join(s))



### FIXED CODE ###

from collections import deque
s=deque(list(input()))
q=int(input())
rev=0
for i in range(q):
    t=list(input().split())
    if t[0]=="1":
        rev=rev+1
    else:
        if t[1]=="1":
            if rev%2==0:
                s.appendleft(t[2])
            else:
                s.append(t[2])
        else:
            if rev%2==0:
                s.append(t[2])
            else:
                s.appendleft(t[2])
if rev%2==0:
    print("".join(s))
else:
    s.reverse()
    print("".join(s))
### BUGGY CODE ###

from collections import deque
from fractions import gcd
from functools import reduce
n = int(input())
v = list(map(int,input().split()))
v = deque(v)

def gcd_list(numbers):
    return reduce(gcd, numbers)

ans = 1
for i in range(n):
    v1 = v.popleft()
    g = gcd_list(v)
    v.append(v1)
    ans = max(ans,g)
print(ans)


### FIXED CODE ###

n = int(input())
v = list(map(int,input().split()))

def gcd(a,b):
  while b != 0:
    a, b = b, a % b
  return a

l_ans = [0] * n
g = 0
for i in range(1, n):
    g = gcd(g, v[i-1])
    l_ans[i] = g
r_ans = [0] * n
g = 0
for i in range(1, n):
    g = gcd(g, v[n-i])
    r_ans[i] = g
r_ans.reverse()
ans = 1
for i in range(n):
    ans = max(ans, gcd(l_ans[i], r_ans[i]))
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    H,W,M=mi()


    H_count = [0] * (H+1)
    W_count = [0] * (W+1)
    G = [[False] * (W+1) for _ in range(H+1)]
    for i in range(M):
        h,w=mi()
        H_count[h] += 1
        W_count[w] += 1
        G[h][w] = True
    
    ans = 0
    for h in range(1,H+1):
        for w in range(1,W+1):
            res = H_count[h] + W_count[w]
            if G[h][w]:
                res -= 1
            ans = max(res,ans)
            # print((h,w),res)


    print(ans)




if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    H,W,M=mi()

    H_count = [0] * (H+1)
    W_count = [0] * (W+1)
    G = set()
    seenH = set()
    seenW = set()
    for i in range(M):
        h,w=mi()
        H_count[h] += 1
        W_count[w] += 1

        seenH.add(h)
        seenW.add(w)
        G.add((h,w))
    
    Hs = []
    Ws = []
    for i in range(max(H,W)+1):
        if i < len(H_count):
            count = H_count[i]
            if count > 0:
                Hs.append((count,i))

        if i < len(W_count):
            count = W_count[i]
            if count > 0:
                Ws.append((count,i))


    Hs.sort(reverse=True)
    Ws.sort(reverse=True)

    # print(Hs)
    # print(Ws)

    h_count,h = Hs[0]
    w_count,w = Ws[0]

    original = h_count + w_count
    ans = original
    if (h,w) in G:
        # print("a")
        ans -= 1

        i = 1
        sameH = []
        while i < len(Hs) and Hs[i][0] == h_count:
            # print("h")
            h = Hs[i][1]
            i += 1
            sameH.append(h)
        
        i = 1
        sameW = []    
        while i < len(Ws) and Ws[i][0] == w_count:
            w = Ws[i][1]
            i += 1
            sameW.append(w)
           
        max_mass = (len(sameH)+1) * (len(sameW)+1)

        # print(max_mass)
        on_bom_count = 0
        for h,w in G:
            count = H_count[h] + W_count[w]
            if count == original:
                on_bom_count += 1
        
        if max_mass - on_bom_count > 0:
            ans += 1

                
    print(ans)


        
    



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

s = input()
num = len(s)
l = []
from collections import deque
l = deque(l)   # deque オブジェクトを取得

for _ in range(1, 20190000):
    if _%2019 == 0 and '0' not in str(_) :
        l.append(str(_))
l = set(l)
#print(l)

def aaa(s, num):
    x = 0
    for i in range(4,num+1):
        for j in range(num - i + 1):
            if s[j:j+i] in l:
                x += 1
    print(x)

aaa(s, num)

### FIXED CODE ###

s = input()[::-1]

cnts = [1] + [0] * (2019 - 1)
tmp = 0
d = 1

for i in s:
    tmp += int(i) * d
    cnts[tmp % 2019] += 1
    d = d * 10 % 2019 # 桁数が大きくなりすぎる → 10と2019が素だから可能

ans = 0
for cnt in cnts:
    ans += (cnt - 1) * cnt // 2

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

#関数リスト
import sys
from bisect import bisect
input = sys.stdin.readline
def RD(): return input().rstrip()
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]

def main():
    N = I()
    A = LI()
    A.sort()
    B = LI()
    B.sort()
    B_len = len(B)
    C = LI()
    C.sort()
    C_len = len(C)
    result = 0
    A_init = A[0]
    for i in A:
        index = bisect(B,i)
        if index == B_len:
            break
        for j in range(index, B_len):
            index2 = bisect(C,B[j])
            if index2 == C_len:
                break
            result += C_len - index2
    print(result)

if __name__ == "__main__":
    main()


### FIXED CODE ###

#関数リスト
import sys
import bisect
input = sys.stdin.readline
def RD(): return input().rstrip()
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]

def main():
    N = I()
    A = LI()
    A.sort()
    B = LI()
    B.sort()
    B_len = len(B)
    C = LI()
    C.sort()
    C_len = len(C)
    result = 0
    A_init = A[0]
    index = 0
    next_i = index
    
    for i in B:
        tempA = bisect.bisect_left(A,i) 
        tempC = C_len - bisect.bisect_right(C,i)
        result += tempA*tempC
    print(result)

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

import numpy as np
import bisect
n = int(input())
aa = np.array(list(map(int, input().split())))
bb = list(map(int, input().split()))
cc = np.array(list(map(int, input().split())))

aa.sort()
cc.sort()

cnt = 0
for b in bb:
    na = bisect.bisect_left(aa,b)
    nc = n - bisect.bisect_right(cc,b)
    cnt += na*nc
print(cnt)

### FIXED CODE ###

import numpy as np
import bisect
n = int(input())
aa = list(map(int, input().split()))
bb = list(map(int, input().split()))
cc = list(map(int, input().split()))

aa.sort()
cc.sort()

cnt = 0
for b in bb:
    na = bisect.bisect_left(aa,b)
    nc = n - bisect.bisect_right(cc,b)
    cnt += na*nc
print(cnt)
### BUGGY CODE ###

n,k =map(int,input().split())
p = list(map(int,input().split()))
kitai = []
for i in range(1,n+1):
    sum_k = 0
    for j in range(1,p[i-1]+1):
        sum_k += j *(1/p[i-1])
    kitai.append(sum_k)
ans = []
sum_ans = 0
for i in range(k):
    sum_ans += kitai[i]
ans.append(sum_ans)
j = 0
cnt = 0
for i in range(k,len(kitai)):
    sum_ans = ans[cnt]
    d = kitai[i] - kitai[j]
    sum_ans += d
    j +=1
    cnt+=1
    ans.append(sum_ans)
ans = sorted(ans)
print(ans[-1])


### FIXED CODE ###

n,k =map(int,input().split())
p = list(map(int,input().split()))
kitai = []
for i in range(n):
    sum_k = 0
    sum_k = (1 + p[i])/2
    kitai.append(sum_k)
ans = []
sum_ans = 0
for i in range(k):
    sum_ans += kitai[i]
ans.append(sum_ans)
j = 0
cnt = 0
for i in range(k,len(kitai)):
    sum_ans = ans[cnt]
    sum_ans -=kitai[j] 
    sum_ans += kitai[i]
    j +=1
    cnt+=1
    ans.append(sum_ans)
print(max(ans))
### BUGGY CODE ###

def main():
    N, W = map(int, input().split())
    dp = [0] * (W + 1)

    WV = [map(int, input().split()) for _ in range(N)]

    for w, v in WV:
        for j in range(W, w - 1, -1):
            dp[j] = max(dp[j], dp[j - w] + v)

    print(dp[-1])


main()


### FIXED CODE ###

import sys


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

    N, W = map(int, input().split())
    dp = [0] * (W + 1)

    WV = (map(int, input().split()) for _ in range(N))

    for w, v in WV:
        for j in range(W, w - 1, -1):
            tmp = dp[j - w] + v
            if tmp > dp[j]:
                dp[j] = tmp

    print(dp[-1])


main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Mon Jun  1 16:47:45 2020

@author: NEC-PCuser
"""

N = int(input())
S = input()
count = 0
for i in range(0, 1000):
    j = 0
    a = str(i).zfill(3)
    for k in range(0, len(S)):
        if (a[j] == S[k]):
            j += 1
        if (j == 3):
            count += 1
            break
            
print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Mon Jun  1 16:47:45 2020

@author: NEC-PCuser
"""

N = int(input())
S = input()
count = 0
for i in range(0, 1000):
    j = 0
    a = str(i).zfill(3)
    b = S.find(a[0])
    if b == -1:
        continue
    c = S[b+1:].find(a[1])
    if c == -1:
        continue
    d= S[b+c+2:].find(a[2])
    if d != -1:
        count += 1
    
            
print(count)