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

S = str(input())

def solution(S):
    count = 0
    for j in range(4, len(S)+1):
        for i in range(len(S)-j+1):
            if int(S[i:i+j])%2019==0:
                count += 1
    print(count)
solution(S)


### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

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

print(ans) # 答えの出力
### BUGGY CODE ###

H,W,D=map(int,input().split())
position=[None]*(H*W+1)
for i in range(H):
  A=list(map(int,input().split()))
  for j in range(len(A)):
    position[A[j]]=[i,j]

dp=[0]*(H*W+1)

for i in range(1,len(dp)):
  if i+D>=len(dp):
    continue
  dp[i]=abs(position[i+D][0]-position[i][0])+abs(position[i+D][1]-position[i][1])

dpsum=[[0 for i in range(H*W+1)] for j in range(D)]

for i in range(1,len(dp)):
  if i-D>=0:
    dpsum[i%D][i]=dpsum[i%D][i-D]+dp[i]
  else:
    dpsum[i%D][i]=dp[i]

Q=int(input())
for i in range(Q):
  L,R=map(int,input().split())
  if L==R:
    print(0)
  elif L-D>0:
    print(dpsum[R%D][R-D]-dpsum[L%D][L-D])
  else:
    print(dpsum[R%D][R-D])


### FIXED CODE ###

H,W,D=map(int,input().split())
position=[None]*(H*W+1)
for i in range(H):
  A=list(map(int,input().split()))
  for j in range(len(A)):
    position[A[j]]=[i,j]

dp=[0]*(H*W+1)

for i in range(1,len(dp)):
  if i+D>=len(dp):
    continue
  dp[i]=abs(position[i+D][0]-position[i][0])+abs(position[i+D][1]-position[i][1])

dpsum=[0]*(H*W+1)

for i in range(1,len(dp)):
  if i-D>=0:
    dpsum[i]=dpsum[i-D]+dp[i]
  else:
    dpsum[i]=dp[i]

Q=int(input())
for i in range(Q):
  L,R=map(int,input().split())
  if L==R:
    print(0)
  elif L-D>0:
    print(dpsum[R-D]-dpsum[L-D])
  else:
    print(dpsum[R-D])
### BUGGY CODE ###

n=int(input())
lr=[[int(i) for i in input().split()] for j in range(n)]
lr=sorted(lr)
li_test=[]

for x,y in lr:
    li_test.append(y)

li=[li_test[0]]
for i in range(1,n):
    a=min(li_test[:i+1])
    li.append(a)

li_test=li_test[::-1]
li2=[li_test[0]]
for i in range(1,n):
    a=min(li_test[:i+1])
    li2.append(a)
li2=li2[::-1]
    
ans=0
maxi=lr[-1][0]
for i in range(n-1):
    one = max(0,li[i]-lr[i][0]+1)
    two = max(0,li2[i+1]-maxi+1)
    ans=max(ans,one+two)
print(ans)
    
    

### FIXED CODE ###

n=int(input())
lr=[[int(i) for i in input().split()] for j in range(n)]
lr=sorted(lr)
li_test=[]

for x,y in lr:
    li_test.append(y)

li=[li_test[0]]
a=li_test[0]
for i in range(1,n):
    a=min(li_test[i],a)
    li.append(a)

li_test=li_test[::-1]
li2=[li_test[0]]
a=li_test[0]
for i in range(1,n):
    a=min(li_test[i],a)
    li2.append(a)
li2=li2[::-1]
    
ans=0


maxi=lr[-1][0]
for i in range(n-1):
    one = max(0,li[i]-lr[i][0]+1)
    two = max(0,li2[i+1]-maxi+1)
    tokubetu=lr[i][1]-lr[i][0]+1
    tokubetu2=max(0,li2[0]-maxi+1)
    check=max(one+two,tokubetu+tokubetu2)
    ans=max(ans,check)
print(ans)
### BUGGY CODE ###

