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

import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
 
from collections import deque
N, M = mi()
x = li2(M)
 
dp = [[0, []] for i1 in range(N+1)]
 
tmp = deque([])
 
for i in range(M):
    dp[x[i][1]][0] = max(dp[x[i][1]][0], dp[x[i][0]][0] + 1)
    dp[x[i][0]][1].append(x[i][1])
    tmp.append(x[i][1])
    while tmp != deque():
        a = tmp.popleft()
        if dp[a][1] != []:
            for b in dp[a][1]:
                dp[b][0] = max(dp[a][0] + 1, dp[b][0])
                tmp.append(b)
 
#print(dp)
print(max([row[0] for row in dp])) 

### FIXED CODE ###

import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
'''
N, M = mi()
x = li2(M)

#dp = dp2(0, 2, N)
dp = [[0, []] for i1 in range(N+1)]


for i in range(M):
    dp[x[i][1]][0] = max(dp[x[i][1]][0], dp[x[i][0]][0] + 1)
    dp[x[i][0]][1].append(x[i][1])
    if dp[x[i][1]][1] != []:
        for a in dp[x[i][1]][1]:
            dp[a][0] = max(dp[x[i][1]][0] + 1, dp[a][0])

print(dp)
print(max([row[0] for row in dp])) 
'''
from collections import deque
N, M = mi()
x = li2(M)

h = [0]*N
adj = [[] for i in range(N)]
for i in range(M):
    x[i][0] -= 1
    x[i][1] -= 1
    h[x[i][1]] += 1
    adj[x[i][0]].append(x[i][1])

zeros = deque([])
ans = []
for i in range(N):
    if h[i] == 0:
        zeros.append(i)
        ans.append(i)

while(zeros != deque()):
    a = zeros.popleft()
    if(adj[a]):
        for b in adj[a]:
            h[b] -= 1
            if h[b] == 0:
                zeros.append(b)
                ans.append(b)

#print(ans)

dp = [0]*N
#print(ans)
#print(adj)
for a in ans:
    #print(dp)
    if adj[a]:
        for b in adj[a]:
            dp[b] = max(dp[a] + 1, dp[b])
#print(dp)
print(dp[ans[-1]])
### BUGGY CODE ###

def main():
  s=input()
  n=len(s)
  ans=0
  for i in range(n-3):
    for j in range(i+3,n+1):
      if int(s[i:j])%2019==0:
        ans+=1
        break
  print(ans)
main()

### FIXED CODE ###

from collections import Counter
s=input()
n=len(s)
ans=0
arr=[0]*(n+1)
if s=='0':
    print(1)
    exit()
elif n==1:
    print(0)
    exit()
for i in reversed(range(n)):
    arr[i]=(arr[i+1]+int(s[i])*pow(10,n-i-1,2019))%2019
m=Counter(arr)
for j in m.keys():
    ans+=m[j]*(m[j]-1)//2
print(ans)
### BUGGY CODE ###

num_str=input().split()
num=list(map(int, num_str))
n=num[0]
x=num[1]
num2_str=input().split()
distance=list(map(int, num2_str))

first_distance=list(map(lambda y:abs(y-x),distance))
min_distance=min(first_distance)


for i in range(min_distance,0,-1):
    Can_go_list=list(map(lambda z: 1 if z % i == 0 else 0,first_distance))

    if 0 not in Can_go_list:
        ans = i
        print(ans)
        break


### FIXED CODE ###

num_str=input().split()
num=list(map(int, num_str))
n=num[0]
x=num[1]
num2_str=input().split()
distance=list(map(int, num2_str))

first_distance=list(map(lambda y:abs(y-x),distance))
min_distance=min(first_distance)

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


if n==1:
    print(first_distance[0])
else:
    element = gcd(first_distance[0], first_distance[1])
    if n==2:print(element)
    else:
        for i in range(2,n):
            element=gcd(element,first_distance[i])
        print(element)
### BUGGY CODE ###

import sys
from math import gcd

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def lcm(a, b):
    return a * b // gcd(a, b)


def resolve():
    n = int(input())
    A = list(map(int, input().split()))

    L = 1
    for a in A:
        L = lcm(L, a)

    res = 0
    for a in A:
        res += L // a
        res %= mod
    print(res)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def prime_factorization(n):
    res = []
    for i in range(2, int(pow(n, 0.5)) + 1):
        if n % i == 0:
            ex = 0
            while n % i == 0:
                ex += 1
                n //= i
            res.append([i, ex])
    if n != 1:
        res.append([n, 1])
    return res


