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

def cal_cost(co, h, i, j):
    return co + abs(h[i]-h[j])

n, k = map(int, input().split())
h = [int(i) for i in input().split(" ")]
lis = [0 for i in range(n)]
for i in range(1, n):
    a = min([cal_cost(lis[i-j], h, i-j, i) for j in range(1, k+1) if j<=i])
    lis[i] = a
print(lis[-1])

### FIXED CODE ###

def cal_cost(co, h, i, j):
    return co + abs(h[i]-h[j])

n, k = map(int, input().split())
h = [int(i) for i in input().split(" ")]
lis = [0 for i in range(n)]
for i in range(1, n):
    a = min([cal_cost(lis[i-j], h, i-j, i) for j in range(1, k+1) if j<=i])
    lis[i] = a
print(lis[-1])
### BUGGY CODE ###

# ABC-143-D
#尺取り方でやってみる。
N = int(input())
L = sorted(list(map(int, input().split())))
ans = 0

for a in range(0, N-2):
    for b in range(a+1, N-1):
        tmp = L[a]+L[b]
        i = b + 1
        while i < N and L[i] < tmp:
            ans += 1
            i += 1
                
print(ans)

### FIXED CODE ###

N = int(input())
L_list = list(map(int, input().split()))
sum = 0

L_list.sort()

from bisect import bisect_left

for i in range(N):
    for j in range(i+1, N):
        t = L_list[i]+L_list[j]
        idx = bisect_left(L_list, t)
        sum += max(0, idx-(j+1))
        
print(sum)
### BUGGY CODE ###

n,*a=map(int,open(0).read().split())
for i in range(n):
    temp = a[i]
    a[i] = 0
    print(max(a))
    a[i]=temp


### FIXED CODE ###

n,*a=map(int,open(0).read().split())

b=sorted(a)[::-1]
for i in range(n):
    if a[i]!=b[0]:
        print(b[0])
    else:
        print(b[1])
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline()

#https://www.slideshare.net/chokudai/union-find-49066733
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * self.n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y: return False
    if self.parents[x] > self.parents[y]:
      x, y = y, x
    self.parents[x] += self.parents[y]
    self.parents[y] = x
        
  def issame(self, x, y):
    return self.find(x) == self.find(y)
  
  def get_node_members(self):
    return [[j for j in range(self.n) if self.issame(i, j)] for i in range(self.n)]
  
  def size(self, x):
    return -self.parents[self.find(x)]
  
N = list(map(int, input().split()))
uf = UnionFind(N[0])
results = [0 for i in range(N[0])]
for i in range(N[1]):
  x, y = list(map(int, input().split()))
  x, y = x - 1, y - 1
  results[x] += 1
  results[y] += 1
  uf.union(x, y)
#print(uf.parents)

for i in range(N[2]):
  x, y = list(map(int, input().split()))
  x, y = x - 1, y - 1
  if uf.issame(x, y):
  	results[x] += 1
  	results[y] += 1
  
node_members = uf.get_node_members()
#print(node_members, results)

print(" ".join([str(uf.size(i) - results[i] - 1) for i in range(N[0])]))


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

#https://www.slideshare.net/chokudai/union-find-49066733
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * self.n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y: return False
    if self.parents[x] > self.parents[y]:
      x, y = y, x
    self.parents[x] += self.parents[y]
    self.parents[y] = x
        
  def issame(self, x, y):
    return self.find(x) == self.find(y)
  
  def get_node_members(self):
    return [[j for j in range(self.n) if self.issame(i, j)] for i in range(self.n)]
  
  def size(self, x):
    return -self.parents[self.find(x)]

N = list(map(int, input().split()))
parents = [-1] * N[0]
def find(x):
  if parents[x] < 0:
    return x
  else:
    parents[x] = find(parents[x])
    return parents[x]

def union(x, y):
  x = find(x)
  y = find(y)

  if x == y: return False
  if parents[x] > parents[y]:
    x, y = y, x
  parents[x] += parents[y]
  parents[y] = x
        
def issame(x, y):
  return find(x) == find(y)
  
def size(x):
  return -parents[find(x)]
  

results = [0 for i in range(N[0])]
for i in range(N[1]):
  x, y = list(map(int, input().split()))
  x, y = x - 1, y - 1
  results[x] += 1
  results[y] += 1
  union(x, y)
