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

A = list(map(int , input().split()))
B = list(map(int , input().split()))
ans = 0.0
SS = {sum(B[i:i+A[1]]):B[i:i+A[1]] for i in range(len(B)-A[1]+1)}
for i in SS[max(SS)]:
     ans += (i/2*(i+1))/i
print(ans)

### FIXED CODE ###

A = list(map(int , input().split()))
B = list(map(int , input().split()))
kitaiti =[(i+1)/2 for i in B]
ans = []
dd = [0]
for i in range(A[0]):
    dd.append(dd[i] + kitaiti[i])
for i in range(A[1] , A[0]+1):
    ans.append(dd[i] - dd[i - A[1]])
print(max(ans))
### BUGGY CODE ###

N = int(input())


def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1

    return len(lower_divisors) + len(upper_divisors)


ans = 0
for i in range(N):
    ans += (i+1) * make_divisors(i+1)
print(ans)


### FIXED CODE ###

N = int(input())

ans = 0
for i in range(1, N + 1):
    p = N // i
    ans += (p * (p + 1) * i) // 2
print(ans)
### BUGGY CODE ###

n,p=map(int,input().split())
s=input()
cnt=0

if p==2 or p==5:
    for i in range(n):
        if int(s[i])%p==0:
            cnt+=i+1
else:
    U=[int(s[i:])%p for i in range(n)]+[0]
    Mod={i:0 for i in range(p)}
    for i in range(n+1):
        Mod[U[i]]+=1
    for i in range(p):
        cnt+=Mod[i]*(Mod[i]-1)//2

print(cnt)

### FIXED CODE ###

#E
from collections import Counter
n,p=map(int,input().split())
s=input()
cnt=0

if p==2 or p==5:
    for i in range(n):
        if int(s[i])%p==0:
            cnt+=i+1
else:
    U=[0]*(n+1)
    for i in range(n,0,-1):
        U[i-1]=(int(s[i-1])*pow(10,n-i,p)+U[i])%p
    #print(U)
    C=Counter(U)
    for c in C.values():
        cnt+=c*(c-1)//2

print(cnt)
### BUGGY CODE ###

K=int(input())
def gcd(a,b):
    if a <b:
        a,b=b,a
    while a%b != 0:
        a,b= b,a%b
    return b
x=0
for i in range(1,K+1):
    for j in range(1,K+1):
        for l in range(1,K+1):
            x+=gcd(gcd(i,j),l)
print(x)


### FIXED CODE ###

K=int(input())
def gcd(a,b,c):
    if a <b:
        a,b=b,a
    while a%b != 0:
        a,b= b,a%b
    if b < c:
        b,c=c,b
    while b % c != 0:
        b,c = c,b%c
    return c
x=0
for i in range(1,K+1):
    for j in range(1,K+1):

            for l in range(1,K+1):
                
                    if (i==1) or (j==1) or (l==1):
                        x+=1
                    else:
                        x += gcd(i,j,l)
print(x)
### BUGGY CODE ###

import sys
n,k = map(int,input().split())
input = sys.stdin.readline
list1 = list(input())
list2 = []
count = 1
for i in range(1,n):
	if list1[i] != list1[i-1]:
		list2.append(count)
		count = 0
	count += 1
list2.append(count) #最後の処理
length = 0
list3 = []
#以下のループはn=1のときのみうまく動作しないので、例外処理
if n ==1:
	print(1)
	exit()

if list1[0] == "0": #長さはk*2
	length1 = k*2 #初期値
	length2 = k*2 + 1
	for i in range(len(list2)):
		if length != length1:
			length = length1
		else:
			length = length2
		if i+length >= n:
			break
		list3.append(sum(list2[i:i+length]))

else: #長さはk*2+1
	length1 = k*2 +1 #初期値
	length2 = k*2
	for i in range(len(list2)):
		if length != length1:
			length = length1
		else:
			length = length2
		if i+length >= n:
			break
		list3.append(sum(list2[i:i+length]))
