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

import queue
H,W = [int(i) for i in input().split()]
P = queue.Queue()
check = [[True for _ in range(W)] for _ in range(H)]

for j in range(H):
    a = list(input())
    if '#' in a:
        for i in range(W):
            if a[i] == '#':
                check[j][i] = False
                P.put([j,i])

ans = [[0 for _ in range(W)] for _ in range(H)]
count = 0
while not P.empty():
    hNow,wNow = P.get()
    if hNow-1 >= 0:
        if check[hNow-1][wNow]:
            P.put([hNow-1,wNow])
            ans[hNow-1][wNow] = ans[hNow][wNow]+1
            check[hNow-1][wNow] = False
            count = max(count,ans[hNow-1][wNow])

    if hNow+1 < H:
        if check[hNow+1][wNow]:
            P.put([hNow+1,wNow])
            ans[hNow+1][wNow] = ans[hNow][wNow]+1
            check[hNow+1][wNow] = False
            count = max(count,ans[hNow+1][wNow])

    if wNow-1 >= 0:
        if check[hNow][wNow-1]:
            P.put([hNow,wNow-1])
            ans[hNow][wNow-1] = ans[hNow][wNow]+1
            check[hNow][wNow-1] = False
            count = max(count,ans[hNow][wNow-1])

    if wNow+1 < W:
        if check[hNow][wNow+1]:
            P.put([hNow,wNow+1])
            ans[hNow][wNow+1] = ans[hNow][wNow]+1
            check[hNow][wNow+1] = False
            count = max(count,ans[hNow][wNow+1])

print(count)


### FIXED CODE ###

from collections import deque

H,W = [int(i) for i in input().split()]
l = [list(input()) for _ in range(H)]
ans = [[-1]*W for _ in range(H)]
q = deque()

for i in range(H):
    for j in range(W):
        if l[i][j] == '#':
            q.append([i,j])
            ans[i][j] = 0

t = 0
while q:
    i,j = q.popleft()
    for next_i, next_j in [[i+1,j], [i-1,j], [i,j+1], [i,j-1]]:
        if 0 <= next_i < H and 0 <= next_j < W:
            if ans[next_i][next_j] == -1 and l[next_i][next_j] == '.':
                ans[next_i][next_j] = ans[i][j] + 1
                t = max(t, ans[next_i][next_j])
                q.append([next_i,next_j])

print(t)
### BUGGY CODE ###

from collections import deque, defaultdict

def bfs(graph, start):
    queue = deque([start])
    visited = set()
    distance = defaultdict(int)
    distance[start] = 0
    while queue:
        current_vertex = queue.popleft()
        visited.add(current_vertex)
        for v in graph[current_vertex]:
            if v not in visited and v not in queue:
                queue.append(v)
                distance[v] = distance[current_vertex] + 1
    return distance

N, M = map(int, input().split())
paths = [tuple(map(int, input().split())) for _ in range(M)]

graph = defaultdict(set)
for A, B in paths:
    graph[A].add(B)
    graph[B].add(A)

distance = bfs(graph, 1)

ans = 'Yes'
ans_list = []
for i in range(2, N+1):

    found = False
    for j in graph[i]:
        if distance[j] == distance[i] - 1:
            ans_list.append(j)
            found = True
            break
    if not found:
        ans = 'No'

if ans == 'No':
    print(ans)
else:
    print(ans)
    for x in ans_list:
        print(x)


### FIXED CODE ###

from collections import deque, defaultdict


def bfs(graph, start):

    queue = deque([start])
    visited = set()
    visited.add(start)
    parent = defaultdict(int)
    parent[start] = 0
    while queue:
        current_vertex = queue.popleft()
        for v in graph[current_vertex]:
            if v not in visited:
                queue.append(v)
                visited.add(v)
                parent[v] = current_vertex
    return parent

N, M = map(int, input().split())
paths = [tuple(map(int, input().split())) for _ in range(M)]

graph = defaultdict(set)
for A, B in paths:
    graph[A].add(B)
    graph[B].add(A)

parent = bfs(graph, 1)

print('Yes')
for k, v in sorted(parent.items()):
    if v != 0:
        print(v)
### BUGGY CODE ###

import math
a, b, n = [int(a) for a in input().split()]

def calc(a, b, x):
    # print(a, b, x, math.floor(a*x/b), math.floor(x/b))
    return math.floor(a*x/b) - a * math.floor(x/b)
    