def resolve():
    n = int(input())
    A = list(map(int, input().split()))

    prime = [0] * max(A)
    for a in A:
        primes = prime_factorization(a)
        for num, ex in primes:
            prime[num - 1] = max(prime[num - 1], ex)

    L = 1
    for i in range(len(prime)):
        if prime[i] == 0:
            continue
        L *= pow(i + 1, prime[i])

    res = 0
    for a in A:
        res += L * pow(a, mod - 2, mod)
        res %= mod
    print(res)


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

from collections import deque
S = deque(list(input()))
Q = int(input())

for q in range(Q):
    query = list(input().split())
    if query[0] == "1":
        S.reverse()
    elif query[1] == "1":
        S.appendleft(query[2])
    elif query[1] == "2" :
        S.append(query[2])

print("".join(map(str, S)))

### FIXED CODE ###

from collections import deque
S = deque(input())
Q = int(input())
is_reversed = 1
for _ in range(Q):
    query = list(input().split())
    if query[0] == "1":
        is_reversed *= -1
    
    else:
        if is_reversed == 1:
            if query[1] == "1":
                S.appendleft(query[2])
            else:
                S.append(query[2])
        else:
            if query[1] == "2":
                S.appendleft(query[2])
            else:
                S.append(query[2])

S = "".join(S)
print(S[::is_reversed])
### BUGGY CODE ###

n = int(input())
s = str(n)
l = len(s)

INF = float('inf')
dp = [[INF]*2 for _ in range(l+1)]
dp[0][0]=0
dp[0][1]=1
for i in range(l):
    num = int(s[i])
    dp0 = dp[i][0]
    dp1 = dp[i][1]
    dp[i+1][0] = min(dp0+num, dp1+min(10-num,num+1))
    dp[i+1][1] = min(dp0+num+1,dp1+10-num-1)

print(dp[-1][0])


### FIXED CODE ###

s = input()
l = len(s)

INF = float('inf')
dp = [[INF]*2 for _ in range(l+1)]
dp[0][0]=0
dp[0][1]=1
for i in range(l):
    num = int(s[i])
    dp0 = dp[i][0]
    dp1 = dp[i][1]
    dp[i+1][0] = min(dp0+num, dp1+min(10-num,num+1))
    dp[i+1][1] = min(dp0+num+1,dp1+10-num-1)

print(dp[-1][0])
### BUGGY CODE ###

#C
n, k, q = map(int, input().split())
a = [int(input()) for _ in range(q)]
for i in range(n):
    count = a.count(i+1)
    if q - count >= k:
        print('No')
    else:
        print('Yes')

### FIXED CODE ###

n, k, q = map(int, input().split())
a = sorted([int(input()) for _ in range(q)])
point = [k-q for _ in range(n)]
for i in range(q):
    point[a[i]-1] += 1
for j in  point:
    if j > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import math
N = int(input())
S = input()
ans = 0
JK = list()
for k in range(2, N):
    for j in range(1, k):
        if not S[j] == S[k]:
            JK.append((j, k))
for jk in JK:
    j, k = jk
    for i in range(j):
        if S[i] == S[j]:
            continue
        if S[i] == S[k]:
            continue
        if j-i == k-j:
            continue
        ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ans = S.count("R") * S.count("G") * S.count("B")
for i in range(N):
    for j in range(i, N):
        k = 2*j - i
        if N > k and S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
            ans -= 1
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
cnt = 0
for i in range(N-1):
    for j in range(i+A[i]+1, N):
        if j-i == A[i] + A[j]:
            cnt += 1
print(cnt)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A1 = [[-a-i,i] for i, a in enumerate(A)]
A2 = [[a-i,i] for i, a in enumerate(A)]
A1.sort()
A2.sort()
i = j = 0
cnt = 0
while i < N and j < N:
    if A1[i][0] == A2[j][0]:
        buf1 = 1
        for k in range(i+1, N):
            if A1[k][0] != A1[i][0]:
                break
            buf1 += 1
        buf2 = 1
        for k in range(j+1, N):
            if A2[k][0] != A2[j][0]:
                break
            buf2 += 1
        cnt += buf1 * buf2
        i += buf1
        j += buf2
    elif A1[i][0] < A2[j][0]:
        i += 1
    else:
        j += 1