import math
import fractions
import copy
#以下てんぷら
def j(q):
    if q==1: print("YES")
    elif q == 0:print("NO")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def printrow(a):
    for i in range(len(a)):
        print(a[i])
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


#n = ip()                                     #入力整数1つ
n,k= (int(i) for i in input().split())       #入力整数横2つ以上
a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#a=[input() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#全足しに4 3sum変数使用はsum関数使用できないので注意
s = [0 for i in range(200001)]
for i in range(n):
    s[a[i]]+=1
#print(s[:max(a)+1])
st = []
for i in range(max(a)+1):
    if s[i]:st.append(s[i])
st.sort()
#print(st)
total = 0
while len(st)>k:
    total+=st.pop(0)
print(total)

### FIXED CODE ###

import math
import fractions
import copy
#以下てんぷら
def j(q):
    if q==1: print("YES")
    elif q == 0:print("NO")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def printrow(a):
    for i in range(len(a)):
        print(a[i])
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


#n = ip()                                     #入力整数1つ
n,k= (int(i) for i in input().split())       #入力整数横2つ以上
a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#a=[input() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#全足しに4 3sum変数使用はsum関数使用できないので注意
a.sort()
cnum = a[0]
ct =1
st = []
for i in range(1,n):
    if a[i] != cnum:
        cnum = a[i]
        st.append(ct)
        ct = 1
    else:ct+=1
st.append(ct)
st.sort(reverse=True)
total = 0
for i in range(min(k,len(st))):
    total+=st[i]
print(n-total)
### BUGGY CODE ###

N = int(input())
dic = {}
for i in range(N):
  a = [int(i) for i in input().split()]
  dic[i+1] = a[::-1]
count = 0
while True:
  nokori = 0
  flag = True
  log = [-1]*N
  for k in dic.keys():
    k = int(k)
    if dic[k]==[]:
      nokori += 1
      continue
    p2 = dic[k][-1]
#    print(k,p2)
    if log[p2-1]==1:
      continue
    if dic[p2]==[]:
      print(-1)
      break
    if dic[p2][-1]==k and log[k-1]==-1 and log[p2-1]==-1:
      a = dic[k].pop()
      b = dic[p2].pop()
#      print('%', a,b)
      log[k-1] = 1
      log[p2-1] = 1
      flag = False
      
  if nokori == N:
    print(count)
    break
  count += 1
  if flag:
    print(-1)
    break

### FIXED CODE ###

N = int(input())
es = [[] for i in range(N)]
cand = set()
for i in range(N):
  es[i] = [int(i)-1 for i in input().split()][::-1]
def check(i):
  if es[i]==[]:
    return
  j = es[i][-1]
  if es[j]==[]:
    return
  if es[j][-1]==i:
    cand.add(i)
    cand.add(j)

for i in range(N):
  check(i)
day = 0
while cand:
  day += 1
  precand = cand.copy()
  cand = set()
  for i in precand:
    x = es[i].pop()
  for i in precand:
    check(i)
for i in range(N):
  if len(es[i])!=0:
    print(-1)
    break
else:
  print(day)
### BUGGY CODE ###

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

ans = 0
for p in range(1000):
  s = '{:03}'.format(p)
  i = 0
  for j in range(N):
    if i < 3 and S[j] == s[i]:
      i += 1
  if i == 3:
    ans += 1
print(ans)


### FIXED CODE ###

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

ans = 0
for p in range(1000):
  s = '{:03}'.format(p)
  i = 0
  for j in range(N):
    if i < 3 and S[j] == s[i]:
      i += 1
  if i == 3:
    ans += 1
print(ans)
### BUGGY CODE ###

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

ans = [str(a.index(x)+1) for x in range(1, n+1)]

print(" ".join(ans))

### FIXED CODE ###

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

l = [[] for x in range(n)]
for i, num in enumerate(a):
    l[num-1] = (int(i) + 1)

print(*l)
### BUGGY CODE ###

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

rem = 0
d = [0]

for i in range(N):
    if not(a[i] in d):
        d.append(a[i])
        if a.count(a[i]) < a[i]:
            rem += a.count(a[i])
        elif a.count(a[i]) > a[i]:
            rem += a.count(a[i])-a[i]