if len(list3) == 0:
	print(n)
	exit()
print(max(list3))

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,k = map(int,readline().split())
s = readline().rstrip().decode('utf-8')

if s[0] == 0: #反転からスタート
    r = 0
else: #無操作からスタート
    r = 1

if r==0:
    lst1 = [0] #裏からに調整
else:
    lst1 = []
res = 0
cache = str(r)
for i in s:
    if i != cache:
        lst1.append(res)
        cache = "1" if cache=="0" else "0"
        res = 1
    else:
        res += 1

lst1.append(res)
lst1.append(0)

#全部1で埋められるなら
if len(lst1) <= 2*k:
    print(n)
    exit()

#累積和
for i in range(len(lst1)-1):
    lst1[i+1] += lst1[i]

def cumsumdif(a,b,lst): #求めたい差のインデックスを入れる
    if a == 0:
        return lst[b]
    else:
        return lst[b] - lst[a-1]
i = 0
ans = 0
while True:
    if i+(k*2) >= len(lst1):
        break
    ans = max(ans,cumsumdif(i,i+2*k,lst1))
    i += 2

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

import math
import sys
import numpy as np
import collections

#n, a, b= map(int, input().split())
n, y  = map(int, input().split())
#s = list(str(input()))
#n = int(input())

max1 = int(y/10000) + 1

for i in reversed(range(max1)):
  rest1 = y-i*10000
  max2 = int((rest1)/5000) + 1
  for ii in reversed(range(max2)):
    rest2 = y-i*10000-ii*5000
    mod = rest2%1000
    iii = int(rest2/1000)
    tot = i+ii+iii
    if(mod == 0 and tot == n):
      print(i, ii, iii)
      sys.exit()

print(-1,-1,-1)

### FIXED CODE ###

import math
import sys
import numpy as np
import collections

#n, a, b= map(int, input().split())
n, y  = map(int, input().split())
#s = list(str(input()))
#n = int(input())

max1 = int(y/1000) + 1

for i in range(max1):
  rest = y-i*9000-n*1000
  mod = rest%4000
  ii  = int((rest)/4000)
  iii = n-i-ii
  if(mod == 0 and iii>=0 and ii>=0):
    print(i, ii, iii)
    sys.exit()
    
print(-1,-1,-1)
### BUGGY CODE ###

import math
data = input()
num = int(data)
o = input().rstrip().split(" ")
list =[]
for i in o:
    list.append(int(i))
list.sort()
p = input()
times = int(p)
ans = sum(list)
num_count=[list.count(i) for i in range(100001)]
for i in range(times):
    B, C = map(int, input().split(" "))
    a = num_count[B]
    num_count[B] = 0
    num_count[C] += a
    ans += a*(C-B)
    print(ans)

### FIXED CODE ###

import math
data = input()
num = int(data)
o = input().rstrip().split(" ")
list =[]
for i in o:
    list.append(int(i))
p = input()
times = int(p)
ans = sum(list)
num_count=[0 for i in range(100001)]
for i in list:
    num_count[i] += 1
for i in range(times):
    B, C = map(int, input().split(" "))
    a = num_count[B]
    num_count[B] = 0
    num_count[C] += a
    ans += a*(C-B)
    print(ans)
### BUGGY CODE ###

# ABC 142 C 
N = int(input())
A = [int(j) for j in input().split()]
ans =""
for i in range(1,N+1):
    ans += str(A.index(i)+1)+" "
print(ans)

### FIXED CODE ###

N = int(input())
A =[int(a) for a in input().split()]
AL=[]
for i,a in enumerate(A):
    AL.append([i+1,a])
AL.sort(key=lambda x:x[1])
AL = [a[0]for a in AL]
ans =""
for a in AL:
    ans+=str(a)+" "
print(ans)
### BUGGY CODE ###