print(cnt)
### BUGGY CODE ###

import sys
def b(bs, cs):
    #print(bs, xs[len(bs):])
    d = set()
    bl = len(bs)
    for bi in range(bl):
      for i, c in enumerate(cs):
        if bs[bi] > c:
            bs.append(c)
            del cs[i]
            break
      else:
        print("No")
        sys.exit()
    return bs, cs
n=int(input())
xs = sorted(list(map(int,input().split())))[::-1]
bs, cs = xs[:1], xs[1:]
for _ in range(n):
    bs, cs = b(bs, cs)

print("Yes")


### FIXED CODE ###

import sys
def b(bs, cs):
    d = set()
    bl, cl = len(bs), len(cs)
    bi, ci = 0, 0
    ncs = []
    while True:
      if bs[bi] > cs[ci]:
        bs.append(cs[ci])
        bi += 1
      else:
        ncs.append(cs[ci])
      ci += 1
      if bi == bl or ci == cl:
        break
    if len(bs) != 2 * bl:
      print("No")
      sys.exit()
    return bs, ncs + cs[ci:]

n=int(input())
xs = sorted(list(map(int,input().split())))[::-1]
bs, cs = xs[:1], xs[1:]
for _ in range(n):
    bs, cs = b(sorted(bs)[::-1], cs)

print("Yes")
### BUGGY CODE ###

import heapq

N, M = map(int, input().split())
A = [int(i) for i in input().split()]

heapq.heapify(A)

for i in range(M):
    k, v = map(int, input().split())
    while v > A[0] and k > 0:
        heapq.heappush(A, v)
        heapq.heappop(A)
        k -= 1

print(sum(A))


### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort()
A.append(0)
S = []
heapq.heapify(S)
c = A[0]
cnt = 1
for i in range(1, N + 1):
    if A[i] == c:
       cnt += 1
    else:
        heapq.heappush(S, (A[i - 1], cnt))
        cnt = 1
        c = A[i]


for i in range(M):
    B, v = map(int, input().split())
    flag = False #Sからの取り出し比較を1度以上終えているか
    b = B # 残りカード
    while len(S) > 0 and S[0][0] < v:
        x = heapq.heappop(S)
        if b <= x[1]:
            heapq.heappush(S, (v, B))
            if not b == x[1] : heapq.heappush(S, (x[0], x[1] - b))
            flag = False
            break
        else:
            flag = True
            b -= x[1]

    if flag: #交換しきらないで、途中で終わっているのでこの分は挿入する
        heapq.heappush(S, (v, B - b))

sumS = 0
while len(S) > 0:
    x = heapq.heappop(S)
    sumS += x[0] * x[1]
print(sumS)
### BUGGY CODE ###

import copy
import numpy as np
# N = int(input())
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

for i in range(K):
    B = np.array([0 for k in range(N)])
    for j in range(N):
        L = A[j]
        B[max(j-L, 0): min(j+L+1, N)] += 1
    A = copy.deepcopy(list(B))
    if len(set(A)) == 1 and A[0] == N:
        break
print(*A)


### FIXED CODE ###

# tokio marine 2020 C.Lamps
import copy
# N = int(input())
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

for i in range(K):
    B = [0 for k in range(N)]
    for j in range(N):
        L = A[j]
        l = max(j-L, 0)
        r = min(j+L, N-1)
        B[l] += 1
        if r + 1 < N:
            B[r+1] -= 1
    for j in range(1, N):
        B[j] += B[j-1]
    A = copy.deepcopy(list(B))
    if len(set(A)) == 1 and A[0] == N:
        break
print(*A)
### BUGGY CODE ###

s = input()
cnt = 0
while True:
    state = False
    if len(s) == 0:
        break
    li = []
    for i in s:
        li.append(i)
    for i in range(len(li)-1):
        if li[i] == "0" and li[i+1] == "1":
            li[i] = ""
            li[i+1] = ""
            cnt+=1
            state = True
            break
        elif li[i] == "1" and li[i+1] == "0":
            li[i] = ""
            li[i+1] = ""
            cnt+=1
            state = True
            break
    if state == False:
        break
    s = ""
    for i in range(len(li)):
        s += li[i]
