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

from collections import defaultdict
import sys
input = sys.stdin.readline
nmax = 10**5+10
eratos = [0 for i in range(nmax+1)]
prime = []
cnt = 2
while True:
  while cnt <= nmax and eratos[cnt]:
    cnt += 1
  if cnt > nmax:
    break
  eratos[cnt] = 1
  prime.append(cnt)
  for i in range(cnt**2,nmax+1,cnt):
    eratos[i] = 1
cbls = []
sqst = set()
for i in prime:
  if i**3 <= 10**10:
    cbls.append(i**3)
  else:
    sqst.add(i**2)
n = int(input())
a = [int(input()) for i in range(n)]
dc = defaultdict(int)
for i in a:
  for p in cbls:
    while i%p == 0:
      i //= p
  dc[i] += 1
ans = n
for i,v in dc.items():
  if i == 1:
    ans -= v-1
    continue
  if v == 0:
    continue
  if i in sqst:
    x = int(i**0.5+0.5)
  else:
    x = 1
    for p in prime:
      if i%(p*p) == 0:
        x *= p
        i //= p*p
      elif i%p == 0:
        x *= p**2
        i //= p
    if x == 1:
      continue
  if x in dc:
    ans -= min(dc[x],v)
    dc[x] = 0
print(ans)

### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline
nmax = 10**5+10
eratos = [0 for i in range(nmax+1)]
prime = []
cnt = 2
while True:
  while cnt <= nmax and eratos[cnt]:
    cnt += 1
  if cnt > nmax:
    break
  eratos[cnt] = 1
  prime.append(cnt)
  for i in range(cnt**2,nmax+1,cnt):
    eratos[i] = 1
cbls = []
sqst = set()
for i in prime:
  if i**3 <= 10**10:
    cbls.append(i**3)
  else:
    sqst.add(i**2)
n = int(input())
a = [int(input()) for i in range(n)]
dc = defaultdict(int)
for i in a:
  for p in cbls:
    while i%p == 0:
      i //= p
  dc[i] += 1
ans = n
for i,v in dc.items():
  if i == 1:
    ans -= v-1
    continue
  if v == 0:
    continue
  x = 1
  for p in prime:
    if p**3 > 10**10:
      break
    if i%(p*p) == 0:
      x *= p
      i //= p*p
    elif i%p == 0:
      x *= p**2
      i //= p
  if i in sqst:
    x *= int(i**0.5+0.5)
    i //= i
  if i != 1:
    continue
  if x in dc:
    ans -= min(dc[x],v)
    dc[x] = 0
print(ans)
### BUGGY CODE ###

import sys
import numpy as np

n, k, q = [int(nkq) for nkq in input().split()]
arr = np.full(n, k, dtype=np.int64)

for i in range(q):
  a_i = int(input())
  
  for j in range(n):
    if arr[j] > 0 and j+1 != a_i:
      arr[j] -= 1

for j in range(n):
  if arr[j] == 0:
    print("No")
  else:
    print("Yes")



### FIXED CODE ###

import numpy as np

n, k, q = [int(nkq) for nkq in input().split()]
arr = np.full(n, k-q, dtype=np.int64)

for i in range(q):
  a_i = int(input()) 
  arr[a_i-1] += 1

for j in range(n):
  if arr[j] > 0:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

import sys
finput=lambda:sys.stdin.readline().strip()

def main():
    p=10**9+7
    n=int(finput())
    a=list(map(int,finput().split()))
    k=sum(a)-(n*(n+1))//2
    pk=[i for i in range(n+1) if a[i]==k]
    fact=[1]*(n+2)
    ifact=[1]*(n+2)
    for i in range(1,n+2):
        fact[i]=fact[i-1]*i % p
    a=fact[-1]
    inv=1
    m=p-2
    while m>0:
        if m&1:
            inv=a*inv % p
        m>>=1
        a=a*a % p
    ifact[-1]=inv
    for i in range(n+1,0,-1):
        ifact[i-1]=ifact[i]*i
    ans0=[0]*(n+2)
    ans1=[0]*(n+2)
    ans2=[0]*(n+2)
    sn=pk[0]+n-pk[1]
    for i in range(0,n+2):
        if i<n:
            ans0[i]=fact[n-1]*ifact[n-i-1]*ifact[i]%p
            ans1[i+1]=ans0[i]*2-(sn>=i)*(fact[sn]*ifact[sn-i]*ifact[i] % p)
            ans2[i+2]=ans0[i]
        if i>0:
            print((ans0[i]+ans1[i]+ans2[i]) % p)