n = int(input())
p = []
n2 = n
# for i in range(2,int(n2**0.5//1 + 1)):
for i in range(2,n):
  index = 0
  while n2%i == 0:
    index+=1
    n2 = n2//i
  if index != 0:
    p.append(index)
  else:
    continue
count = 0
t = 1

if n == 1:
  print(0)
elif not p:
  print(1)
else:
  for i in range(len(p)):
    while p[i] - t >= 0:
      p[i]-=t
      count+=1
      t+=1
    t = 1
  print(count)

### FIXED CODE ###

n = int(input())
p = []
n2 = n
for i in range(2,int(n2**0.5//1 + 1)):
  index = 0
  while n2%i == 0:
    index+=1
    n2 = n2//i
  if index != 0:
    p.append(index)
  else:
    continue
count = 0
t = 1

if n2 == 1:
  next
else:
  count+=1

if n == 1:
  print(0)
elif not p:
  print(1)
else:
  for i in range(len(p)):
    while p[i] - t >= 0:
      p[i]-=t
      count+=1
      t+=1
    t = 1
  print(count)
### BUGGY CODE ###

from collections import deque

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

inf = 100100100

x -= 1
y -= 1

ans = [0] * n

for i in range(n):
    dist = [inf] * n
    queue = deque()
    queue.append(i)
    dist[i] = 0
    while queue:
        current = queue.popleft()
        d = dist[current]

        if current - 1 >= 0 and dist[current - 1] == inf:
            queue.append(current - 1)
            dist[current - 1] = d + 1
        if current + 1 < n and dist[current + 1] == inf:
            queue.append(current + 1)
            dist[current + 1] = d + 1
        if current == x and dist[y] == inf:
            queue.append(y)
            dist[y] = d + 1
        if current == y and dist[x] == inf:
            queue.append(x)
            dist[x] = d + 1

    for j in range(n):
        ans[dist[j]] += 1

for k in range(1, n):
    print(ans[k] // 2)


### FIXED CODE ###

from collections import deque, Counter

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

inf = 100100100
x -= 1
y -= 1

ans = [0] * n

for i in range(n):
    dist = [inf] * n
    queue = deque()
    queue.append(i)
    dist[i] = 0
    while queue:
        current = queue.popleft()
        d = dist[current]

        if current - 1 >= 0 and dist[current - 1] == inf:
            queue.append(current - 1)
            dist[current - 1] = d + 1
        if current + 1 < n and dist[current + 1] == inf:
            queue.append(current + 1)
            dist[current + 1] = d + 1
        if current == x and dist[y] == inf:
            queue.append(y)
            dist[y] = d + 1
        if current == y and dist[x] == inf:
            queue.append(x)
            dist[x] = d + 1

    for j in range(n):
        ans[dist[j]] += 1

for k in range(1, n):
    print(ans[k] // 2)
### BUGGY CODE ###

from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))

N,M=map(int,input().split())
LRC=[list(map(int,input().split())) for i in range(M)]
LRC.sort()


stack=[[0,-1]]
idle_max=10**18
visited=[idle_max for i in range(N+1)]
visited2=[0 for i in range(N+1)]
visited[1]=0
while stack:
    #print(stack)
    m,a=heappop(stack)
    a=-a
    if a==N:
        print(m)
        break
    if not visited2[a]:
        visited2[a]=1
        for i in range(M):
            l,r,c=LRC[i]
            if l<=a:
                _m=m+c
                if _m<visited[r]:
                    visited[r]=_m
                    heappush(stack,[_m,-r])
            else:
                break
else:
    print(-1)


### FIXED CODE ###

from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))

N,M=map(int,input().split())
LRC=[list(map(int,input().split())) for i in range(M)]
LRC.sort()