print(cnt*2)
    

### FIXED CODE ###

s = input()
cnt1 = 0
cnt0 = 0
for i in range(len(s)):
    if s[i] == "0":
        cnt0 +=1
    else:
        cnt1+=1
print(min(cnt0,cnt1)*2)
### BUGGY CODE ###

s = input()
x, y = map(int, input().split())

index = 0
dxys = [(1, 0), (0, -1), (-1, 0), (0, 1)]

ss = set([(0, 0, 0)])
ns = set()
while len(s) > 0:
    c = s[0]
    p = 0
    if c == 'F':
        while len(s) and s[0] == 'F':
            p += 1
            s = s[1:]
    elif c == 'T':
        s = s[1:]
    for e in ss:
        if c == 'T':
            ns.add((e[0], e[1], (e[2]+1)%4))
            ns.add((e[0], e[1], (e[2]-1+4)%4))
        elif c == 'F':
            nx, ny = e[0] + p*dxys[e[2]][0], e[1] + p*dxys[e[2]][1]
            ns.add((nx, ny, e[2]))
    ss = ns
    ns = set()

yes = False
for i in range(4):
    if (x, y, i) in ss:
        yes = True
        break
if yes:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

s = input()
x, y = map(int, input().split())
hL = len(s)
L = 2 * hL

dp = [[False] * (L + 1) for i in range(2)]
ndp = [False] * (L + 1)

def next(i):
    global s
    while i < hL and s[i] != 'T':
        i += 1
    i += 1
    return i

def c(x):
    global hL
    return x + hL

index = 0
t = 0
js = [1]
dp[0][c(0)] = True
dp[1][c(0)] = True
mini, maxi = 0, 1
while index < hL:
    ni = next(index)
    dx, index = ni - index - 1, ni
    for i in range(mini, maxi):
        for j in js:
            if -hL <= i + j * dx <= hL:
                nx = c(i + j * dx)
                ndp[nx] = ndp[nx] or dp[t][c(i)]
    for i in range(mini, maxi):
        dp[t][c(i)] = False
    dp[t], ndp = ndp, dp[t]
    mini, maxi = mini - dx, maxi + dx
    js = [-1, 1]
    t = (t + 1) % 2
print('Yes' if dp[0][c(x)] and dp[1][c(y)] else 'No')
### BUGGY CODE ###

def f_f():
    n = int(input())
    *s, = map(int, input().split())
    s.sort()
    p1, p2 = [s[-1]], []
    s[-1] = -1
    o = "Yes"
    for _ in range(n):
        j = len(s)
        while j>-1 and p1:
            j -= 1
            if s[j]<0:
                pass
            elif p1[-1]>s[j]:
                p2 += [s[j], p1.pop()]
                s[j] = -1
                j = len(s)
        if p1:
            o="No"
            break
        p1, p2 = sorted(p2), []
    print(o)

if __name__ == "__main__":
    f_f()


### FIXED CODE ###


def f_f():
    n, *s = map(int, open(0).read().split())
    s.sort()
    ps, next_ps, cs = [s.pop()], [], []
    for _ in range(n):
        for p in ps:
            while s:
                c = s.pop()
                if p>c:
                    next_ps.append(c)
                    break
                else:
                    cs.append(c)
        s, ps, next_ps, cs = s+cs[::-1], sorted(ps+next_ps, reverse=True), [], []

    print("No" if s else "Yes")

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

from sys import stdin, stderr
from itertools import groupby, permutations, combinations
import numpy as np


def main():
    N = int(input())
    L = np.sort(np.array([int(x) for x in input().split()]))

    ret = 0
    # print(L, file=stderr)
    for ij in combinations(range(N - 1), 2):
        i, j = ij
        c = L[i] + L[j]
        k = np.searchsorted(L, c, side='right')
        if L[k - 1] == c:
            k = np.searchsorted(L, c, side='left')
        # print(L[i], L[j], k, ret, file=stderr)
        ret += k - j - 1

    # for i in range(N - 2):
    #     for j in range(i + 1, N - 1):
    #         k = np.searchsorted(L, L[i] + L[j], side='right')
    #         if L[k - 1] == L[i] + L[j]:
    #             k = np.searchsorted(L, L[i] + L[j], side='left')
    #         # print(L[i], L[j], k, ret, file=stderr)
    #         ret += k - j - 1
    return ret