if __name__=='__main__':
    main()




### FIXED CODE ###

import sys
finput=lambda:sys.stdin.readline().strip()

def main():
    p=10**9+7
    n=int(finput())
    a=list(map(int,finput().split()))
    k=sum(a)-(n*(n+1))//2
    pk=[i for i in range(n+1) if a[i]==k]
    fact=[1]*(n+2)
    ifact=[1]*(n+2)
    for i in range(1,n+2):
        fact[i]=fact[i-1]*i % p
    a=fact[-1]
    inv=1
    m=p-2
    while m>0:
        if m&1:
            inv=a*inv % p
        m>>=1
        a=a*a % p
    ifact[-1]=inv
    for i in range(n+1,0,-1):
        ifact[i-1]=ifact[i]*i % p
    ans0=[0]*(n+2)
    ans1=[0]*(n+2)
    ans2=[0]*(n+2)
    for i in range(n):
        ans0[i]=fact[n-1]*ifact[n-i-1]*ifact[i]%p
        ans1[i+1]=ans0[i]*2
        ans2[i+2]=ans0[i]
    sn=pk[0]+n-pk[1]
    for i in range(sn+1):
        ans1[i+1]-=fact[sn]*ifact[sn-i]*ifact[i] % p
    for i in range(1,n+2):
        print((ans0[i]+ans1[i]+ans2[i]) % p)

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

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

sumA = sum(A)
ct = {0:1}

for a in A:
  nct = {}
  for k in ct:
    nct[k] = nct.get(k, 0) + ct[k]
    nct[k+a] = nct.get(k+a, 0) + ct[k]
  ct = nct

ct[0] = 0
medidx = (2**N)//2
n = 0
keys = list(ct.keys())
keys.sort()
for key in keys:
  n += ct[key]
  if n >= medidx:
    print(key)
    exit()

### FIXED CODE ###

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

sumA = sum(A)
halfA = math.ceil(sumA / 2)
bitset = 1
for a in A:
  bitset |= bitset << a

bitset >>= halfA
i = 0
while i < halfA:
  if bitset & 1:
    print(i+halfA)
    exit()
  bitset >>= 1
  i += 1
print(i+halfA)
### BUGGY CODE ###

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

ans = N
for i in range(N):
    cnt = 0
    for j in range(N):
        if i < j and S[j] == 'E':
            cnt += 1
        if i > j and S[j] == 'W':
            cnt += 1
    if cnt < ans:
        ans = cnt

print(ans)


### FIXED CODE ###

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

cnt = S.count('E')
if S[0] == 'E':
    cnt -= 1
ans = cnt
for i in range(1, N):
    if S[i] == 'E':
        cnt -= 1
    if S[i - 1] == 'W':
        cnt += 1
    if cnt < ans:
        ans = cnt
print(ans)
### BUGGY CODE ###

N = int(input())
List = list(input())
ListR = []
ListG = []
ListB = []

for i in range(N):
  if List[i]=="R":
    ListR.append(i)
  elif List[i]=="G":
    ListG.append(i)
  else:
    ListB.append(i)
    
ans = len(ListR)*len(ListG)*len(ListB)
for a in ListR:
  for b in ListG:
    for c in ListB:
      L=[a,b,c]
      L.sort()
      if L[1]-L[0] == L[2]-L[1]:
        ans -=1
print(ans)

### FIXED CODE ###

N = int(input())
List = list(input())
ans = (List.count("R"))*(List.count("G"))*(List.count("B"))

for i in range(1,2000):
  for j in range(N-i*2):
    if {List[j], List[j+i], List[j+2*i]} == {"R","G","B"}:
      ans -=1
print(ans)
### BUGGY CODE ###