stack=[[0,-1,0]]
idle_max=10**18
visited=[idle_max for i in range(N+1)]
visited2=[0 for i in range(N+1)]
visited[1]=0
x=0
while stack:
    #print(stack)
    m,a,p=heappop(stack)
    a=-a
    if a==N:
        print(m)
        break
    if not visited2[a]:
        visited2[a]=1
        for i in range(x,M):
            l,r,c=LRC[i]
            x=i
            if l<=a:
                _m=m+c
                if _m<visited[r]:
                    visited[r]=_m
                    heappush(stack,[_m,-r,a+1])
            else:
                break
else:
    print(-1)
### BUGGY CODE ###

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

S = sum(A)
ans = []
for i in range(N):
    v = S
    for j in range((N-1)//2):
        v -= 2 * A[(2*j+1+i) % N]
    ans.append(v)

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

### FIXED CODE ###

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

S = sum(A)
ans = []

# 山1
v = S
for i in range((N-1)//2):
    v -= 2 * A[(2*i+1) % N]
ans.append(v)

for i in range(1, N):
    ans.append(2*A[i-1] - ans[i-1])

print(" ".join(map(str, ans)))
### BUGGY CODE ###

#!/usr/bin/env python3
#import sys; sys.stdin=open('input_file.txt')
#------------------------------------------
from bisect import bisect_left,bisect_right

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

A.sort()

hi = 10**18+1
lo = -10**18-1

while hi-lo > 1:
    mid = (hi+lo)//2
    under_mid = 0

    for i in range(N):
        if A[i] == 0:
            if mid > 0:
                under_mid += N
        elif A[i] > 0:
            under_mid += bisect_left(A,-(-mid//A[i]))
        else:
            under_mid += N-bisect_right(A,mid//A[i])
        if A[i]*A[i] < mid:
            under_mid -= 1
    under_mid //= 2

    if under_mid < K:
        lo = mid
    else:
        hi = mid

print(lo)


### FIXED CODE ###

#!/usr/bin/env python3
#import sys; sys.stdin=open('input_file.txt')
#------------------------------------------
import numpy as np

N,K = map(int,input().split())
A = np.array(input().split(),dtype=np.int64)

A = np.sort(A)

pos = A[A>0]
neg = A[A<0]
zero = len(A[A==0])

hi = 10**18+1
lo = -10**18-1

while hi-lo > 1:
    mid = (hi+lo)//2
    under_mid = 0

    if mid > 0: under_mid += N*zero
    under_mid += np.searchsorted(A,-(-mid//pos),side='left').sum()
    under_mid += (N-np.searchsorted(A,mid//neg,side='right')).sum()
    under_mid -= np.count_nonzero(A*A < mid)
    under_mid //= 2

    if under_mid < K:
        lo = mid
    else:
        hi = mid

print(lo)
### BUGGY CODE ###

import sys
N = int(input())
L = list(map(int, input().split()))
L.sort()
ret = 0
for i in range(0, N-2):
    for j in range(i+1, N-1):
        ret += len([k for k in L[j+1:] if L[i]+L[j]>k])
print(ret)

### FIXED CODE ###

from bisect import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
ret = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        ret += bisect(L,L[i]+L[j]-1)-j-1
print(ret)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = ['No' for i in range(n - k)]

pre = 1
cur = 1
for i in range(k):
    pre *= a[i]

for i in range(1, n - k + 1):
    cur = (pre // a[i - 1]) * a[i + k-1]
    if cur > pre:
        ans[i - 1] = 'Yes'

    pre = cur


for i in ans:
    print(i)


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = ['No' for i in range(n - k)]


for i in range(n - k):
    if a[i] < a[i + k]:
        ans[i] = 'Yes'


for i in ans:
    print(i)
### BUGGY CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools

s = stdin.readline().rstrip()
n = int(stdin.readline().rstrip())

for i in range(n):
    q = [x for x in stdin.readline().rstrip().split()]

    if len(q) == 1:
        s = ''.join(list(reversed(s)))
    else:
        if q[1] == "1": s = q[2] + s
        if q[1] == "2": s = s + q[2]

print (s)


### FIXED CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque

s = deque(stdin.readline().rstrip())
n = int(stdin.readline().rstrip())

flag = 0

for i in range(n):
    q = [x for x in stdin.readline().rstrip().split()]

    if len(q) == 1:
        flag = 1 - flag
    else:
        if (q[1] == "1" and flag == 0) or (q[1] == "2" and flag == 1):
            s.appendleft(q[2])
        else:
            s.append(q[2])

if flag == 1:
    s = ''.join(s)[::-1]
else:
    s = ''.join(s)
print (s)
### BUGGY CODE ###

N = int(input())
s = []
ans = []
for _ in range(N):
    inp = int(input())
    s.append(inp)
mx = 0
for bit in range(1<<N):
    sums = 0
    for i in range(N):
        mask = 1<<i
        if mask&bit:
            sums += s[i]
        
    if mx < sums:
        if sums%10!=0:
            mx = sums

print(mx)

### FIXED CODE ###

N = int(input())
s = []
for _ in range(N):
    inp = int(input())
    s.append(inp)
s = sorted(s)
sm = sum(s)
if sm%10!=0:
    ans = sm
else:
    for i in s:
        if i%10!=0:
            sm-=i
            break
    ans = sm
    if sm==sum(s):
        ans = 0
print(ans)
### BUGGY CODE ###

def main():
    # 町の数N, 町iの転送先はindexがAi-1の町
    N,K = map(int, input().split())
    A = list(map(int, input().split()))

    # K回移動した時の町番号を出力
    # もし一度出てきた番号が出てきたら記憶している道順リストを使う
    # 最初は道を覚えさせる作業が必要
    now = 0
    history = [0]
    i = 0
    while i<K:
        # まず進む
        now = A[now]-1
        # 道順登録
        if now not in set(history): # ここが線形探索なのが遅い
            history.append(now)
            i+=1
        # 以前出てきてる町ならそこから末尾までを自動で進めてiのカウントも進める
        else:
            start = history.index(now)
            r = start + (K-1-i)%(len(history)-start)
            now = history[r]
            break

    print(now+1)

main()


### FIXED CODE ###

def main():
    # 町の数N, 町iの転送先はindexがAi-1の町
    N,K = map(int, input().split())
    A = list(map(int, input().split()))

    # K回移動した時の町番号を出力
    # もし一度出てきた番号が出てきたら記憶している道順リストを使う
    # 最初は道を覚えさせる作業が必要
    now = 0
    history = [0]
    isVisited = [False for i in range(N)]
    i = 0
    while i<K:
        # まず進む
        now = A[now]-1
        # 道順登録
        #if now not in history:
        if isVisited[now] == False:
            history.append(now)
            isVisited[now] = True
            i+=1
        # 以前出てきてる町ならそこから末尾までを自動で進めてiのカウントも進める
        else:
            start = history.index(now)
            r = start + (K-1-i)%(len(history)-start)
            now = history[r]
            break

    print(now+1)

main()
### BUGGY CODE ###

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

for i in range(N):
    print(A.index(i+1)+1, end=' ')


### FIXED CODE ###

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

A2 = [0]*N

i =1
for a in A:
  A2[a-1] = i
  i+=1

print(*A2)
### BUGGY CODE ###

k, s = map(int, input().split())
count = 0
for a in range(k+1):
  for b in range(k+1):
    for c in range(k+1):
      if a + b + c == s:
        count += 1
      else:
        pass
print(count)

### FIXED CODE ###

k, s = map(int, input().split())
count = 0
for a in range(k+1):
  for b in range(k+1):
      if s-k <= a + b <= s:
        count += 1
      else:
        pass
print(count)
### BUGGY CODE ###

N, M, K = map(int, input().split(' '))
A_ls = [0] + list(map(int, input().split(' ')))
B_ls = [0] + list(map(int, input().split(' ')))

for i in range(1, N + 1):
    A_ls[i] += A_ls[i - 1]
for i in range(1, M + 1):
    B_ls[i] += B_ls[i - 1]

a_cnt, b_cnt, rst = -1, -1, 0
for i in range(N + 1):
    if A_ls[i] > K:
        break
    for j in range(M + 1):
        if A_ls[i] + B_ls[j] > K:
            break
        rst = max(rst, i + j)
print(rst)

### FIXED CODE ###

n, m, k = map(int, input().split(' '))
ans = 0

a_ls = [0] + list(map(int, input().split(' ')))
b_ls = [0] + list(map(int, input().split(' ')))

for i in range(1, n+1):
    a_ls[i] += a_ls[i-1]
for i in range(1, m+1):
    b_ls[i] += b_ls[i-1]

b_cnt = m
for a_cnt in range(0, n+1):
    if a_ls[a_cnt] > k:
        continue
    while a_ls[a_cnt] + b_ls[b_cnt] > k:
        b_cnt -= 1
    ans = max(ans, a_cnt + b_cnt)

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

def main():
    n = int(input())

    ans = 0
    for i in range(n):
        ans += i % n

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())

    ans = 0

    for i in range(1,n):
        ans += i

    print(ans)

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

from functools import reduce
from operator import mul
N = int(input())
A = [int(c) for c in input().split()]
c = reduce(mul,A)
if c>10**18:
  print(-1)
else:
  print(c)


### FIXED CODE ###

from functools import reduce
from operator import mul
N = int(input())
A = [int(c) for c in input().split()]
ans = 1
if 0 in A:
  print(0)
  import sys
  sys.exit()
for c in A:
  ans *= c
  if ans>10**18:
    print(-1)
    break
else:
  print(ans)
### BUGGY CODE ###

N = int(input())
S = list(input())
L = []
for i in range(N):
    tmp = S[:i].count("W")+S[i+1:].count("E"); L.append(tmp)
    if tmp == 1: break
print(min(L))

### FIXED CODE ###

N = int(input())
S = input()
 
oE = S.count("E")
Wo = 0

L = []
for i in range(N):
    if i == 0:
        if S[i] == "E":
            oE -= 1
    else:
        if S[i-1] == "W":
            Wo += 1
        if S[i] == "E":
            oE -= 1
    L.append(Wo + oE)
    if Wo + oE == 0:
        break
print(min(L))
### BUGGY CODE ###

N = int(input())
import numpy as np

a = np.floor(np.sqrt(N))
while True:
  if N%a==0:
    break
  a=a-1
b=N/a
print(int(a+b-2))

### FIXED CODE ###

N = int(input())
import math
def is_prime(n):
  if n == 1: return False
  for k in range(2, int(math.sqrt(n)) + 1):
    if n % k == 0:
      return False
  return True
if is_prime(N):
  print(N-1)
else:
  a = math.floor(math.sqrt(N))
  while True:
    if N%a==0:
      break
    a=a-1
  print(int(a+N/a-2))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N,M = map(int,input().split())
    paylist = [[] for _ in range(M)]
    for _ in range(N):
        a,b = map(int,input().split())
        if M >= a:
            paylist[a-1].append(b)

    work = []
    payment = 0
    for i in range(M):
        work += paylist[i]
        work.sort()
        if work != []:
            payment += work.pop()

    print(payment)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline

def main():
    N,M = map(int,input().split())
    paylist = [[] for _ in range(M)]
    for _ in range(N):
        a,b = map(int,input().split())
        if M >= a:
            heapq.heappush(paylist[a-1],-b)
    work = []
    payment = 0
    for i in range(M):
        for j in paylist[i]:
            heapq.heappush(work,j)
        if work:
            payment += heapq.heappop(work)

    print(-payment)

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

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

dp = [[[0]*(N+2) for _ in range(N+2)] for _ in range(N+2)]

cnt = {1:0, 2:0, 3:0}
for a in a_list:
    cnt[a] += 1

for i in range(N+1):
    for j in range(N+1):
        for k in range(N+1):
            if i==0 and j==0 and k==0:
                continue
            dp[i][j][k] += (N/(i+j+k))
            if k >= 1:
                dp[i][j][k] += dp[i][j][k-1] * (k/(i+j+k))
            if j >= 1:
                dp[i][j][k] += dp[i][j-1][k+1] * (j/(i+j+k))
            if i >= 1:
                dp[i][j][k] += dp[i-1][j+1][k] * (i/(i+j+k))
print(dp[cnt[3]][cnt[2]][cnt[1]])

### FIXED CODE ###

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

dp = [[[0]*(N+2) for _ in range(N+2)] for _ in range(N+2)]

cnt = {1:0, 2:0, 3:0}
for a in a_list:
    cnt[a] += 1

for i in range(N+1):
    for j in range(N+1):
        for k in range(N+1):
            if i==0 and j==0 and k==0:
                continue
            dp[i][j][k] += (N/(i+j+k))
            if k >= 1:
                dp[i][j][k] += dp[i][j][k-1] * (k/(i+j+k))
            if j >= 1:
                dp[i][j][k] += dp[i][j-1][k+1] * (j/(i+j+k))
            if i >= 1:
                dp[i][j][k] += dp[i-1][j+1][k] * (i/(i+j+k))
print(dp[cnt[3]][cnt[2]][cnt[1]])
### BUGGY CODE ###

ans=0
n=int(input())
def tri(x):
	p=""
	while x>0:
		p+=str(x%4)
		x//=4
	return p[::-1]
if n>=50000000:
	ans=4470
	k=51111113
	i=32768
else:
	i=16
	k=357
while k<=n:
	c0=0
	c1=0
	c2=0
	for j in range(len(tri(i))):
		if tri(i)[j]=="1":
			c0+=1
		elif tri(i)[j]=="2":
			c1+=1
		elif tri(i)[j]=="3":
			c2+=1
		else:
			c0=0
			break
	if c0!=0 and c1!=0 and c2!=0:
		ans+=1
	i+=1
	k=0
	for j in range(len(tri(i))):
		k+=(int(tri(i)[-j-1])*2+1)*(10**j)
print(ans)

### FIXED CODE ###

n=input()
p=""
for i in range(len(n)):
	if int(n[i])>7:
		p+="3"*(len(n)-i)
		break
	elif int(n[i])==7:
		p+="3"
	elif int(n[i])==6:
		p+="2"
		p+="3"*(len(n)-i-1)
		break
	elif int(n[i])==5:
		p+="2"
	elif int(n[i])==4:
		p+="1"
		p+="3"*(len(n)-i-1)
		break
	elif int(n[i])==3:
		p+="1"
	else:
		p+="0"
total=0
for i in range(len(n)):
	total+=int(p[-i-1])*(4**i)
def tet(x):
	q=""
	while x!=0:
		q+=str(x%4)
		x//=4
	if len(q)==0:
		q="0"
	return q[::-1]
ans=[]
cnt=0
for i in range(total):
	if tet(i+1).count("0")==0:
		ans.append(tet(i+1))
for i in range(len(ans)):
	if ans[i].count("1") and ans[i].count("2")\
	and ans[i].count("3"):
		cnt+=1
print(cnt)
### BUGGY CODE ###

from itertools import accumulate

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

if n >= m:
    print(0)
    exit()

ans = []
for i in range(m - 1, 0, -1):
    ans.append(x[i] - x[i - 1])

for i in range(n - 1):
    ans.remove(max(ans))
print(sum(ans))


### FIXED CODE ###

from itertools import accumulate

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

if n >= m:
    print(0)
    exit()

ans = []
for i in range(m - 1, 0, -1):
    ans.append(x[i] - x[i - 1])

ans = sorted(ans, reverse=True)
print(sum(ans[n-1:]))