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

n,m = list(map(int,input().split()))
h = list(map(int,input().split()))
a_list = []
b_list = []
good_list = list(range(1,n+1))
for i in range(m):
    a,b = list(map(int,input().split()))
    a_list.append(a)
    b_list.append(b)
    if a in good_list:
        if h[a-1] < h[b-1] or h[a-1] == h[b-1]:
            good_list.remove(a)
    if b in good_list:
        if h[a-1] > h[b-1] or h[a-1] == h[b-1]:
            good_list.remove(b)
print(len(good_list))

### FIXED CODE ###

n,m = list(map(int,input().split()))
h = list(map(int,input().split()))

not_good = []
for i in range(m):
    a,b = list(map(int,input().split()))
    if h[a-1] <= h[b-1]:
        not_good.append(a)
    if h[a-1] >= h[b-1]:
        not_good.append(b)
print(n-len(set(not_good)))
### BUGGY CODE ###

import itertools

n, m, q = map(int, input().split())
abcd = [0] * q
for i in range(q):
    a, b, c, d = map(int, input().split())
    abcd[i] = [a, b, c, d]

lis = []
for i in range(m):
    for j in range(n):
        lis.append(i+1)
pat = list(itertools.combinations(lis, n))

ans = 0
for l in pat:
    cnt = 0
    for i in range(q):
        if l[abcd[i][1]-1] - l[abcd[i][0]-1] == abcd[i][2]:
            cnt += abcd[i][3]
    ans = max(ans, cnt)
print(ans)

### FIXED CODE ###

import itertools

n, m, q = map(int, input().split())
abcd = [0] * q
for i in range(q):
    a, b, c, d = map(int, input().split())
    abcd[i] = [a, b, c, d]

pat = list(itertools.combinations_with_replacement(range(1, m+1), n))

ans = 0
for l in pat:
    cnt = 0
    for i in range(q):
        if l[abcd[i][1]-1] - l[abcd[i][0]-1] == abcd[i][2]:
            cnt += abcd[i][3]
    ans = max(ans, cnt)
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp= [0]*n

for i in range(1,n):  
  dp[i] =min([dp[i-j] + abs(h[i] - h[i-j]) \
              for j in range(1,min(i+1,k+1))])       
print(dp[-1])  

### FIXED CODE ###

# TLE
n,k = map(int,input().split())
h = list(map(int,input().split()))
dp= [0]*n

for i in range(1,n):
  tmp = float('inf')
  for j in range(1,min(i+1,k+1)):    
    d = dp[i-j] + abs(h[i] - h[i-j])    
    tmp = min(tmp,d)  
  dp[i] = tmp
  
print(dp[-1])
### BUGGY CODE ###

def main():
    H, W, M = (int(i) for i in input().split())
    hc = [0]*(H+1)
    wc = [0]*(W+1)
    maps = set()
    for _ in range(M):
        h, w = (int(i) for i in input().split())
        hc[h] += 1
        wc[w] += 1
        maps.add((h, w))
    mah = -1
    maw = -1
    hmaps = set()
    wmaps = set()
    for i, h in enumerate(hc):
        if mah < h:
            mah = h
            hmaps = {i}
        elif mah == h:
            hmaps.add(i)
    for i, w in enumerate(wc):
        if maw < w:
            maw = w
            wmaps = {i}
        elif maw == w:
            wmaps.add(i)
    ans = mah+maw
    aru = True

    for h in list(hmaps):
        for w in list(wmaps):
            if (h, w) not in maps:
                aru = False
                break
    if aru:
        print(ans - 1)
    else:
        print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    H, W, M = (int(i) for i in input().split())
    hc = [0]*(H+1)
    wc = [0]*(W+1)
    maps = set()
    for _ in range(M):
        h, w = (int(i) for i in input().split())
        hc[h] += 1
        wc[w] += 1
        maps.add((h, w))
    mah = -1
    maw = -1
    hmaps = set()
    wmaps = set()
    for i, h in enumerate(hc):
        if mah < h:
            mah = h
            hmaps = {i}
        elif mah == h:
            hmaps.add(i)
    for i, w in enumerate(wc):
        if maw < w:
            maw = w
            wmaps = {i}
        elif maw == w:
            wmaps.add(i)
    ans = mah+maw
    aru = True
    if len(hmaps) * len(wmaps) <= 5*10**6:
        for h in list(hmaps):
            for w in list(wmaps):
                if (h, w) not in maps:
                    aru = False
                    break
    else:
        aru = False
    if aru:
        print(ans - 1)
    else:
        print(ans)


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