def main():
    k, q = map(int, input().split())
    d = list(map(int, input().split()))
    nxm = [list(map(int, input().split())) for _ in [0]*q]
    for n, x, m in nxm:
        d2 = sum([(i-1) % m+1 for i in d[:(n-2) % k+1]])
        d3 = sum([(i-1) % m+1 for i in d[(n-2) % k+1:]])
        print(n-1-(x % m+(d2+d3)*((n-2)//k)+d2)//m)


main()


### FIXED CODE ###

def main():
    k, q = map(int, input().split())
    d = list(map(int, input().split()))
    nxm = [list(map(int, input().split())) for _ in [0]*q]
    for n, x, m in nxm:
        d2 = sum([(i-1) % m+1 for i in d[:(n-2) % k+1]])
        d3 = sum([(i-1) % m+1 for i in d[(n-2) % k+1:]])
        print(n-1-(x % m+(d2+d3)*((n-2)//k)+d2)//m)


main()
### BUGGY CODE ###

N=int(input())
ans=0
for i in range(N):
  ans+=i
print(ans)

### FIXED CODE ###

N=int(input())
print((N-1)*N//2)
### BUGGY CODE ###

def is_prime(n):
  ps = [2, 3, 5, 7, 11, 13, 17]
  for p in ps:
    if n == p: return 1
    if n % p == 0: return 0
  t = 19
  while n > t:
    if n % t == 0: return 0
    t += 2
  return 1

c = 0
for _ in range(int(input())):
  c += is_prime(int(input()))
print(c)


### FIXED CODE ###

def is_prime(x):
  if x == 2: return 1
  if x % 2 == 0: return 0
  for i in range(3, int(x ** 0.5) + 1, 2):
    if x % i == 0: return 0
  return 1

c = 0
for _ in range(int(input())):
  c += is_prime(int(input()))
print(c)
### BUGGY CODE ###

n = input()
st = input()

N = n.split(' ')[0]
Q = int(n.split(' ')[1])

for i in range(0, Q):
    n = input()
    l = int(n.split(' ')[0])
    r = int(n.split(' ')[1])
    partial = st[l-1:r]
    count = 0
    for i in range(0, len(partial) - 1):
        if partial[i] != 'A':
            continue

        AC = partial[i:i+2]
        if AC == 'AC':
            count += 1

    print(count)

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
a = [list(map(int, input().split())) for i in range(q)]

cum=[0]*n
for i in range(1, n):
    cum[i] = cum[i - 1]
    if s[i-1:i+1] == 'AC':
        cum[i]+=1

for i in range(q):
    print(cum[a[i][1]-1]-cum[a[i][0]-1])
### BUGGY CODE ###

import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def main():
	a = int(input())
	al=[]
	for i in range(a):
		b = int(input())
		al.append(b)
		
	opened_list=set()
	st=0
	opened_list.add(st)
	count=0
	while st != 1:
		st = al[st]-1
		count+=1
		if st in opened_list:
			return -1
			
	return count
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def main():
	a = int(input())
	al=[]
	for i in range(a):
		b = int(input())
		al.append(b)
		
	opened_list=set()
	st=0
	opened_list.add(st)
	count=0
	while st != 1:
		st = al[st]-1
		count+=1
		if st in opened_list:
			return -1
		opened_list.add(st)
			
	return count
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
### BUGGY CODE ###

n = int(input())
s = input()

R_inds = []
G_inds = []
B_inds = []

for i in range(n):
    if s[i] == 'R':
        R_inds.append(i)
    elif s[i] == 'G':
        G_inds.append(i)
    else:
        B_inds.append(i)
    
ans = 0
for r in R_inds:
    for g in G_inds:
        big = max(r,g)
        small = min(r,g)
        bigger = big + (big - small)
        smaller = small - (big - small)
        if (big - small) % 2 == 0:
            middle = (big + small) // 2
        else:
            middle = -1
        
        subans = 0
        subans += len(B_inds)
        if smaller in B_inds:
            subans -= 1
        if bigger in B_inds:
            subans -= 1
        if middle in B_inds:
            subans -= 1
        if subans > 0:
            ans += subans

print(ans)


### FIXED CODE ###

n = int(input())
s = input()
R_ls = [0] * n
G_ls = [0] * n
B_ls = [0] * n
R_csum = [0] * n
G_csum = [0] * n
B_csum = [0] * n
for i in range(n):
    if s[i] == 'R':
        R_ls[i] = 1
        R_csum[i] = R_csum[i-1] + 1
        G_csum[i] = G_csum[i-1]
        B_csum[i] = B_csum[i-1]
    elif s[i] == 'G':
        G_ls[i] = 1
        G_csum[i] = G_csum[i-1] + 1
        R_csum[i] = R_csum[i-1]
        B_csum[i] = B_csum[i-1]
    else:
        B_ls[i] = 1
        B_csum[i] = B_csum[i-1] + 1
        R_csum[i] = R_csum[i-1]
        G_csum[i] = G_csum[i-1]
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        if (s[i] == 'R' and s[j] == 'G') or (s[i] == 'G' and s[j] == 'R'):
            now = B_csum[-1] - B_csum[j]
            if j + (j-i) < n and s[2*j-i] == 'B':
                now -= 1
        elif (s[i] == 'R' and s[j] == 'B') or (s[i] == 'B' and s[j] == 'R'):
            now = G_csum[-1] - G_csum[j]
            if j + (j-i) < n and s[2*j-i] == 'G':
                now -= 1
        elif (s[i] == 'G' and s[j] == 'B') or (s[i] == 'B' and s[j] == 'G'):
            now = R_csum[-1] - R_csum[j]
            if j + (j-i) < n and s[2*j-i] == 'R':
                now -= 1
        else:
            now = 0
        ans += now
print(ans)
### BUGGY CODE ###

import numpy as np
h,w,m=map(int, input().split())
hw=[list(map(int,input().split())) for i in range(m)]
H=np.zeros(h)
W=np.zeros(w)
for i in range(m):
    hi,wi=hw[i]
    H[hi-1]+=1
    W[wi-1]+=1
hmax=[i for i, x in enumerate(H) if x == max(H)]
wmax=[i for i, x in enumerate(W) if x == max(W)]
ans=0
for hi in hmax:
    for wi in wmax:
        if [hi+1,wi+1] in hw:
            ans=max(ans,max(H)+max(W)-1)
        else:
            ans=max(ans,max(H)+max(W))
print(int(ans))

### FIXED CODE ###

import numpy as np
h,w,m=map(int, input().split())
hw=[tuple(map(int,input().split())) for i in range(m)]
H=np.zeros(h)
W=np.zeros(w)
for i in range(m):
    hi,wi=hw[i]
    H[hi-1]+=1
    W[wi-1]+=1
mh=max(H)
mw=max(W)
hmax=[i for i, x in enumerate(H) if x == mh]
wmax=[i for i, x in enumerate(W) if x == mw]
f=0
for i in range(m):
    hi,wi=hw[i]
    if H[hi-1]==mh and W[wi-1]==mw:
        f+=1
if len(hmax)*len(wmax)-f<1:
    print(int(mh+mw-1))
else:
    print(int(mh+mw))
### BUGGY CODE ###

from collections import*
n=int(input())
a=list(map(int,input().split()))
b=Counter(list(map(int,input().split())))
c=Counter(a)
d=Counter()
for i in c.keys():
  if n-b[i]<c[i]:
    print('No')
    exit()
print('Yes')
i=n-1
while i>=0:
  x=a[i]
  for y in b.keys():
    if x==y:continue
    for j in range(min(b[y],c[x])):
      a[i]=y
      d+=Counter({y:1})
      i-=1
    c[x]-=j+1
  b-=d
print(*a)

### FIXED CODE ###

from collections import*
from bisect import*
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ca=Counter(a)
cb=Counter(b)
for i in a:
  if ca[i]+cb[i]>n:
    print('No')
    exit()
print('Yes')
ba=[bisect(a,i+1) for i in range(n)]
bb=[bisect_left(b,i+1) for i in range(n)]
i=0
for x,y in zip(ba,bb):
  i=max(i,x-y)
ans=b[n-i:]+b[:n-i]
print(*ans)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    e = [[] for _ in range(n)]
    if m > 0:
        for _ in range(m):
            l,r,d = LI()
            e[l-1].append((r-1,d))
            e[r-1].append((l-1,-d))

    b = [False] * n
    def g(i):
        b[i] = 0
        q = [i]
        qi = 0
        while len(q) > qi:
            j = q[qi]
            qi += 1
            c = b[j]
            for r,d in e[j]:
                if b[r] == False:
                    b[r] = c+d
                    q.append(r)
                else:
                    if b[r] != c+d:
                        return False
        return True

    for i in range(n):
        if b[i] != False:
            continue
        if not g(i):
            return 'No'
    return 'Yes'


print(main())




### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    e = [[] for _ in range(n)]
    if m > 0:
        for _ in range(m):
            l,r,d = LI()
            e[l-1].append((r-1,d))
            e[r-1].append((l-1,-d))

    b = [None] * n

    for i in range(n):
        if not b[i] is None:
            continue
        b[i] = 0
        q = [i]
        qi = 0
        nq = []
        while True:
            if len(q) == qi:
                if not nq:
                    break
                q = nq
                qi = 0
                nq = []
            j = q[qi]
            qi += 1
            c = b[j]
            for r,d in e[j]:
                if b[r] is None:
                    b[r] = c+d
                    nq.append(r)
                else:
                    if b[r] != c+d:
                        return 'No'

    return 'Yes'


print(main())
### BUGGY CODE ###

import sys
import re
s = sys.stdin.read().strip()
n = len(s)

while len(re.findall("10|01", s)) > 0:
    s = re.sub("10|01", "", s)
print(n - len(s))

### FIXED CODE ###

import sys
s = sys.stdin.read().strip()
n = len(s)
print(2 * min(s.count("0"), s.count("1")))
### BUGGY CODE ###

N = int(input())
l = [int(x) for x in input().split()]
l.sort(reverse=True)
ans = 0
room = [l[0]]
for i in range(1, N):
    ans += room.pop(0)
    room.append(l[i])
    room.append(l[i])
print(ans)

### FIXED CODE ###

import queue

N = int(input())
l = [int(x) for x in input().split()]
l.sort(reverse=True)
ans = 0
room = queue.Queue()
room.put(l[0])
for i in range(1, N):
    ans += room.get()
    room.put(l[i])
    room.put(l[i])
print(ans)
### BUGGY CODE ###

S = input()
cnt = 0
for i in range(len(S)):
    for j in range(i + 4, len(S)):
        if int(S[i:j + 1]) % 2019 == 0:
            cnt += 1
print(cnt)


### FIXED CODE ###

import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
from collections import defaultdict
def main():
    S_ = S()
    mod_list = defaultdict(int)
    ans = 0
    num = 0
    point = 1
    for i in S_[::-1]:
        num += int(i) * point
        mod = int(num) % 2019
        mod_list[mod] += 1
        point *= 10
        point %= 2019
    values_ = mod_list.values()
    ans += mod_list[0]
    for value in values_:
        ans += (value - 1) * value // 2

    print(ans)

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

def main():
    N = int(input())
    edges = [int(i) for i in input().split()]

    ans = set()
    for i, a in enumerate(edges):
        for j, b in enumerate(edges[i+1:]):
            for k, c in enumerate(edges[i+j+2:]):
                if a < b + c and b < c + a and c < a + b:
                    ans.add((a, b, c))
    print(len(ans))


if __name__ == "__main__":
    main()

### FIXED CODE ###

import bisect


def main():
    N = int(input())
    edges = [int(i) for i in input().split()]
    edges.sort()
    ans = 0
    for a in range(N - 2):
        for b in range(a + 1, N - 1):
            ans += bisect.bisect_left(edges, edges[a] + edges[b])-b-1

    print(ans)


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

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

L_len = len(L)

count = 0
for i in range(L_len - 2):
    for j in range(i + 1, L_len - 1):
        for k in range(j + 1, L_len):
            f = 0
            if L[i] >= L[j] + L[k]:
                f = 1
            if L[j] >= L[i] + L[k]:
                f = 1
            if L[k] >= L[i] + L[j]:
                f = 1
            
            if f == 0:
                count += 1

print(count)

### FIXED CODE ###

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

from bisect import bisect_left

L.sort()

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

print(count)
### BUGGY CODE ###

#ABC154D
import sys

n, k = map(int, sys.stdin.readline().split())
p = list(map(int, sys.stdin.readline().split()))
L = [0 for _ in range(n)]
for i in range(n):
    L[i] = (1 + p[i])/2

ans = 0
for i in range(n+1-k):
    tmp = sum(L[i:i+k])
    if ans < tmp:
        ans = tmp

print(ans)

### FIXED CODE ###

#ABC154D
import sys
N, K = map(int, sys.stdin.readline().split())
P = list(map(int, sys.stdin.readline().split()))

#print(P)

#期待値L
L = [0 for _ in range(N)]
for i in range(N):
    L[i] = (1+P[i])/2
#print(L)

#累積和S
S = [0 for i in range(N)]
S[0] = L[0]
for i in range(1, N):
    S[i] = S[i-1] + L[i]

#print(S)
total = S[K-1]
for i in range(N-K):
    tmp = S[i+K]-S[i]
    if total < tmp:
        total = tmp

print(total)
### BUGGY CODE ###

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

for i in a:
    ans *= i

if ans > 10 ** 18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

if 0 in a:
    print(0)
else:
    for i in a:
        ans *= i
        if ans > 10 ** 18:
            print(-1)
            break
    else:
        print(ans)
### BUGGY CODE ###

import queue
N=int(input())
d=[-1 for _ in range(N+1)]
e=[[] for _ in range(N+1)]
for _ in range(N-1):
	a,b,c=map(int,input().split())
	e[a].append([b, c])
	e[b].append([a, c])
Q,K=map(int,input().split())
d[K]=0
q=queue.Queue()
q.put(K)
while not q.empty():
	now=q.get()
	for nx,c in e[now]:
		if d[nx] == -1:
			d[nx] = c+d[now]
			q.put(nx)
for _ in range(Q):
	x,y=map(int,input().split())
	print(d[x]+d[y])


### FIXED CODE ###

import sys
sys.setrecursionlimit(1145141919)
N=int(input())
d=[-1 for _ in range(N+1)]
e=[[] for _ in range(N+1)]
for _ in range(N-1):
	a,b,c=map(int,input().split())
	e[a].append((b, c))
	e[b].append((a, c))
Q,K=map(int,input().split())
def dfs(now, dis):
	d[now] = dis
	for nxt,cos in e[now]:
		if d[nxt] == -1:
			dfs(nxt, dis+cos)
dfs(K, 0)
for _ in range(Q):
	x,y=map(int,input().split())
	print(d[x]+d[y])
### BUGGY CODE ###

from bisect import bisect_left as bl
from math import factorial as f

def comb(a,b) :
    a,b = min(a,b),max(a,b)
    return f(b)//(f(a)*f(b-a))


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

p = L[-1]
q = bl(L,p/2)
#print(q)
if N == 2 :
    q = 0
    r = L[q]
else :
    if abs((p/2)-L[q]) < abs((p/2)-L[q-1]) :
        r = L[q]
    else :
        r = L[q-1]

ans = comb(p,r)
#print(ans)
print(p,r)


### FIXED CODE ###

from bisect import bisect_left as bl

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

p = L[-1]
q = bl(L,p/2)
if N == 2 :
    r = L[0]
else :
    if abs((p/2)-L[q]) < abs((p/2)-L[q-1]) :
        r = L[q]
    else :
        r = L[q-1]
print(p,r)
### BUGGY CODE ###

N=int(input())

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

B=sorted(A,reverse=True)

ans=B[0]

C=[B[0],B[1]]

ans=B[0]
for i in range(2,N):
    jmax=1
    scoremax=min(C[0],C[1])
    for j in range(1,len(C)-1):
        score = min(C[j],C[j+1])
        if scoremax < score:
            scoremax = score
            jmax=j
    ans += scoremax
    C=C[0:jmax]+[B[i]]+C[jmax:]
    # print(C)

print(ans)

### FIXED CODE ###

N=int(input())

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

B=sorted(A,reverse=True)

ans=B[0]

sheets=[B[0]]

ans=0
for i in range(1,N):

    ans += sheets[i-1]
    sheets.append(B[i])
    sheets.append(B[i])

print(ans)