#print(uf.parents)

for i in range(N[2]):
  x, y = list(map(int, input().split()))
  x, y = x - 1, y - 1
  if issame(x, y):
  	results[x] += 1
  	results[y] += 1
  
#print(node_members, results)

print(" ".join([str(size(i) - results[i] - 1) for i in range(N[0])]))
### BUGGY CODE ###

def calc():
  n=int(input())
  table=[i for i in range(n+1)]
  for i in range(2,n+1):
    if table[i]<i:
      continue
    for j in range(i,n+1,i):
      table[j]=i
  ans=0
  for i in range(1,n+1):
    cnt={}
    tmp=i
    while tmp!=1:
      if table[tmp] in cnt:
        cnt[table[tmp]]+=1
      else:
        cnt[table[tmp]]=1
      tmp//=table[tmp]
    tmp=i
    for val in cnt.values():
      tmp*=val+1
    ans+=tmp
  print(ans)
calc()

### FIXED CODE ###

import sys
input=sys.stdin.readline

def calc():
  n=int(input())
  table=[1]*(n+1)
  check=[False]*(n+1)
  for i in range(2,n+1):
    if check[i]==True:
      continue
    check[i]=True
    for j in range(1,n//i+1):
      check[i*j]=True
      tmp=j
      cnt=1
      while tmp%i==0:
        tmp//=i
        cnt+=1
      table[i*j]*=(i**cnt)*(cnt+1)
  print(sum(table)-1)
calc()
### BUGGY CODE ###

N, X = map(int,input().split())
S = list(map(int,input().split()))
S.sort()
S.reverse()
S.insert(0,0) # 1-indexed
MOD = 10**9+7
dp = [[0]*(10**5+1) for i in range(N+1)]
dp[0][X] = 1
for i in range(N):
    for x in range(10**5+1):
        dp[i+1][x%S[i+1]] += dp[i][x]
        dp[i+1][x] += dp[i][x]*(N-(i+1))
ans = 0
for x in range(10**5+1):
    ans = (ans+(x*dp[N][x]))%MOD
print(ans)

### FIXED CODE ###

N, X = map(int,input().split())
S = list(map(int,input().split()))
S.sort(reverse=True)
S = [0] + S # 1-indexed 
MOD = 10**9+7
dp = [[0]*(10**5+1) for i in range(N+1)]
dp[0][X] = 1
for i in range(N):
    for x in range(10**5+1):
        dp[i+1][x%S[i+1]] += dp[i][x]
        dp[i+1][x] += dp[i][x]*(N-(i+1))
        dp[i+1][x%S[i+1]] %= MOD
        dp[i+1][x] %= MOD
ans = 0
for x in range(10**5+1):
    ans += (x*dp[N][x])%MOD
print(ans%MOD)
### BUGGY CODE ###

N = int(input())
S = [input() for _ in range(N)]
ans = 0
for k in range(N):
    f = True
    for i in range(N):
        for j in range(i + 1, N):
            if S[i][(j + k) % N] != S[j][(i + k) % N]:
                f = False
                break

        if not f:
            break
    if f:
        ans += N
print(ans)

### FIXED CODE ###

N = int(input())
S = [input() for _ in range(N)]
ans = 0
for k in range(N):
    f = True
    for i in range(N):
        for j in range(i + 1, N):
            if S[i][(j + k) % N] != S[j][(i + k) % N]:
                f = False
                break

        if not f:
            break
    if f:
        ans += N
print(ans)
### BUGGY CODE ###

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

MAX = 10**18

res = 1
for a in A:
    res *= a

if res > MAX:
    print("-1")
else:
    print(res)


### FIXED CODE ###

import sys

MAX = 10**18

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

if 0 in A:
    print("0")
else:
    res = 1
    for a in reversed(sorted(A)):
        if a == 1:
            break
        res *= a
        if res > MAX:
            print("-1")
            sys.exit()
    print(res)
### BUGGY CODE ###

s=input()
q=int(input())
m=1
for i in range (q):
    a=list(input().split())
    if a[0]=="1":
        m=m*(-1)
    else:
        if m==1:
            if a[1]=="1":
                s=a[2]+s
            else:
                s=s+a[2]
        else:
            if a[1]=="2":
                s=a[2]+s
            else:
                s=s+a[2]


print(s[::m])

### FIXED CODE ###

from collections import deque

s=input()
q=int(input())
d=deque()
d.append(s)
m=1
for i in range (q):
    a=list(input().split())
    if a[0]=="1":
        m=m*(-1)
    else:
        if m==1:
            if a[1]=="1":
                d.appendleft(a[2])
            else:
                d.append(a[2])
        else:
            if a[1]=="2":
                d.appendleft(a[2])
            else:
                d.append(a[2])
s="".join(d)


print(s[::m])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort()
b.sort()
c.sort()
ans = 0
for i in range(len(b)):
    al = 0
    ar = n-1
    while True:
        if a[-1] < b[i]:
            an = n
            break
        if a[0] >= b[i]:
            an = 0
            break
        am = (al+ar)//2
        if a[am] < b[i]:
            al = am
        else:
            ar = am
        an = al + 1
        if al+1 == ar:
            break
    cl = 0
    cr = n-1
    while True:
        if c[0] > b[i]:
            cn = n
            break
        if c[-1] <= b[i]:
            cn = 0
            break
        cm = (cl+cr)//2
        if c[cm] <= b[i]:
            cl = cm
        else:
            cr = cm
        cn = n - cr
        if cl+1 == cr:
            break
    ans += an*cn
print(ans)

### FIXED CODE ###

N = int(input())

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

A = sorted(A)
B = sorted(B)
C = sorted(C)

A.insert(0, -100000000000)
A.append(1000000000000)
C.insert(0, -100000000000)
C.append(1000000000000)


total= 0
for b in B:
    # search A
    l = 0
    r = N + 1
    while r - l > 1:
        m = (l + r) // 2
        if A[m] < b:
            l = m
        else:
            r = m

    a_count = l

    # search C
    l = 0
    r = N + 1
    while r - l > 1:
        m = (l + r) // 2
        if C[m] > b:
            r = m
        else:
            l = m

    c_count = N + 1 - r

    total += a_count * c_count

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

# -*- coding: utf-8 -*-

import sys
import math

sys.setrecursionlimit(10 ** 6)

input_line = input()
inputs = input_line.split(' ')
N, = [int(s) for s in inputs]

input_line = input()
s = list(input_line)
sl = len(s)

two = {}
for i in range(sl):
    for j in range(i+1,sl):
        if s[i]!=s[j]:
            if s[i]+s[j] in two:
                two[s[i]+s[j]].append((i,j))
            else:
                two[s[i]+s[j]] = [(i, j)]


ans = 0
for k1, v1 in two.items():
    for k2, v2 in two.items():
        if k1[1]==k2[0] and k1[0]!=k2[1]:
            for t1 in v1:
                for t2 in v2:
                    if t1[1]==t2[0] and t1[1]-t1[0]!=t2[1]-t2[0]:
                        ans += 1
print(ans)



### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
import math

sys.setrecursionlimit(10 ** 6)

input_line = input()
inputs = input_line.split(' ')
N, = [int(s) for s in inputs]

input_line = input()
s = list(input_line)
sl = len(s)

r = 0
g = 0
b = 0
for ss in s:
    if ss=='R':
        r += 1
    elif ss=='G':
        g += 1
    else:
        b += 1
ans = r*g*b

num = 0

for i in range(sl):
    for j in range(i+1, sl):
        k = j + (j - i)
        if k<sl:
            if s[i]!=s[j] and s[i]!=s[k] and s[j]!=s[k]:
                num += 1

ans -= num

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

s = input()

lst = [0 for i in range(2019)]
lst[0] = 1

for i in range(len(s)):
    amari = int(s[i:]) % 2019
    lst[amari] += 1

ans = 0
for i in range(2019):
    num = lst[i]
    ans += num * (num-1) // 2

print(ans)

### FIXED CODE ###

s = input()

lst = [0 for i in range(2019)]
lst[0] = 1

amari = 0
tmp = 1
for i in range(1, len(s)+1):
    amari = (amari + int(s[-i])*tmp) % 2019
    lst[amari] += 1
    tmp = (tmp*10) % 2019

ans = 0
for i in range(2019):
    num = lst[i]
    ans += num * (num-1) // 2

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

N = int(input())
A = list(map(int,input().split()))
for i in range(1,N + 1):
	print(A.count(i))

### FIXED CODE ###

N = int(input())
num = [0] * (3 * 10 ** 5)
A = list(map(int,input().split()))
for i in range(len(A)):
	num[A[i]] += 1
for i in range(1,N + 1):
	print(num[i])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,q=map(int,input().split())
STX=[tuple(map(int,input().split())) for i in range(n)]
D=[int(input()) for i in range(q)]
event=[]
for si,ti,xi in STX:
  event.append((si-xi,0,xi))
  event.append((ti-xi,-1,xi))
for di in D:
  event.append((di,1,di))
event.sort()
hq=[]; S=set()
for time, query, number in event:
  if query == 0:
    # print("#F")
    heapq.heappush(hq,number)
    S.add(number)
  elif query == -1:
    # print(S,number)
    S.remove(number)
  else:
    while hq and hq[0] not in S:
      heapq.heappop(hq)
    if not hq:
      print(-1)
    else:
      print(hq[0])




### FIXED CODE ###

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,q=map(int,input().split())
STX=[tuple(map(int,input().split())) for i in range(n)]
D=[int(input()) for i in range(q)]
event=[]
for si,ti,xi in STX:
  event.append((si-xi,0,xi))
  event.append((ti-xi,-1,xi))
for di in D:
  event.append((di,1,di))
event.sort()
hq=[]; S=set()
for time, query, number in event:
  if query == 0:
    heapq.heappush(hq,number)
    S.add(number)
  elif query == -1:
    S.remove(number)
  else:
    while hq and hq[0] not in S:
      heapq.heappop(hq)
    if not hq:
      print(-1)
    else:
      print(hq[0])
### BUGGY CODE ###

from itertools import product
import numpy as np
N = int(input())
lisS = [list(input()) for _ in range(N)]
arS = np.array(lisS)
arExt = np.tile(arS, [2,2])[:-1,:-1]

cnt = 0
for i, j in product(range(N),range(N)):
    ar = arExt[i:i+N, j:j+N]
    cnt += (ar == ar.T).all()

print(cnt)



### FIXED CODE ###

import numpy as np

N = int(input())
lisS = [list(map(ord, list(input()))) for _ in range(N)]
arS = np.array(lisS)
arExt = np.tile(arS, [2,2])[:-1,:-1]

cnt = 0
for i in range(N):
    ar = arExt[i:i+N, 0:N]
    cnt += N * (ar == ar.T).all()

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

from itertools import permutations
N,M,R = map(int,input().split())
r = list(map(int,input().split()))

d = [[float('inf') for _ in range(N)] for _ in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
for i in range(N):
    d[i][i]=0
for k in range(N):
    for i in range(N):
        for j in range(N):
            if d[i][j] > d[i][k]+d[k][j]:
                d[i][j] = d[i][k]+d[k][j]

ans = float('inf')
for seq in permutations(r):
    s = 0
    for j in range(R-1):
        s += d[seq[j]-1][seq[j+1]-1]
    ans = min(ans,s)
print(ans)


### FIXED CODE ###

from itertools import permutations
N,M,R = map(int,input().split())
r = list(map(int,input().split()))

d = [[float('inf') for _ in range(N)] for _ in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
for i in range(N):
    d[i][i]=0
from scipy.sparse import csgraph
d = csgraph.floyd_warshall(d)
ans = float('inf')
for seq in permutations(r):
    s = 0
    for j in range(R-1):
        s += d[seq[j]-1][seq[j+1]-1]
    ans = min(ans,s)
print(int(ans))
### BUGGY CODE ###

from collections import Counter

if __name__ == '__main__':
    s = list(input())
    n = len(s)
    mods = [0] * n
    for i in range(n - 1, -1, -1):
        mods[i] = int(''.join(s[i:])) % 2019
    mods.sort()
    m = Counter(mods)
    ans = 0
    for k, v in m.items():
        if k == 0:
            ans += v
        ans += (v * (v - 1)) // 2
    print(ans)


### FIXED CODE ###

if __name__ == '__main__':

    s = list(input())
    s.reverse()
    n = len(s)
    now = 0
    mods = [0] * 2019
    mods[0] += 1
    ten = 1
    for i in range(n):
        now += ten * int(s[i])
        now %= 2019
        ten *= 10
        ten %= 2019
        mods[now] += 1
    ans = 0
    for i in mods:
        ans += (i * (i - 1)) // 2
    print(ans)
### BUGGY CODE ###

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

ans = 1
for A in Aj:
	ans *= A
if ans > 10**18:
	ans = -1
print(ans)


### FIXED CODE ###

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

ans = 1
ng = False
max = 10**18
for A in Aj:
	if A == 0:
		ans = 0
		break
	if ng or ans*A > max:
		ans = -1
		ng = True
	else:
		ans *= A
print(ans)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
ans = 1
for i in range(n):
    ans *= l[i]
if ans <= 10**18:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()
if l[0] == 0:
    print(0)
    exit()
ans = 1
for i in range(n):
    ans *= l[i]
    if ans > 10**18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

N, W = map(int, input().split())
w = [0]*N
v = [0]*N
for i in range(N):
    w[i], v[i] = map(int, input().split())
vmax = max(v)
dp = [[0]*(N * vmax + 1) for i in range(N + 1)]
dp[0][0] = 0
for j in range(N * vmax):
    dp[0][j + 1] = float("inf")

for i in range(N):
    for j in range(N * vmax + 1):
        if j < v[i]:
            dp[i + 1][j] = dp[i][j]
        else: 
            dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i])

ans = 0
for j in range(N * vmax + 1):
    if dp[N][j] <= W:
        ans = j
print(ans)

### FIXED CODE ###

N, W = map(int, input().split())
w = [0]*N
v = [0]*N
for i in range(N):
    w[i], v[i] = map(int, input().split())
vmax = max(v)
dp = [[0]*(N * vmax + 1) for i in range(N + 1)]
dp[0][0] = 0
for j in range(N * vmax):
    dp[0][j + 1] = float("inf")

for i in range(N):
    for j in range(N * vmax + 1):
        if j < v[i]:
            dp[i + 1][j] = dp[i][j]
        else: 
            dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i])