if __name__ == "__main__":
    print(main())


### FIXED CODE ###

from sys import stdin, stderr
from itertools import groupby, permutations, combinations
from bisect import bisect_right
import numpy as np


def main():
    N = int(input())
    L = sorted([int(x) for x in input().split()])
    ret = 0
    # print(L, file=stderr)
    # for ij in combinations(range(N - 1), 2):
    #     i, j = ij
    #     c = L[i] + L[j] - 1
    #     k = bisect_right(L, c)
    # #     k = np.searchsorted(L, c, side='right')
    #     ret += k - j - 1

    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            c = L[i] + L[j] - 1
            # k = np.searchsorted(L, c, side='right')
            k = bisect_right(L, c)
            # print(L[i], L[j], k, ret, file=stderr)
            ret += k - j - 1
    return ret


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

#ABC068C
N,M=map(int,input().split())
A=[]
B=[]
C=[]
D=[]
for m in range(M):
	I=list(map(int,input().split()))
	if I[0]==1:
		A.append(I[0])
		B.append(I[1])
	if I[1]==N:
		C.append(I[0])
		D.append(I[1])
for b in B:
	for c in C:
		if b==c:
			print('POSSIBLE')
			exit()
print('IMPOSSIBLE')

### FIXED CODE ###

#ABC068C
N,M=map(int,input().split())
A=[]
B=[]
C=[]
D=[]
for m in range(M):
	I=list(map(int,input().split()))
	if I[0]==1:
		A.append(I[0])
		B.append(I[1])
	elif I[1]==N:
		C.append(I[0])
		D.append(I[1])
if len(set(B)&set(C))>0:
	print('POSSIBLE')
else:
	print('IMPOSSIBLE')
### BUGGY CODE ###

import fractions
N = int(input())
a = list(map(int, input().split()))
ans = a[0]
for i in range(1, N):
    ans = ans * a[i] // fractions.gcd(ans, a[i])