ans = -1
for x in range(1, n+1):
    r = calc(a, b, x)
    if r > ans:
        ans = r
        # print(x)
print(ans)

### FIXED CODE ###

import math
a, b, n = [int(a) for a in input().split()]

def calc(a, b, x):
    # print(a, b, x, math.floor(a*x/b), math.floor(x/b))
    return math.floor(a*x/b) - a * math.floor(x/b)
    
ans = 0
max_x = b
if b > n:
    max_x = n
for x in range(1, max_x+1)[::-1]:
    r = calc(a, b, x)
    if r > ans:
        ans = r
        break

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

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

sum = 1
ans = 0
for x in A:
  sum *= x
  if sum > 1000000000000000000:
    ans = -1
  if sum == 0:
    ans = 0

if ans < 0:
  print(ans)
else:
  print(sum)

### FIXED CODE ###

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

sum = 1
if 0 in A:
  sum = 0
ans = 0
for x in A:
  sum *= x
  if sum > 1000000000000000000:
    ans = -1
    break
  if sum == 0:
    ans = 0
    break

if ans < 0:
  print(ans)
else:
  print(sum)
### BUGGY CODE ###

import heapq
t = int(input())
for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    # x to lowest coin
    cheapest = dict()
    # (coin, x)
    search = [(d, 1)]
    first = True

    while 1:
        coin, x = heapq.heappop(search)

        if (x > 1 or first) and x not in cheapest:
            first = False
            if x == n:
                print(coin)
                break
            cheapest[x] = coin

            heapq.heappush(search, (coin + a, 2 * x))
            heapq.heappush(search, (coin + b, 3 * x))
            heapq.heappush(search, (coin + c, 5 * x))
            heapq.heappush(search, (coin + d, x + 1))
            if x - 1 > 1:
                heapq.heappush(search, (coin + d, x - 1))

### FIXED CODE ###

t = int(input())

import sys
sys.setrecursionlimit(10 ** 6)

def calc(x):
    if x in dp:
        return dp[x]
    
    divs = [5, 3, 2]
    costs = [c, b, a]
    res = d * x
    for div, cost in zip(divs, costs):
        dived = x//div
        res = min(res, calc(dived) + cost + abs(x-dived*div) * d)
        if x > div:
            dived = x//div+1
            res = min(res, calc(dived) + cost + abs(x-dived*div) * d)
    dp[x] = res
    return res

for _ in range(t):
    n, a, b, c, d = list(map(int, input().split()))
    dp = {}
    dp[0] = 0
    dp[1] = d
    print(calc(n))
### BUGGY CODE ###

def f(n, m):
    to1 = {}
    for _ in range(m):
        u, v = map(int, input().split())
        to1.setdefault(u, [])
        to1[u] += [v]
    s, t = map(int, input().split())

    vst1 = set()
    cnt = 0
    to = {}

    for i in range(1, n + 1):
        ss = set([i])
        for _ in range(3):
            nss = []
            for ii in ss:
                if ii not in to1: continue
                nss+=to1[ii]
            ss = set(nss)
        to[i] = list(ss)

#    print(to)

    ss = set([s])
    while 1:
        cnt += 1
#        print(ss)
        nss=set()
        for i in ss:
            if i not in to: continue
            for j in to[i]:
                nss.add(j)
        ss = nss
#        print(ss)
        if t in ss:
            print(cnt)
            exit()
        if ss <= vst1:
            print(-1)
            exit()
        vst1 |= ss

n, m = map(int, input().split())
f(n, m)


### FIXED CODE ###