ans = 0
for j in range(N * vmax + 1):
    if dp[N][j] <= W:
        ans = j
print(ans)
### BUGGY CODE ###

import math

N = int(input())

ans=1
x = math.factorial(N)
for i in range(1, x//2+1):
    if x%i == 0:
        ans += 1
print(ans%(10**9+7))

### FIXED CODE ###

import math

N = int(input())
x = math.factorial(N)

ans = 1
i = 2
while i <= x:
    cnt = 1
    while x%i == 0:
        x //= i
        cnt += 1
    ans *= cnt
    i += 1
                
print(ans%(10**9+7))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=[]
for i in range(1,n+1):
  ans.append(str(a.index(i)+1))
  
print(' '.join(ans))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans={}
for i in range(1,n+1):
  ans[a[i-1]]=i
s=list(ans.keys())
s.sort()
for i in s:
  print(ans[i],end=' ')
  
print()
### BUGGY CODE ###

N = int(input())
P = list(map(int,input().split()))
import collections
c = collections.Counter(P)
t = 0
c1 =c
for i in range(N):
    c1[P[i]]= c1[P[i]]-1
    for j in c1.values():
        t = t+j*(j-1)/2
    print(int(t))
    t = 0
    c1[P[i]]= c1[P[i]]+1   

### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
import collections
c = collections.Counter(P)
t = 0
for j in c.values():
    t = t+j*(j-1)/2
for i in range(N):
    t1 = t -(c[P[i]]-1)
    print(int(t1))
### BUGGY CODE ###

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

res = 0
pn = n
for i in range(10**18):
    if K == 1:
        res = 0
        break
    if abs(pn - K) > pn:
        res = pn
        break
    else:
        pn = n
        n = abs(pn - K)

print (res)

### FIXED CODE ###

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

res = 0
if n % K > abs((n % K) - K):
    res = abs((n % K) - K)
else:
    res = n % K
    
print (res)
### BUGGY CODE ###

from collections import deque
h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())