B = []
for i in range(N):
    B.append(ans//a[i])

print(sum(B) % (10**9 + 7))

### FIXED CODE ###

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

def lcm(a,b):
    return a*b//gcd(a,b)

N = int(input())
a = list(map(int, input().split()))
ans = a[0]
for i in range(1, N):
    ans = ans * a[i] // gcd(ans, a[i])

B = []
for i in range(N):
    B.append(ans//a[i])

print(sum(B) % (10**9 + 7))
### BUGGY CODE ###

from bisect import bisect_left, bisect_right

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

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            index = N - bisect_left(As, -(t//(-A)), lo = i+1)
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
        if count >= K:
            return False
    return True

m_count = 0
p_count = 0
for A in As:
    if A < 0:
        m_count += 1
    if A > 0:
        p_count += 1

if K <= m_count * p_count:
    l = - (10 ** 18 + 10)
    r = 0
elif K > N * (N-1) // 2 - p_count * (p_count-1) // 2 - m_count * (m_count-1) // 2 :
    l = 0
    r = 10 ** 18 + 10
else:
    print(0)
    exit()

while r - l > 1:
    mid = (l + r) // 2
    if check(mid):
        l = mid
    else:
        r = mid

print(r)


### FIXED CODE ###

from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))
        
l = - (10 ** 18 + 10)
r = 10 ** 18 + 10
while True:
    mid = (l + r) // 2
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            count += bisect_right(As, mid//A, lo = i+1) - (i+1)
        elif A < 0:
            count += N - bisect_left(As, -((-mid)//A), lo = i+1)
        else:
            if mid >= 0:
                count += N - i - 1
    if count < K:
        l = mid
    else:
        r = mid
    if r - l == 1:
        break

print(r)
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

import sys
input = sys.stdin.readline

if __name__=='__main__':
  N, K = map(int, input().split())
  sushis = sorted((tuple(map(int, input().split())) for _ in range(N)), key=lambda x:x[1], reverse=True)

  curr = sushis[:K]
  leave = sushis[K:]
  base = lambda li: sum([l[1] for l in li])
  types_max = len(set([c[0] for c in sushis]))
  types = []
  dups = []

  for c in curr:
    if c[0] in types:
      dups += [c]
    else:
      types += [c[0]]
  types = list(set(types))

  ps = base(curr) + len(types)**2
  di = {}
  di[len(types)] = ps
  n_types = len(types) + 1
  for l in leave:
    if len(types) >= types_max:
      break
    if len(dups) == 0:
      break
    if not l[0] in types:
      dup = dups.pop()
      di[n_types] = ps - dup[1] + l[1] + n_types**2 - (n_types-1)**2
      ps = di[n_types]
      n_types += 1
      types += [l[0]]

  print(sorted(di.items(), key=lambda x:x[1])[-1][1])

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

import sys
input = sys.stdin.readline

def main():
  N, K = map(int, input().split())
  sushis = [tuple(map(int, input().split())) for _ in range(N)]
  sushis.sort(key=lambda x:x[1], reverse=True)
  curr = sushis[:K]
  leave = sushis[K:]
  base = lambda li: sum([l[1] for l in li])
  types_max = len(set([c[0] for c in sushis]))
  types = set()
  dups = []

  for c in curr:
    if c[0] in types:
      dups += [c]
    else:
      types.add(c[0])
  types = set(types)

  ps = base(curr) + len(types)**2
  di = {}
  di[len(types)] = ps
  n_types = len(types) + 1
  for l in leave:
    if len(types) >= types_max:
      break
    if len(dups) == 0:
      break
    if not l[0] in types:
      dup = dups.pop()
      di[n_types] = ps - dup[1] + l[1] + n_types**2 - (n_types-1)**2
      ps = di[n_types]
      n_types += 1
      types.add(l[0])

  print(sorted(di.items(), key=lambda x:x[1])[-1][1])


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

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

S = 0
reg = 0

for i in range(n-k+1):
    s = sum(p[i:i+k])
    if S < s:
        S = s
        reg = i
        
ans = 1 / 2 *(S + k)

print(ans)

### FIXED CODE ###

n , k = map(int, input().split())
p = list(map(int, input().split()))
p_accu = [p[0] + 1]

if k == 1:
    print((max(p) + 1 ) / 2 )
    exit()
elif k == n:
    print((sum(p) + n ) / 2 )
    exit()

for i in range(1, n):
    p[i] += p[i-1] + 1
    p_accu.append(p[i])

S = p_accu[k-1]

for i in range(n - k):
    if S < p_accu[i+k] - p_accu[i]:
        S = p_accu[i+k] - p_accu[i]
    
print(S/2)
### BUGGY CODE ###

INF=float('inf')
import numpy as np

n=int(input())
P=list(map(float,input().split()))#0

dp=np.zeros([n+1,n+1], dtype='float128')

for i in range(n+1):
  if i==0:
    dp[0][0]=1
  else:
    dp[i][0]=(1-P[i-1])*dp[i-1][0]

    
for j in range(1,n+1):
  for i in range(1,n+1):
    if i<j:
      continue
    dp[i][j]=P[i-1]*(dp[i-1][j-1])+(1-P[i-1])*(dp[i-1][j])

ans=0
for i in range(1,n+1):
  if i>=(n+1)//2:
    ans+=dp[n][i]
    
print(ans)

### FIXED CODE ###

INF=float('inf')

n=int(input())
P=list(map(float,input().split()))#0

dp=[[0 for i in range(n+1)] for j in range(n+1)]

for i in range(n+1):
  if i==0:
    dp[0][0]=1
  else:
    dp[i][0]=(1-P[i-1])*dp[i-1][0]

    
for j in range(1,n+1):
  for i in range(1,n+1):
    if i<j:
      continue
    dp[i][j]=P[i-1]*(dp[i-1][j-1])+(1-P[i-1])*(dp[i-1][j])

ans=0
for i in range(1,n+1):
  if i>=(n+1)//2:
    ans+=dp[n][i]
    
print(ans)
### BUGGY CODE ###

import itertools
x = 10**9 + 7
n = int(input())
a = list(map(lambda i: i % x , map(int, input().split(" "))))

ans = 0
for i, j in itertools.combinations(range(n), 2):
    ans += (a[i] * a[j]) % x
print(ans % x)

### FIXED CODE ###

import itertools
x = 10**9 + 7
n = int(input())
a = list(map(lambda i: i % x , map(int, input().split(" "))))
sum_a = []
prev = 0
for i in a:
    sum_a.append(prev + i)
    prev = prev + i

ans = 0
for i in range(n):
    ans += (a[i] * (sum_a[n-1] - sum_a[i] )) % x
print(ans % x)