print(rem)

### FIXED CODE ###

from collections import Counter

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

C = Counter(a)
ans = 0

for i in C:
    if C[i] > i:
        ans += C[i]-i
    elif C[i] < i:
        ans += C[i]

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

def main():
	N, M = map(int, input().split())
	A = []
	B = []
	for i in range(N):
		a, b = map(int, input().split())
		A.append(a)
		B.append(b)
	cost = 0
	while True:
		mc = 0
		minp = min(A)
		for i in range(N):
			if A[i] == minp:
				mc = B[i]
				A[i] = 10**10
				break
		if M <= mc:
			for i in range(mc):
				M -= 1
				cost += minp
				if M <= 0:
					print(cost)
					return
		else:
			M -= mc
			cost += minp * mc
	return

if __name__ == '__main__':
	main()


### FIXED CODE ###

def main():
	N, M = map(int, input().split())
	S = []
	for i in range(N):
		a, b = map(int, input().split())
		S.append([a, b])
	sorted_shop_list = sorted(S, key=lambda x: x[0])
	cost = 0
	for i in sorted_shop_list:
		a = i[0]
		b = i[1]
		if b < M:
			M -= b
			cost += a * b
		else:
			cost += a * M
			break
	print(cost)
	return

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

import numpy as np

MOD = 10 ** 9 + 7

H, W = map(int, input().split())
count = np.ones(W, dtype=np.int)

row = input()
for w in range(1, W):
  if row[w] == '#':
    count[w:] = 0
    break

for h in range(1, H):
  row = input()
  if row[0] == '#':
    count[0] = 0
  for w in range(1, W):
    if row[w] == '#':
      count[w] = 0
    else:
      count[w] = (count[w-1] + count[w]) % MOD
print(count[-1])

### FIXED CODE ###

MOD = 10 ** 9 + 7

H, W = map(int, input().split())
count = [0] * W

row = input()
for w in range(W):
  if row[w] == '#':
    break
  else:
    count[w] = 1

for h in range(1, H):
  row = input()
  if row[0] == '#':
    count[0] = 0
  for w in range(1, W):
    if row[w] == '#':
      count[w] = 0
    else:
      count[w] = (count[w-1] + count[w]) % MOD
print(count[-1])
### BUGGY CODE ###

def main():
    n = [int(i) for i in input().split()]
    bridge = []
    counter = 0
    reqs = [[int(j) for j in input().split()] for i in range(n[1])]
    reqs.sort(key=lambda x:(x[0],x[1]))
    
    for i in range(1, n[0]+1):
        if i in bridge:
            bridge = []
            counter += 1
        for j in range(len(reqs)):
            if reqs[j][0] == i:
                bridge.append(reqs[j][1])
            else:
                reqs = reqs[j:]
                break
    
    print(counter)

main()

### FIXED CODE ###

def main():
    n = [int(i) for i in input().split()]
    bridge = set()
    counter = 0
    reqs = [[int(j) for j in input().split()] for i in range(n[1])]
    reqs.sort(key=lambda x:(x[0],x[1]))
    
    preset = 0
    for i in range(1, n[0]+1):
        if i in bridge:
            bridge.clear()
            counter += 1
        for j in range(preset, len(reqs)):
            if reqs[j][0] == i:
                bridge.add(reqs[j][1])
            else:
                preset = j
                break
    
    print(counter)

main()
### BUGGY CODE ###

import bisect
n,m=map(int,input().split())
A=sorted(list(map(int,input().split())))
for i in range(m):
    b=A.pop(n-1)//2
    bisect.insort_left(A, b)
print(sum(A))

### FIXED CODE ###

import heapq
n,m=map(int,input().split())
A=list(map(int,input().split()))
H=[]
for a in A:
    heapq.heappush(H,-a)