g = []
for i in range(h):
    g.append(input())

inf = 10**9
dp = [[inf for j in range(w)] for k in range(h)]
dp[x1-1][y1-1] = 0
q = deque([(x1-1, y1-1)])

while q:
    x, y = q.popleft()
    if (x, y) == (x2-1, y2-1):
        break
    c = dp[x][y]
    for i in range(x+1, x+k+1):
        if 0 <= i <= h-1:
            if g[i][y] == "@":
                break
            if dp[i][y] >= c + 1:
                dp[i][y] = c + 1
                q.append((i, y))
            else:
                break
        else:
            break

    for i in range(x-1, x-k-1, -1):
        if 0 <= i <= h-1:
            if g[i][y] == "@":
                break
            if dp[i][y] >= c + 1:
                dp[i][y] = c + 1
                q.append((i, y))
            else:
                break
        else:
            break

    for j in range(y+1, y+k+1):
        if 0 <= j <= w-1:
            if g[x][j] == "@":
                break
            if dp[x][j] >= c + 1:
                dp[x][j] = c + 1
                q.append((x, j))
            else:
                break
        else:
            break

    for j in range(y-1, y-k-1, -1):
        if 0 <= j <= w-1:
            if g[x][j] == "@":
                break
            if dp[x][j] >= c + 1:
                dp[x][j] = c + 1
                q.append((x, j))
            else:
                break
        else:
            break