import sys
input = sys.stdin.buffer.readline
import bisect

def main():
    N,K = map(int,input().split())
    a = list(map(int,input().split()))
    a.sort()

    def check(x):
        count = 0
        if x > 0:
            for i in range(N):
                if a[i] < 0:
                    num = -(-x//a[i])
                    count += N-max(i+1,bisect.bisect_left(a,num))
                elif a[i] > 0:
                    num = x//a[i]
                    count += max(0,bisect.bisect_right(a,num)-i-1)
                else:
                    count += N-(i+1)
        elif x == 0:
            for i in range(N):
                if a[i] < 0:
                    num = 0
                    count += N-max(i+1,bisect.bisect_left(a,num))
                elif a[i] > 0:
                    continue
                else:
                    count += N-(i+1)
        else:
            for i in range(N):
                if a[i] < 0:
                    num = -(-x//a[i])
                    count += N-bisect.bisect_left(a,num)
                else:
                    continue
        return count
    
    left,right = -10**18-1,10**18+1
    while right-left > 1:
        mid = (left+right)//2
        if check(mid) >= K:
            right = mid
        else:
            left = mid
            
    print(right)
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
import numpy as np

def main():
    N,K = map(int,input().split())
    a = np.array(list(map(int,input().split())))
    a.sort()
    posi,zero,nega = a[a>0],a[a==0],a[a<0]
    lz = len(zero)
    
    def ch(x):
        count = 0
        if x >= 0:
            count += lz*N
        count += np.searchsorted(a,x//posi,side="right").sum()
        count += (N-np.searchsorted(a,-(-x//nega))).sum()
        count -= np.count_nonzero(a**2<=x)
        return count//2

    l,r = -10**18-1,10**18
    while r-l > 1:
        mid = (r+l)//2
        if ch(mid) >= K:
            r = mid
        else:
            l = mid

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

from collections import deque
N,M,L = map(int, input().split())
INF = float("inf")
# 初期化
d = [[INF]*N for i in range(N)]
for i in range(N):
    d[i][i] = 0
for i in range(M):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1   
    # 多重辺の場合はMIN
    d[a][b] = c
    d[b][a] = c
# 最適化(わーしゃゆふよいど)
for k in range(N):
    for i in range(N):
        for j in range(N):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

# 初期化2
d2 = [[INF]*N for i in range(N)]
for i in range(N):
    d2[i][i] = 0
for i in range(N):
    for j in range(N):
        # 給油できるところに辺を張る
        if d[i][j] <= L:
            d2[i][j] = 1
for k in range(N):
    for i in range(N):
        for j in range(N):
            d2[i][j] = min(d2[i][j], d2[i][k] + d2[k][j])

#query
Q = int(input())
for i in range(Q):
    s,t  = map(int, input().split())
    s -= 1
    t -= 1
    ans = d2[s][t]-1
    if ans == INF:
        ans = -1
    print(ans)

### FIXED CODE ###

N,M,L = map(int, input().split())
INF = 10**18
# 初期化
d = [[INF]*N for i in range(N)]
for i in range(N):
    d[i][i] = 0
for i in range(M):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    # 多重辺の場合はMIN
    d[a][b] = c
    d[b][a] = c
# 最適化(わーしゃゆふよいど)
for k in range(N):
    for i in range(N):
        # 左右は対称だろう
        for j in range(i+1,N):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
            d[j][i] = d[i][j]

# 初期化2
d2 = [[INF]*N for i in range(N)]
for i in range(N):
    d2[i][i] = 0
for i in range(N):
    for j in range(N):
        # 給油できるところに辺を張る
        if d[i][j] <= L:
            d2[i][j] = 1
for k in range(N):
    for i in range(N):
        for j in range(i+1,N):
            d2[i][j] = min(d2[i][j], d2[i][k] + d2[k][j])
            d2[j][i] = d2[i][j]
            

#query
Q = int(input())
for i in range(Q):
    l  = list(map(int, input().split()))
    s = min(l)-1
    t = max(l)-1
    
    ans = d2[s][t]
    if ans == INF:
        ans = 0
    print(ans-1)
### BUGGY CODE ###

#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！

def main():
    n,m,*a=map(int,open(0).read().split())
    dp=[0]*(n+1)
    dp[0]=1
    mod=10**9+7
    for i in range(1,n+1):
        if i in a:
            continue
        dp[i]=dp[i-1]%mod
        if i>1:
            dp[i]+=dp[i-2]%mod
    print(dp[n]%mod)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！

def main():
    n,m,*a=map(int,open(0).read().split())
    dp=[0]*(n+1)
    a=set(a)
    dp[0]=1
    mod=10**9+7
#    dp[1]=dp[0]%mod
    for i in range(1,n+1):
        if i in a:
            continue
        else:
            dp[i]=(dp[i-1]+dp[i-2])%mod
    print(dp[n]%mod)
#    print(dp)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

maxa=0
N=int(input())
L=list(map(int,input().split()))
L=sorted(L)
R=list(set(L))
for i in range(len(R)):
  s=L.count(R[i])+L.count(R[i]+1)+L.count(R[i]-1)
  maxa=max(maxa,s)
print(maxa)

### FIXED CODE ###

maxa=0
N=int(input())
L=list(map(int,input().split()))
c=[0]*100000
for i in L:
  c[i]+=1
for i in range(1,99999):
  s=c[i]+c[i-1]+c[i+1]
  maxa=max(maxa,s)
print(maxa)
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    mod_v = 10**9 + 7
    ans = [0] * (N + 1)
    for i in range(0, N - 1):
        ai = A[0]
        aj = A[i + 1]
        ans[0] += ai * aj
    for j in range(1, N - 1):
        if A[j - 1] != 0:
            ans[j] = (ans[j - 1] - A[j - 1] * A[j]) // A[j - 1] * A[j]
        else:
            for k in range(j, N - 1):
                ai = A[k]
                aj = A[k + 1]
                ans[j] += ai * aj
    ret = 0
    for k in range(0, N):
        ret += ans[k]
    ret = ret % mod_v
    print(ret)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def calc(A, N, i):
    ans = 0
    ai = A[i]
    for i in range(i, N - 1):
        aj = A[i + 1]
        ans += ai * aj
    return (ans)


def main():
    N = int(input())
    A = list(map(int, input().split()))
    mod_v = 10**9 + 7
    ans = [0] * (N + 1)
    for i in range(0, N - 1):
        if A[i] != 0:
            ans[i] = calc(A, N, i)
            break
    for j in range(i + 1, N - 1):
        if A[j] != 0:
            ans[j] = (ans[j - 1] - A[j - 1] * A[j]) // A[j - 1] * A[j]
        else:
            ans[j] = 0
    ret = 0
    for k in range(0, N):
        ret += ans[k]
    ret = ret % mod_v
    print(ret)


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

k = int(input())
number = 7
cnt = 1
answer = -1

for i in range(k):
    if number % k == 0:
        answer = cnt
        break
    else:
        cnt += 1
        number = number + 7 * 10 ** (cnt - 1)
print(answer)


### FIXED CODE ###

k = int(input())
mod = 7 % k
cnt = 1
answer = -1

for i in range(k):
    if mod == 0:
        answer = cnt
        break
    else:
        cnt += 1
        mod = (mod * 10 + 7) % k
print(answer)
### BUGGY CODE ###

n, y = map(int, input().split())
for i in range(n + 1):
    for j in range(n + 1 - i): 
        for k in range(n + 1 - i - j):
            if 10000 * i + 5000 * j + 1000 * k == y and i + j + k == n:
                print(i, j, k)
                break
        else:
            continue
        break
    else:
        continue
    break
else:
    print(-1, -1, -1)

### FIXED CODE ###

n, y = map(int, input().split())
for i in range(n + 1):
    for j in range(n + 1 - i): 
        k = n - i - j
        if 10000 * i + 5000 * j + 1000 * k == y and i + j + k == n:
            print(i, j, k)
            break
    else:
        continue
    break
else:
    print(-1, -1, -1)
### BUGGY CODE ###

import bisect


def make_divisors(n):
    lower_divisors, upper_divisors = set(), set()
    tmp = 1
    while tmp * tmp <= n:
        if n % tmp == 0:
            lower_divisors.add(tmp)
            if tmp != n // tmp:
                upper_divisors.add(n // tmp)
        tmp += 1
    return lower_divisors | upper_divisors


n = int(input())
*A, = map(int, input().split())
A.sort()
setA = set(A)
cnt = 0
for i, a in enumerate(A):
    if bisect.bisect_right(A, a) - bisect.bisect_left(A, a) != 1:
        cnt += 1
        continue
    X = make_divisors(a)
    for x in X:
        if x != a and x in setA:
            cnt += 1
            break
print(n - cnt)


### FIXED CODE ###

n = int(input())
*A, = map(int, input().split())
maxA = max(A)
# C[a] = A内のaの個数
C = {a: 0 for a in range(1, maxA + 1)}
for a in A:
    C[a] += 1
# D[a]=1: Aにaより小さいaの約数が存在する
D = {a: 0 for a in range(1, maxA + 1)}
for a in A:
    if C[a] > 0:
        tmp = 2
        while a * tmp <= maxA:
            D[a * tmp] = 1
            tmp += 1
ans = 0
for a in A:
    if C[a] == 1 and D[a] == 0:
        ans += 1
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)
    # print(A, B)
    # 最小のコスト順に買っていけばよい
    # 同じコストのときはどうするか
    sum = 0
    count = 0
    flg = False
    for i in range(N):
        l = A.index(min(A)) # 最安値となっている要素
        for j in range(B[l]): # 買い占め
            count = count + 1
            sum = sum + A[l]
            if count == M:
                flg = True
                break
        A[l] = max(A) + 1 # 配列Aを書き換え
        if flg:
            break

    print(sum)
    # print(count)

main()

### FIXED CODE ###

def main():
    N, M = map(int, input().split())
    lis = []
    for i in range(N):
        lis.append(list(map(int, input().split())))
    # 最小のコスト順に買っていけばよい
    # 同じコストのときはどうするか
    lis.sort() # 一列目をソート，二列目を対応してくれる，同じ値のときは二列目が低い方を優先
    sum = 0
    count = 0
    flg = False
    for i in range(N):
        if (count+lis[i][1]<M) :
            sum = sum + lis[i][0]*lis[i][1]
            count = count + lis[i][1] # Bi全部
        elif (count+lis[i][1]==M):
            sum = sum + lis[i][0]*lis[i][1]
            count = count + lis[i][1] # Bi全部
            break
        else:
            for j in range(lis[i][1]):
                sum = sum + lis[i][0]
                count = count + 1
                if count==M:
                    flg = True
                    break
        if flg:
            break

    print(sum)
    # print(count)

main()
### BUGGY CODE ###

import itertools
# H, W = [int(_) for _ in input().split()]
N = int(input())

comb = itertools.combinations_with_replacement([str(i) for i in range(1, 10)], 2)
count = 0
for c in comb:
    A = c[0]
    B = c[1]
    count_1 = 0
    count_2 = 0
    for i in range(1, N+1):
        if str(i)[0] == A and str(i)[-1] == B:
            count_1 += 1
        elif str(i)[0] == B and str(i)[-1] == A:
            count_2 += 1
    if A == B:
        count += count_1 ** 2
    else:
        count += count_1 * count_2 * 2
print(count)


### FIXED CODE ###

import itertools
# H, W = [int(_) for _ in input().split()]
N = int(input())

comb = itertools.combinations_with_replacement([str(i) for i in range(1, 10)], 2)
count = 0
for c in comb:
    A = c[0]
    B = c[1]
    count_1 = 0
    count_2 = 0
    for i in range(1, N+1):
        if str(i)[0] == A and str(i)[-1] == B:
            count_1 += 1
        elif str(i)[0] == B and str(i)[-1] == A:
            count_2 += 1
    if A == B:
        count += count_1 ** 2
    else:
        count += count_1 * count_2 * 2
print(count)
### BUGGY CODE ###

from bisect import bisect, bisect_left
import sys

n = int(input())
x = list(map(int, input().split()))
l = int(input())

def search_1(start):
	return bisect(x, x[start] + l) - 1

route = [[] for _ in range(n)]

i = 0 # 親の位置
for i in range(n - 1):
	if route[i] == []:
		j = search_1(i) # カーソルの位置
		num = 1 # 何日目の場所か
		route[i].append(j)
		if route[j] == []:
			route[j] = (i, num)
		else: # 既に他の親が通っている
			route[i] += route[route[j][0]][route[j][1]:]
			continue
		while j < n - 1:
			j = search_1(j)
			num += 1
			route[i].append(j)
			if route[j] == []:
				route[j] = (i, num)
			else: # 既に他の親が通っている
				route[i] += route[route[j][0]][route[j][1]:]
				break
	else:
		continue

# print(route)

def search_2(start, goal):
	if type(route[start]) == type([]):
		return bisect_left(route[start], goal) + 1
	else:
		return bisect_left(route[route[start][0]][route[start][1]:], goal) + 1

q = int(input())
for _ in range(q):
	a, b = map(int, sys.stdin.readline().strip().split())
	if a > b:
		a, b = b, a
	print(search_2(a - 1, b - 1))

### FIXED CODE ###

from bisect import bisect

n = int(input())
x = list(map(int, input().split()))
l = int(input())
q = int(input())

#r[i][j]: jから(2**i)日で行ける右端
r = [[i for i in range(n)] for _ in range(18)]
for j in range(n):
	r[0][j] = bisect(x, x[j]+l) - 1
for i in range(1, 18):
	for j in range(n):
		r[i][j] = r[i-1][r[i-1][j]]

def search(x, y):
	res = 0
	cur = x
	while True:
		for i in range(18):
			if r[i][cur] >= y:
				if i == 0:
					return res+1
				cur = r[i-1][cur]
				res += 1 << (i-1) 
				break

for _ in range(q):
	a, b = map(int, input().split())
	print(search(min(a, b)-1, max(a, b)-1))
### BUGGY CODE ###

from collections import deque
n = int(input())
p = [int(x) for x in input().split()]

ans = 0
seat = [[min(i, j, n-i-1, n-j-1) for j in range(n)] for i in range(n)]
reserved = [[True for j in range(n)] for i in range(n)]

vec = [(-1, 0), (1, 0), (0, -1), (0, 1)]

for i in range(n**2):
    v = p[i]-1
    x, y = v//n, v % n
    reserved[x][y] = False
    ans += seat[x][y]
    q = deque([(x, y)])
    while q:
        x, y = q.popleft()
        if 0 <= x+1 < n and 0 <= y < n and seat[x+1][y] > seat[x][y] + reserved[x][y]:
            seat[x+1][y] = seat[x][y] + reserved[x][y]
            if not reserved[x][y]:
                q.appendleft((x+1, y))
            else:
                q.append((x+1, y))
        if 0 <= x-1 < n and 0 <= y < n and seat[x-1][y] > seat[x][y] + reserved[x][y]:
            seat[x-1][y] = seat[x][y] + reserved[x][y]
            if not reserved[x][y]:
                q.appendleft((x-1, y))
            else:
                q.append((x-1, y))
        if 0 <= x < n and 0 <= y+1 < n and seat[x][y+1] > seat[x][y] + reserved[x][y]:
            seat[x][y+1] = seat[x][y] + reserved[x][y]
            if not reserved[x][y]:
                q.appendleft((x, y+1))
            else:
                q.append((x, y+1))
        if 0 <= x < n and 0 <= y-1 < n and seat[x][y-1] > seat[x][y] + reserved[x][y]:
            seat[x][y-1] = seat[x][y] + reserved[x][y]
            if not reserved[x][y]:
                q.appendleft((x, y-1))
            else:
                q.append((x, y-1))


print(ans)


### FIXED CODE ###

n = int(input())
p = [int(x) for x in input().split()]

ans = 0
seat = [[min(i, j, n-i-1, n-j-1) for j in range(n)] for i in range(n)]
reserved = [[True for j in range(n)] for i in range(n)]

vec = [(-1, 0), (1, 0), (0, -1), (0, 1)]

for i in range(n**2):
    v = p[i]-1
    x, y = v//n, v % n
    reserved[x][y] = False
    ans += seat[x][y]
    q = [(x, y)]
    while q:
        x, y = q.pop()
        if 0 <= x+1 < n and 0 <= y < n and seat[x+1][y] > seat[x][y] + reserved[x][y]:
            seat[x+1][y] = seat[x][y] + reserved[x][y]
            q.append((x+1, y))
        if 0 <= x-1 < n and 0 <= y < n and seat[x-1][y] > seat[x][y] + reserved[x][y]:
            seat[x-1][y] = seat[x][y] + reserved[x][y]
            q.append((x-1, y))
        if 0 <= x < n and 0 <= y+1 < n and seat[x][y+1] > seat[x][y] + reserved[x][y]:
            seat[x][y+1] = seat[x][y] + reserved[x][y]
            q.append((x, y+1))
        if 0 <= x < n and 0 <= y-1 < n and seat[x][y-1] > seat[x][y] + reserved[x][y]:
            seat[x][y-1] = seat[x][y] + reserved[x][y]
            q.append((x, y-1))


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

def kitai(n):
  return (n+1)/2
a,b=map(int,input().split())
L=list(map(int,input().split()))
maxa=10**10*(-1)
L=list(map(kitai,L))
for i in range(a-b+1):
  maxa=max(maxa,sum(L[i:i+b]))
print(maxa)

### FIXED CODE ###

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())
def NIJIGEN(H): return [list(input()) for i in range(H)]
N,M=MAP()
L=LIST()
maxa=-(10**10)
sums=sum(L[:M])
maxa=max(maxa,sums)
for i in range(N-M):
  sums=sums-L[i]+L[i+M]
  maxa=max(maxa,sums)
print((maxa+M)/2)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
check = [0] * (10**5+1)
check[0] = A.count(0)+A.count(1)

for i in range(1, 10**5+1):
    
    check[i] = check[i-1] - A.count(i-2) + A.count(i+1)
print(max(check))

### FIXED CODE ###

import collections
N = int(input())
A = sorted(list(map(int, input().split())))
ans = 1

AA = collections.Counter(A)
cc = [0]*(max(A)+1)

for i in AA.keys():
    cc[i] = AA[i]

for i in range(len(cc)):
    ans =  max(ans, sum(cc[i:i+3]))

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

from bisect import bisect_left

N = int(input())
L = list(map(int, input().split(" ")))

L.sort()

num_triangles = 0
for i in range(N-2): # stick 1
    for j in range(i+1, N-1): # stick 2; must be larger than 1
        # if a<b then we require c<b+a
        idx = bisect_left(a=L, x=L[i]+L[j]) # find the index at which c<b+a
        num_triangles += max(0, idx-(j+1)) # c can be, at minimum, b=c
print(num_triangles)


### FIXED CODE ###

from bisect import bisect_left

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

ans = 0
for i in range(n):
    for j in range(i+1, n):
        endpt = bisect_left(l, l[i] + l[j])
        ans += endpt-j-1

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

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


X, Y, Z, K = read_ints()
A = list(map(int, read().split()))
B = list(map(int, read().split()))
C = list(map(int, read().split()))

from itertools import product

AB = [a + b for a, b in product(A, B)]
AB.sort(reverse=True)

ABC = [ab + c for ab, c in product(AB[:K], C)]
ABC.sort(reverse=True)

ABC = ABC[:K]

print(*ABC, sep='\n')



### FIXED CODE ###

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


X, Y, Z, K = read_ints()
A = read_ints()
B = read_ints()
C = read_ints()

from itertools import product

AB = [a + b for a, b in product(A, B)]
AB.sort(reverse=True)

ABC = [ab + c for ab, c in product(AB[:K], C)]
ABC.sort(reverse=True)

ABC = ABC[:K]

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

S = input()
L = len(S)

ans = 0
for i in range(L-3):
    for j in range(i+2, L+1):
        if int(S[i:j])%2019==0:
            ans += 1
print(ans)

### FIXED CODE ###

S = list(input())[::-1]
L = len(S)
from collections import defaultdict

mod = 2019
t = 0
dic = defaultdict(int)
ans = 0
for l in range(L):
    t += pow(10, l, mod)*int(S[l])%mod
    t %= mod
    ans += dic[t]
    dic[t] += 1
    if t==0:
        ans += 1

print(ans)