for i in range(m):
    heapq.heappush(H,-(-heapq.heappop(H)//2))
print(-sum(H))
### BUGGY CODE ###

N=int(input())
A=list(map(int, input().split()))
A_=list(set(A))
count_=["0\n"]*N

for i in range(len(A_)):
	count_[A_[i]-1]=str(A.count(A_[i]))+"\n"

print("".join(count_))



### FIXED CODE ###

N = int(input())
K = [0]*N
A = [int(i) for i in input().split()]

for i in range(N-1):
    K[A[i]-1] += 1
for i in K:
    print(i)
### BUGGY CODE ###

import copy
N, M, K = map(int, input().split())

class UnionFind():
    def __init__(self, n):
        self.n = 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[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
      
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

uf = UnionFind(N+1)

not_uf = [set() for _ in range(N+1)]
for _ in range(M):
  a, b = map(int, input().split())
  not_uf[a].add(b)
  not_uf[b].add(a)
  uf.union(a, b)

for _ in range(K):
  c, d = map(int, input().split())
  if d in uf.members(c):
    not_uf[c].add(d)
    not_uf[d].add(c)

for i in range(1, N+1):
  print(uf.size(i)-len(not_uf[i])-1)
  

### FIXED CODE ###

import copy
N, M, K = map(int, input().split())

class UnionFind():
    def __init__(self, n):
        self.n = 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[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
      
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

uf = UnionFind(N+1)

not_uf = [set() for _ in range(N+1)]
for _ in range(M):
  a, b = map(int, input().split())
  not_uf[a].add(b)
  not_uf[b].add(a)
  uf.union(a, b)

for _ in range(K):
  c, d = map(int, input().split())
  if uf.same(c, d):
    not_uf[c].add(d)
    not_uf[d].add(c)

for i in range(1, N+1):
  print(uf.size(i)-len(not_uf[i])-1)
### BUGGY CODE ###

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

ans = "Yes"

for i in range(1, N-1):

    if H[i] > H[i+1] and max(H[0: i]) - 1 > min(H[i: N]):
        ans = "No"
        break
print(ans)

### FIXED CODE ###

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

flag = True

for i in range(N-1, 0, -1):
    if H[i-1] - 1 == H[i]:
        H[i-1] -= 1
    elif H[i-1] - 1 > H[i]:
        flag = False
        break

if flag:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline


def main():
    n = int(input())
    l = list(map(int, input().split()))
    l = sorted(l)

    result = 0
    # print(l)
    for i in range(n-2):
        for j in range(i + 1, n - 1):
            target = l[j + 1:]
            count = sum(1 for x in target if x < (l[i] + l[j]))
            # count = np.count_nonzero(target < (l[i] + l[j]))
            # print(l[i], l[j], target, count)
            result += count

    print(result)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import bisect
import sys
input = sys.stdin.readline


def main():
    n = int(input())
    l = list(map(int, input().split()))
    l.sort()

    result = 0
    for i in range(n-2):
        for j in range(i + 1, n - 1):
            result += bisect.bisect_left(l, l[i] + l[j]) - (j + 1)

    print(result)


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

from collections import deque

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

results = deque()
while len(A) > 0:
    if not (len(A) > 1 and A[0] == A[1]):
        results.append(A[0])
    A = [a for a in A if a % A[0] != 0]

print(len(results))


### FIXED CODE ###

from collections import Counter
import numpy as np

A_MAX = 10 ** 6 + 1

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

dp = np.zeros(shape=A_MAX, dtype=np.int64)

if A[1] == 1:
    print(1)
elif A[1] > 1:
    print(0)
else:
    for a in A.keys():
        multiples = np.arange(a, A_MAX, a)
        np.add.at(dp, multiples, 1)

    ans = 0
    for a, count in A.items():
        if count > 1:
            continue
        if dp[a] == 1:
            ans += 1

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

n=int(input())
h=[int(i) for i in input().split()]
j=0
ans=0
while True:
  if h[0]>j:
    ans+=1
  for i in range(1,n):
    if h[i-1]<=j and h [i]>j:
      ans+=1
  j+=1
  if j==max(h):
    break
print(ans) 

### FIXED CODE ###

n=int(input())
h=[int(i) for i in input().split()]
j=0
ans=0
while j<max(h):
  if h[0]>j:
    ans+=1
  for i in range(1,n):
    if h[i-1]<=j and h [i]>j:
      ans+=1
  j+=1
print(ans)
### BUGGY CODE ###

H, W = map(int, input().split())
S = [input() for _ in range(H)]
ans = 0
for i in range(H):
	for j in range(W):
		if S[i][j] == ".":
			n, e, s, w = 0, 0, 0, 0
			while i - n >= 0 and S[i - n][j] == ".":
				n += 1
			while i + s <= H - 1 and S[i + s][j] == ".":
				s += 1
			while j + e <= W - 1 and S[i][j + e] == ".":
				e += 1
			while j - w >= 0 and S[i][j - w] == ".":
				w += 1
			ans = max(ans, n + s + e + w - 3)
print(ans)


### FIXED CODE ###

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

L = [[0] * W for _ in range(H)]
R = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]
U = [[0] * W for _ in range(H)]

for i in range(H):
	for j in range(W):
		if S[i][j] == ".":
			if j == 0:
				L[i][j] = 1
			else:
				L[i][j] = L[i][j - 1] + 1

# print(L)

for i in range(H):
	for j in range(W - 1, -1, -1):
		if S[i][j] == ".":
			if j == W - 1:
				R[i][j] = 1
			else:
				R[i][j] = R[i][j + 1] + 1

# print(R)

for j in range(W):
	for i in range(H - 1, -1, -1):
		if S[i][j] == ".":
			if i == H - 1:
				D[i][j] = 1
			else:
				D[i][j] = D[i + 1][j] + 1

# print(D)

for j in range(W):
	for i in range(H):
		if S[i][j] == ".":
			if i == 0:
				U[i][j] = 1
			else:
				U[i][j] = U[i - 1][j] + 1

# print(U)


ans = 0
X = [[0] * W for _ in range(H)]
for i in range(H):
	for j in range(W):
		X[i][j] = L[i][j] + R[i][j] + D[i][j] + U[i][j] - 3
	ans = max(ans, max(X[i]))

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

n,k=map(int,input().split())
arr=list(map(int,input().split()))
ans=1
for i in range(n):
    if i<k:
        ans*=arr[i]
    else:
        c=ans
        ans=(ans*arr[i])//arr[i-k]
        if ans>c:
            print("Yes")
        else:
            print("No")




### FIXED CODE ###

n,k=map(int,input().split())
arr=list(map(int,input().split()))
for i in range(n):
    if i>=k:
        if arr[i-k]<arr[i]:
            print("Yes")
        else:
            print("No")
### BUGGY CODE ###

def solve():
    n, q = map(int, input().split())
    s = list(map(int, input().split()))
    cnt = []
    rcnt = []
    for i in range(1, n + 1):
        x = len(set(s[:i]))
        cnt.append(x)
    for i in range(n - 1, -1, -1):
        x = len(set(s[i:]))
        rcnt.append(x)
    rcnt = rcnt[::-1]
    for _ in range(q):
        l, r = map(int, input().split())
        if r == l:
            print(1)
            continue
        l, r = l - 1, r - 1
        y = cnt[l - 1] if l >= 1 else 0
        z = rcnt[r] if r < n - 1 else 0
        print(min(r - l + 1, max(cnt[r] - y, rcnt[l - 1] - z)))

solve()


### FIXED CODE ###

def solve():
    import sys
    input = sys.stdin.readline

    class BIT:
        def __init__(self, n):
            self.n = n
            self.data = [0] * n

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.data[i - 1]
                i &= i - 1
            return s

        def update(self, i, x):
            while i < self.n:
                self.data[i] += x
                i |= i + 1

    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    odr_r = [[] for _ in range(n + 1)]
    for i in range(q):
        l, r = map(int, input().split())
        odr_r[r].append((l - 1, i))

    b = BIT(n)
    diff = 0
    ans = [-1] * q
    last = [-1] * (n + 1)

    for i, v in enumerate(c):
        if last[v] != -1:
            b.update(last[v], -1)
        else:
            diff += 1

        b.update(i, 1)
        last[v] = i

        for l, j in odr_r[i + 1]:
            ans[j] = diff - b.sum(l)
    print("\n".join(map(str, ans)))
    return


solve()
### BUGGY CODE ###

def main():  
  import sys
  read = sys.stdin.buffer.read
  readline = sys.stdin.buffer.readline
  readlines = sys.stdin.buffer.readlines
  import numpy as np #pypy不可
  n,k = map(int,readline().split())
  p =  np.array(read().split(),np.int32)
  if n%k == 0:
    r = k
    L = n
  else:
    r = n%k+1
    L = n+k-n%k
  chk = 0
  for _ in range(r):
    p.resize(L) # np.resize(p,L) にすると足りない分を繰り返す
    l = p.reshape(-1,k).sum(axis=1)
    #print(p.reshape(-1,k))
    m = max(l)
    chk = max(chk,m)
    p = np.delete(p,0)

  print((chk+k)/2)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():  
  import sys
  read = sys.stdin.buffer.read
  readline = sys.stdin.buffer.readline
  readlines = sys.stdin.buffer.readlines
  import numpy as np #pypy不可
  n,k = map(int,readline().split())
  p =  np.array(read().split(),np.int32)
  np.cumsum(p,out=p)
  chk = p[k-1]
  for i in range(n-k):
    c = p[i+k]-p[i]
    chk = max(c,chk)
  print((chk+k)/2)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
X, Y = [], []
for i in range(N):
    X.append(i + 1 + A[i])
    Y.append(i + 1 - A[i])
X.sort()
Y.sort()
y = 0
c = 0
for i in range(N):
    if X[i] > Y[-1]:
        break
    for j in range(y, N):
        if X[i] == Y[j]:
            c += 1
            y = Y[j]
        if X[i] < Y[j]:
            break
print(c)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
X, Y = [], []
for i in range(N):
    X.append(i + 1 + A[i])
    Y.append(i + 1 - A[i])
XL = Counter(X)
c = 0
for y in Y:
    c += XL.get(y, 0)
print(c)
### BUGGY CODE ###

root=[]
n,k = map(int,input().split())
for i in range(k):
    x,y = map(int,input().split())
    root.append([x,y])

toori=[0]*(2*10**5)+[0]*n+[0]*(2*10**5)
toori[2*10**5]=1
cum=[0]*k
for a,i in enumerate (root):
    s=0
    for j in range (i[0],i[1]+1):
        s+=toori[2*10**5+1-j]
    cum[a]=s
toori[2*10**5+1]+=sum(cum)


for now in range(2,n):#nowが今の場所
    for a,i in enumerate (root):
        cum[a]=cum[a]+toori[2*10**5+now-i[0]] - toori[2*10**5+now-1-i[1]]
    toori[2*10**5+now]+=sum(cum)
    


print(toori[2*10**5+n-1]%998244353)

### FIXED CODE ###

root=[]
n,k = map(int,input().split())
for i in range(k):
    x,y = map(int,input().split())
    root.append([x,y])

toori=[0]*(2*10**5)+[0]*n+[0]*(2*10**5)
toori[2*10**5]=1
cum=[0]*k
for a,i in enumerate (root):
    s=0
    for j in range (i[0],i[1]+1):
        s+=toori[2*10**5+1-j]
    cum[a]=s
aaa=sum(cum)%998244353
toori[2*10**5+1]+=aaa


for now in range(2,n):#nowが今の場所
    hueru=0
    for a,i in enumerate (root):
        hueru+=(toori[2*10**5+now-i[0]] - toori[2*10**5+now-1-i[1]])
    aaa+=hueru
    aaa%=998244353
    toori[2*10**5+now]+=aaa
    toori[2*10**5+now]%=998244353
    


print(toori[2*10**5+n-1]%998244353)