def f(n, m):
    to = {}
    for _ in range(m):
        u, v = map(int, input().split())
        to.setdefault(u, [])
        to[u] += [v]
    s, t = map(int, input().split())
    vst = [[False] * 3 for _ in range(n + 1)]
    a = [s]
    vst[s][0] = True
    cnt = 0
    while a:
        b = []
        cnt += 1
        j = cnt % 3
        for ak in a:
            if ak not in to: continue
            for i in to[ak]:
                if vst[i][j]: continue
                vst[i][j] = True
                b.append(i)
            if vst[t][0]:
                print(cnt // 3)
                exit()
        a = b
    print(-1)

n, m = map(int, input().split())
f(n, m)
### BUGGY CODE ###

n=int(input())
s=input()
cnt=0
r=s.count("R")
g=s.count("G")
b=s.count("B")

ans=r*g*b

for i in range(n):
    for j in range(n):
        if s[i]!=s[j]:
            if j-i<=n//2:
                if i<j:
                    d=j-i
                    k=j+d
                    if k<n:
                        if s[k]!=s[j] and s[i]!=s[k]:
                            ans-=1

                    else:
                        break
                        

      
print(ans)
        

### FIXED CODE ###

n=int(input())
s=input()
cnt=0
r=s.count("R")
g=s.count("G")
b=s.count("B")

ans=r*g*b

for i in range(n):
    for j in range(n):
        if s[i]!=s[j]:
            if j-i<=n//2:
                if i<j:
                    d=j-i
                    k=j+d
                    if k<n:
                        if s[k]!=s[j] and s[i]!=s[k]:
                            ans-=1
                        

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

#n, m, q = map(int, input().split())
#List = list(map(int, input().split()))
#req = [list(map(int, input().split())) for _ in range(q)]
#t = t[:-1]
#print(ans[j], end = "") 改行無しで出力
#[0]*n
n = int(input())
a = list(map(int, input().split()))
q = int(input())
req = [list(map(int, input().split())) for _ in range(q)]
count = [0]*100000
sum = 0
ans = [0]*q

for i in range(100000):
    count[i] = a.count(i+1)

for j in a:
    sum += j

for k in range(q):
    diff = req[k][1] - req[k][0]
    diff = diff * count[req[k][0] - 1]
    count[req[k][1] - 1] += count[req[k][0] - 1]
    count[req[k][0] - 1] = 0
    sum += diff
    ans[k] = sum

for l in range(q):
    print(ans[l])


### FIXED CODE ###

#n, m, q = map(int, input().split())
#List = list(map(int, input().split()))
#req = [list(map(int, input().split())) for _ in range(q)]
#t = t[:-1]
#print(ans[j], end = "") 改行無しで出力
#[0]*n
n = int(input())
a = list(map(int, input().split()))
q = int(input())
req = [list(map(int, input().split())) for _ in range(q)]
count = [0]*100001
sum = sum(a)

for i in a:
    count[i] += 1

for k in range(q):
    sum += (req[k][1] - req[k][0]) * count[req[k][0]]
    count[req[k][1]] += count[req[k][0]]
    count[req[k][0]] = 0
    print(sum)
### BUGGY CODE ###

N, M = map(int, input().split())
v = [[] for _ in range(N)]
for i in range(M) :
    s, t = map(int, input().split())
    v[s-1].append(t-1)

# 削除しないでdp
dp = [0] * N
for i in range(N - 1, -1, -1) :
    if len(v[i]) == 0 :
        continue
   
    s = [dp[j] for j in v[i]]
    dp[i] = 1 + sum(s) / len(v[i])
    
ret = dp[0]

# 削除してdp
for i in range(N) :
    if len(v[i]) == 0 :
        continue
        
    for j in range(i, -1, -1) :
        if len(v[j]) == 0 :
            continue
            
        s = [dp[k] for k in v[j]]
        if j == i :
            if len(v[j]) != 1 :
                dp[j] = 1 + (sum(s) - max(s)) / (len(v[j]) - 1)
        else :
            dp[j] = 1 + sum(s) / len(v[j])
    ret = min(ret, dp[0])
print(ret)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
v = [[] for _ in range(N)]
for i in range(M) :
    s, t = map(int, input().split())
    v[s-1].append(t-1)

# 削除しないでdp
dp = [0] * N
for i in range(N - 1, -1, -1) :
    if len(v[i]) == 0 :
        continue
    
    for j in v[i] :
        dp[i] += dp[j]
    dp[i] = 1 + dp[i] / len(v[i])
    
ret = dp[0]
# 削除してdp
for i in range(N - 1) :
    if len(v[i]) <= 1 :
        continue
        
    dp[i] = 0
    M = -1
    for j in v[i] :
        dp[i] += dp[j]
        M = max(M, dp[j])
    dp[i] = 1 + (dp[i] - M) / (len(v[i]) - 1)
    
    for j in range(i - 1, -1, -1) :
        if len(v[j]) == 0 :
            continue
            
        dp[j] = 0
        for k in v[j] :
            dp[j] += dp[k]
        dp[j] = 1 + dp[j] / len(v[j])
    
    ret = min(ret, dp[0])

print(ret)
### BUGGY CODE ###

import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
#import numpy as np

#from math import gcd
from fractions import gcd

def main():
	n=int(input())
	A=list(map(int,input().split()))
	B=set(A)
	A=list(A)
	A.sort(reverse=True)
	a=1
	for i in A:
		a=a*i//gcd(a, i)
	ans=0
	for i in A:
		ans+=(a//i)
		ans%=mod
	print(ans)
	
	
	
	
	
	


if __name__ == "__main__":
	main()


### FIXED CODE ###

import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
#import numpy as np

#from math import gcd
from fractions import gcd

def main():
	n=int(input())
	A=list(map(int,input().split()))
	B=set(A)
	A=list(A)
	A.sort(reverse=True)
	a=1
	ans=0
	for i in A:
		g=gcd(a, i)
		ans *=i//g
		a=a*i//gcd(a, i)
		ans+=a//i
	
	
	
	
	print(ans%mod)
	
	
	
	
	
	


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

import sys
input = sys.stdin.readline
def min_cost_flow(E, s, t, f):
    INF = 1<<100
    NN = T+1
    G = [[] for _ in range(NN)]
    for a, b, cap, c in E:
        G[a].append([b, cap, c, len(G[b])])
        G[b].append([a, 0, -c, len(G[a])-1])
    prevv = [-1] * NN
    preve = [-1] * NN
    res = 0
    while f > 0:
        dist = [INF] * NN
        dist[s] = 0
        update = 1
        while update:
            update = 0
            for v in range(NN):
                if dist[v] == INF: continue
                for i, (b, _cap, c, r) in enumerate(G[v]):
                    if _cap > 0 and dist[b] > dist[v] + c:
                        dist[b] = dist[v] + c
                        prevv[b] = v
                        preve[b] = i
                        update = 1
        
        if dist[t] == INF:
            return -1

        d = f
        v = t
        while v != s:
            d = min(d, G[prevv[v]][preve[v]][1])
            v = prevv[v]
        f -= d
        res += d * dist[t]
        v = t
        while v != s:
            G[prevv[v]][preve[v]][1] -= d
            G[v][G[prevv[v]][preve[v]][3]][1] += d
            v = prevv[v]
    
    return res

E = []
inf = 1 << 17
N, H, W = map(int, input().split())
S, T = H+W+N, H+W+N+1
for i in range(H):
    E.append((S, i, 1, 0))
for i in range(W):
    E.append((S, H+i, 1, 0))
for i in range(N):
    r, c, a = map(int, input().split())
    r -= 1
    c -= 1
    E.append((r, H+W+i, 1, 0))
    E.append((H+c, H+W+i, 1, 0))
    E.append((H+W+i, T, 1, inf - a))

E.append((S, T, H+W, inf))
print(inf * (H+W) - min_cost_flow(E, S, T, H+W))

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def par(a):
    if P[a] < 0: return a
    t = par(P[a])
    P[a] = t
    return t
def unite(a, b):
    if par(a) == par(b): return 0
    C[par(a)], C[par(b)] = C[par(a)] + C[par(b)], C[par(a)] + C[par(b)]
    if P[par(b)] == P[par(a)]:
        P[par(b)] = par(a)
        P[par(a)] -= 1
    elif P[par(b)] > P[par(a)]:
        P[par(b)] = par(a)
    else:
        P[par(a)] = par(b)
N, H, W = map(int, input().split())
P = [-1 for i in range(H+W)]
C = [1] * (H+W)
X = []
for _ in range(N):
    r, c, a = map(int, input().split())
    X.append((a, r-1, c+H-1))
X = sorted(X)
ans = 0
while X:
    a, r, c = X.pop()
    unite(r, c)
    if C[par(r)]:
        ans += a
        C[par(r)] -= 1
print(ans)
### BUGGY CODE ###

from fractions import gcd
mod = 10**9+7
n = int(input())
A = list(map(int, input().split()))
m = A[0]
for i in range(1, n):
  m = A[i] // gcd(m, A[i]) * m
ans = 0
for i in A:
  ans += m//i
print(ans%mod)

### FIXED CODE ###

from fractions import gcd
mod = pow(10, 9)+7
n = int(input())
A = list(map(int, input().split()))
m = A[0]
for i in range(1, n):
  m = m // gcd(m, A[i]) * A[i]
ans = 0
for i in A:
  ans += m//i
print(ans%mod)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
H,W=map(int,input().split())
S=[[d for d in input()] for i in range(H)]
ans=[[0 for j in range(W)] for i in range(H)]
t=0
for i in range(H):
 p=0
 for j in range(W):
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
for i in range(H):
 p=0
 for j in range(W)[::-1]:
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
for j in range(W):
 p=0
 for i in range(H):
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
for j in range(W):
 p=0
 for i in range(H)[::-1]:
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
  t=max(t,ans[i][j])
print(t-3)


### FIXED CODE ###

import sys
input = sys.stdin.readline
H,W=map(int,input().split())
S=[[d for d in input()] for i in range(H)]
ans=[[0 for j in range(W)] for i in range(H)]
t=0
for i in range(H):
 p=0
 for j in range(W):
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
for i in range(H):
 p=0
 for j in range(W)[::-1]:
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
for j in range(W):
 p=0
 for i in range(H):
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
for j in range(W):
 p=0
 for i in range(H)[::-1]:
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
  t=max(t,ans[i][j])
print(t-3)
### BUGGY CODE ###

a, b,n = list(map(int, input().split()))
res = 0
for x in range(1, n+1):
    if  a *(x//b) != 0:
        break
    if res < (a*x)//b - a *(x//b):
        res = (a*x)//b - a *(x//b)

print(res)

### FIXED CODE ###

a, b,n = list(map(int, input().split()))
if b > n:
    print((a*n)//b - a *(n//b))
elif b <= n:
    print((a*(b-1))//b )
### BUGGY CODE ###

import sys

input = sys.stdin.readline


def main():
    H, N = map(int, input().split())
    AB = [None] * N
    for i in range(N):
        AB[i] = tuple(map(int, input().split()))

    INF = 10 ** 18
    dp = [INF] * (H + 1)
    dp[0] = 0
    for A, B in AB:
        for d in range(H + 1):
            if d < A:
                dp[d] = min(dp[d], B)
            else:
                dp[d] = min(dp[d], dp[d - A] + B)

    ans = dp[-1]
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline

INF = float("inf")


def main():
    H, N = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    dp = [INF] * (H + max(A))
    dp[0] = 0
    for h in range(H):
        for a, b in zip(A, B):
            if dp[h]+b < dp[h+a]:
                dp[h+a] = dp[h]+b
    ans = min(dp[H:])
    print(ans)


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

def resolve():
    N = int(input())
    S = list(input())

    ans = 0

    for i in range(N):
        for ii in range(i, N):
            for iii in range(ii, N):
                if ((ii - i) == (iii - ii)):
                    continue
                if (len(set([S[i], S[ii], S[iii]])) == 3):
                    ans += 1

    print(ans)


resolve()

### FIXED CODE ###

from collections import Counter


def resolve():
    n = int(input())
    s = input()
    cnt = Counter(s)
    ans = cnt['R'] * cnt['G'] * cnt['B']

    for i in range(n - 1):
        for j in range(i + 1, n):
            ken = j * 2 - i
            if (ken >= n):
                continue
            if (s[i] != s[j] and s[j] != s[ken] and s[i] != s[ken]):
                ans -= 1

    print(ans)

resolve()
### BUGGY CODE ###

A,B,K = map(int,input().split())

for i in range(K):
  if A > 0:
    A -= 1
    continue
  
  if A ==0 and B > 0:
    B -= 1
    continue
  
  else:
    continue
    
print(A,B)
  
 

### FIXED CODE ###

a, b, k = [int(x) for x in input().split(" ")]

if a + b == k or a + b < k or (a == 0 and b == 0):
  print(0, 0)
elif a + b > k and a >= k:
  print(a-k, b)
elif a + b > k and a < k:
  print(0, a+b-k)
### BUGGY CODE ###

n=int(input())
for i in range(3500):
    for j in range(3498):
        try:
            a=i+1 ; b=j+1
            t=(a*b*n)/(4*a*b-b*n-a*n)
            if t>0 and t%1<0.0000000001:
                print(a,b,int(t))
                exit()
        except ZeroDivisionError:
            continue

### FIXED CODE ###

import math
n=int(input())
for a in range(math.ceil(n/4),3501):
    q=4/n-1/a
    if q==0:continue
    for b in range(math.ceil(q),3501):
        if not 4*a*b==b*n+a*n:
            t=a*b*n/(4*a*b-b*n-a*n)
            if t>0 and t%1==0:
                print(a,b,int(t))
                exit()
### BUGGY CODE ###

N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))
T.insert(0, 0)
V.insert(0, 0)
V.append(0)

Z = [0] * (len(T))
for i in range(len(T)-1):
    Z[i+1] = Z[i] + T[i+1]

K = [[0, 0]]
for i in range(N):
    K.append([Z[i], Z[i+1]])
K.append([sum(T), sum(T)])

ans = 0
time_table = [0.5*i for i in range(2*sum(T)+1)]

for time in time_table:
    speed = 10**5
    for k, v in zip(K, V):
        if time <= k[0]:
            tmp = v + (k[0]-time)
        elif k[0] <= time <= k[1]:
            tmp = v
        elif k[1] <= time:
            tmp = v + (time - k[1])

        speed = min(speed, tmp)
    ans += 0.5 * speed

print(ans)

### FIXED CODE ###

"""
prd_xxx 様のコードを参考にさせていただきました。感謝です...！
https://beta.atcoder.jp/contests/abc076/submissions/1724160
"""

N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))

maxv = [0]
# グラフを整える準備
for v, t in zip(V, T):
    # 転換地点では低い方に合わせる
    maxv[-1] = min(maxv[-1], v)
    for ti in range(t * 2):
        maxv.append(v)

T = len(maxv)
# 前からグラフを整える
for i in range(T - 1):
    maxv[i + 1] = min(maxv[i+1], maxv[i] + 0.5)

maxv[-1] = 0
# 後ろからグラフを整える
for i in reversed(range(T-1)):
    maxv[i] = min(maxv[i], maxv[i + 1] + 0.5)

ans = 0
# 台形計算
for i in range(T-1):
    ans += (maxv[i] + maxv[i+1]) * 0.25
print(ans)
### BUGGY CODE ###

n = int(input())
v = list(map(int, input().split()))
v_odd = v[0::2]
v_even = v[1::2]
chars_odd = list(set(v_odd))
chars_even = list(set(v_even))
odd_cnt = [[0, '_']]
for char in chars_odd:
    cnt_odd = v_odd.count(char)
    odd_cnt.append([cnt_odd, char])
odd_cnt.sort(reverse=True)
even_cnt = [[0, '_']]
for char in chars_even:
    cnt_even = v_even.count(char)
    even_cnt.append([cnt_even, char])
even_cnt.sort(reverse=True)
if odd_cnt[0][1] == even_cnt[0][1]:
    res = max(odd_cnt[0][0] + even_cnt[1][0], odd_cnt[1][0] + even_cnt[0][0])
else:
    res = odd_cnt[0][0] + even_cnt[0][0]
print(n - res)

### FIXED CODE ###

n = int(input())
v = list(map(int, input().split()))
v_odd = v[0::2]
v_even = v[1::2]
chars_odd = list(set(v_odd))
cnt_odd = dict()
for char in chars_odd:
    cnt_odd[char] = 0
for char in v_odd:
    cnt_odd[char] += 1
odd_cnt = sorted(cnt_odd.items(), key=lambda x:x[1], reverse=True)
odd_cnt.append(('_', 0))

chars_even = list(set(v_even))
cnt_even = dict()
for char in chars_even:
    cnt_even[char] = 0
for char in v_even:
    cnt_even[char] += 1
even_cnt = sorted(cnt_even.items(), key=lambda x:x[1], reverse=True)
even_cnt.append(('_', 0))

if odd_cnt[0][0] == even_cnt[0][0]:
    res = max(odd_cnt[0][1] + even_cnt[1][1], odd_cnt[1][1] + even_cnt[0][1])
else:
    res = odd_cnt[0][1] + even_cnt[0][1]
print(n - res)
### BUGGY CODE ###

from fractions import gcd
N, M = map(int, input().split())
S = input()
T = input()

def lcm(N, M):
    return N * M // gcd(N, M)

L = lcm(N, M)
n = L // N
m = L // M

# print(N, M, L, n, m, S, T)

ans = True
for i in range(L):
    if i % n == 0 and i % m == 0:
        s = S[i // n]
        t = T[i // m]
        if s != t:
            ans = False
            break

if ans:
    print(L)
else:
    print(-1)


### FIXED CODE ###

from fractions import gcd
N, M = map(int, input().split())
S = input()
T = input()

def lcm(N, M):
    return N * M // gcd(N, M)

L = lcm(N, M)
n = L // N
m = L // M
C = n * m

# print(N, M, L, n, m, S, T)

ans = True
for i in range(0, L, C):
    s = S[i // n]
    t = T[i // m]
    if s != t:
        ans = False
        break

if ans:
    print(L)
else:
    print(-1)