if dp[x2-1][y2-1] == inf:
    print(-1)
else:
    print(dp[x2-1][y2-1])


### FIXED CODE ###

from collections import deque
h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())

g = []
for i in range(h):
    g.append(input())

inf = 10**9
dp = [[inf for j in range(w)] for k in range(h)]
dp[x1-1][y1-1] = 0
q = deque([(x1-1, y1-1)])

while q:
    x, y = q.popleft()
    if (x, y) == (x2-1, y2-1):
        break
    c = dp[x][y]
    for i in range(x+1, min(x+k+1, h)):
        if g[i][y] == "@":
            break

        if dp[i][y] == inf:
           q.append((i, y))

        if dp[i][y] >= c + 1:
            dp[i][y] = c + 1
        else:
            break


    for i in range(x-1, max(x-k-1, -1), -1):
        if g[i][y] == "@":
            break

        if dp[i][y] == inf:
           q.append((i, y))

        if dp[i][y] >= c + 1:
            dp[i][y] = c + 1
        else:
            break

    for j in range(y+1, min(y+k+1, w)):
        if g[x][j] == "@":
            break

        if dp[x][j] == inf:
            q.append((x, j))

        if dp[x][j] >= c + 1:
            dp[x][j] = c + 1
        else:
            break


    for j in range(y-1, max(y-k-1, -1), -1):
        if g[x][j] == "@":
            break

        if dp[x][j] == inf:
            q.append((x, j))

        if dp[x][j] >= c + 1:
            dp[x][j] = c + 1
        else:
            break

if dp[x2-1][y2-1] == inf:
    print(-1)
else:
    print(dp[x2-1][y2-1])
### BUGGY CODE ###

n,a=int(input()),list(map(int,input().split()));c=[0,0,0];x=[1.0/i for i in range(1,n+1)];dp=[[[-1]*(n+2) for i in range(n+2)]for i in range(n+2)]
for i in a:c[i-1]+=1
for k in range(n+1):
  for j in range(n-k+1):
    for i in range(n-k-j+1):
      if i+j+k>0:dp[i][j][k]=(n+dp[i-1][j][k]*i+dp[i+1][j-1][k]*j+dp[i][j+1][k-1]*k)*x[i+j+k-1]
print(dp[c[0]][c[1]][c[2]]+1)

### FIXED CODE ###

n,a=int(input()),map(int,input().split());c=[0]*3
for i in a:c[i-1]+=1
x,y,z=c;dp=[[[None]*(z+2) for i in range(n-x+2)]for i in range(n+2)];dp[0][0][0]=0
for k in range(z+1):
  for j in range(n-x-k+1):
    for i in range(n-k-j+1):
      if i+j+k:dp[i][j][k]=((dp[i-1][j][k]*i if i else 0)+(dp[i+1][j-1][k]*j if j else 0)+(dp[i][j+1][k-1]*k if k else 0)+n)/(i+j+k)
print(dp[x][y][z])