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

class DisjointSet():
    def __init__(self):
        self.parent = None


def ancestor(elems, x):
    s = elems[x]
    while s.parent is not None:
        s = s.parent
    return s


def unite(elems, x, y):
    ax = ancestor(elems, x)
    ay = ancestor(elems, y)
    if ax is not ay:
        parent = DisjointSet()
        ax.parent = ay.parent = parent


def same(elems, x, y):
    return ancestor(elems, x) is ancestor(elems, y)


def main():
    n, q = [int(x) for x in input().split()]
    elems = [DisjointSet() for _ in range(n)]

    for _ in range(q):
        com, x, y = [int(x) for x in input().split()]
        if com == 0:
            unite(elems, x, y)
        else:
            print(1 if same(elems, x, y) else 0)


if __name__ == '__main__':
    main()



### FIXED CODE ###

class DisjointSetElement():
    def __init__(self, x):
        self.parent = x
        self.rank = 0


class DisjointSet():
    def __init__(self, n):
        self.elems = [DisjointSetElement(n) for n in range(n)]

    def _find_set(self, x):
        if x != self.elems[x].parent:
            self.elems[x].parent = self._find_set(self.elems[x].parent)
        return self.elems[x].parent

    def same(self, x, y):
        return self._find_set(x) == self._find_set(y)

    def _link(self, x, y):
        if self.elems[x].rank > self.elems[y].rank:
            self.elems[y].parent = x
        else:
            self.elems[x].parent = y
            if self.elems[x].rank == self.elems[y].rank:
                self.elems[y].rank += 1

    def unite(self, x, y):
        self._link(self._find_set(x), self._find_set(y))


def main():
    n, q = [int(x) for x in input().split()]
    ds = DisjointSet(n)

    for _ in range(q):
        com, x, y = [int(x) for x in input().split()]
        if com == 0:
            ds.unite(x, y)
        else:
            print(1 if ds.same(x, y) else 0)


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

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
  
K = int(input())
A = B = C = [i for i in range(1, K+1)]
cnt = sum([gcd(gcd(a,b),c) for a in A for b in B for c in C])   
print(cnt)

### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
  
K = int(input())
A = B = C = [i for i in range(1, K+1)]

L = [gcd(a,b) for a in A for b in B]

cnt = sum([gcd(l,c) for l in L for c in C])   
print(cnt)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
from collections import Counter
n,m=map(int,input().split())
A,B=[],[]
for _ in range(n):
    A.append(tuple(map(lambda x:int(x)-1,input().split())))
    B.append(A[-1][0])
delete=[False]*m
ans=n
for _ in range(m-1):
    c=Counter(B)
    sport,num=c.most_common()[0]
    ans=min(ans,num)
    delete[sport]=True
    for i in range(n):
        idx=0
        while delete[A[i][idx]]:
            idx+=1
        B[i]=A[i][idx]
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline
from collections import Counter
n,m=map(int,input().split())
A,B=[],[]
for _ in range(n):
    A.append(tuple(map(lambda x:int(x)-1,input().split())))
    B.append(A[-1][0])
delete=[False]*m
ans=n
idx=[0]*n
for _ in range(m-1):
    c=Counter(B)
    sport,num=c.most_common()[0]
    ans=min(ans,num)
    delete[sport]=True
    for i in range(n):
        while delete[A[i][idx[i]]]:
            idx[i]+=1
        B[i]=A[i][idx[i]]
print(ans)
### BUGGY CODE ###

import fractions

from sys import stdin


def main():
    n = int(stdin.readline())
    a = list(map(int, stdin.readline().split()))
    sa = set(a)

    lcm = 1

    for ai in sa:
        lcm = (ai * lcm) // fractions.gcd(ai, lcm)

    ans = 0

    for ai in a:
        ans += lcm // ai
        ans %= 10 ** 9 + 7

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import fractions

from sys import stdin


def main():
    n = int(stdin.readline())
    a = list(map(int, stdin.readline().split()))
    sa = set(a)

    lcm = 1

    for ai in sa:
        lcm = (ai * lcm) // fractions.gcd(ai, lcm)

    ans = 0

    for ai in a:
        ans += lcm // ai
    ans %= 10 ** 9 + 7

    print(ans)


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

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

n = len(ab)

for i in range(n):
    if ab[i][1] != N:
        continue
    for j in range(n):
       if ab[i][0] == ab[j][1] and ab[j][0] == 1:
           print('POSSIBLE')
           exit()
print('IMPOSSIBLE')

### FIXED CODE ###

N,M = map(int,input().split())

s = []
g = []
for i in range(M):
    a,b = map(int,input().split())
    if a == 1:
        s.append(b)
    elif b == N:
        g.append(a)
    
ans = set(s) & set(g)

if len(ans) >= 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

# input
x, y, z, k = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]

import heapq


a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

index_hstr = []
deliciouses = []
# priority queue
pq = []
heapq.heappush(pq, (-a[0] - b[0] - c[0], 0, 0, 0))
index_hstr.append((0, 0, 0))

for t in range(k):
    deli, i, j, k = heapq.heappop(pq)
    if i+1<x and (i+1, j, k) not in index_hstr:
        heapq.heappush(pq, (-a[i+1] - b[j] - c[k], i+1, j, k))
        index_hstr.append((i+1, j, k))
    if j+1<y and (i, j+1, k) not in index_hstr:
        heapq.heappush(pq, (-a[i] - b[j+1] - c[k], i, j+1, k))
        index_hstr.append((i, j+1, k))
    if k+1<z and (i, j, k+1) not in index_hstr:
        heapq.heappush(pq, (-a[i] - b[j] - c[k+1], i, j, k+1))
        index_hstr.append((i, j, k+1))
    deliciouses.append(-deli)


print('\n'.join(str(i) for i in deliciouses))


### FIXED CODE ###

# input
x, y, z, k = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

ab = []
ab.extend([i+j for j in b for i in a])
ab.sort(reverse=True)

abc = []
abc.extend([i+j for j in ab[:k] for i in c])
abc.sort(reverse=True)

print('\n'.join(str(i) for i in abc[:k]))
### BUGGY CODE ###

n, _ = map(int, input().split())
CST = {} # {c:[[s,t],...]}
for i in range(n):
    s, t, c = map(int, input().split())
    if c in CST: CST[c] += [[s,t]]
    else: CST[c] = [[s,t]]
mx_t = 200002
R = [0]*mx_t
for c, ST in CST.items():
    TZ = [0]*mx_t
    for s,t in ST:
        TZ[2*s - 1] += 1
        TZ[2*t] -= 1
    for i in range(mx_t - 1):
        TZ[i+1] += TZ[i]
        if TZ[i+1] > 0: R[i+1] += 1
print(max(R))


### FIXED CODE ###

N, C = map(int, input().split())
STC = [[*map(int, input().split())] for _ in range(N)]
mx_t = 200002
R = [0]*mx_t
for cc in range(1, C+1):
    TZ = [0]*mx_t
    for s,t,c in STC:
        if c == cc:
            TZ[2*s - 1] += 1
            TZ[2*t] -= 1
    for i in range(mx_t - 1):
        TZ[i+1] += TZ[i]
        if TZ[i+1] > 0: R[i+1] += 1
print(max(R))
### BUGGY CODE ###

N = int(input())
S = []
for _ in range(N):
  s = list(str(input()))
  dic = dict()
  for i in s:
    if dic.get(i) is None:
      dic[i] = 1
    else:
      dic[i] += 1
  S.append(dic)

ans = 0
for i in range(N-1):
  for j in range(i+1, N):
    if S[i] == S[j]:
      ans += 1
     
print(ans)

### FIXED CODE ###

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

ans = 0
for _ in range(N):
  s = list(str(input()))
  string = "".join(sorted(s))
  if S.get(string) is None:
  	S[string] = 1
  else:
    ans += S[string]
    S[string] += 1
     
print(ans)
### BUGGY CODE ###

import bisect
N = int(input())
A = [int(input()) for n in range(N)]

tree = [[A[0]]]
leaf = [A[0]]
for n in range(1,N):
    a = A[n]
    pos = min(n-1,bisect.bisect_left(leaf,a)-1)
    if pos==-1:
        tree = [[a]] + tree
        leaf = [a] + leaf
    else:
        tree[pos].append(a)
        leaf[pos] = a
print(len(tree))

### FIXED CODE ###

import bisect
from collections import deque
N = int(input())
A = [int(input()) for n in range(N)]

tree = deque([[A[0]]])
leaf = deque([A[0]])
for n in range(1,N):
    a = A[n]
    pos = min(n-1,bisect.bisect_left(leaf,a)-1)
    if pos==-1:
        tree.appendleft([a])
        leaf.appendleft(a)
    else:
        tree[pos].append(a)
        leaf[pos] = a
print(len(tree))
### BUGGY CODE ###


# 1 2
n, m = list(map(int, input().split()))
c = [None]*m

key_prices = [0]*m
key_targets = [None]*m

for i in range(m):
    yen, matches_num = list(map(int, input().split()))
    key_prices[i] = yen
    key_targets[i] = set(map(int, input().split()))


min_price = -1


def calc(i, status):
    res = 0

    if i >= m:
        # res = 0
        if len(status) >= n:
            # print(status)
            # print(res)
            global min_price
            if res != 0 and (min_price == -1 or min_price > res):
                min_price = res
        else:
            res = 999999999
    elif key_targets[i] < status:
        # 入れる意味がない
        res = calc(i+1, status)
    else:
        r1 = calc(i+1, status)
        status = status | key_targets[i]
        r2 = calc(i+1, status)+key_prices[i]
        res = min(r1, r2)
    # memo[memo_key] = res

    return res


r = calc(0, set())

if r == 999999999:
    print(-1)
else:
    print(r)


### FIXED CODE ###

box_num, key_num = map(int, input().split())
dp_length = 2**box_num
dp = [float('inf')] * dp_length
dp[0] = 0
for _ in range(key_num):
    current_key_price, _ = map(int, input().split())
    c = 0
    effects = list(map(int, input().split()))
    for i in effects:
        e = 1 << (i - 1)
        c += e
    for x in range(dp_length):
        new_price = dp[x] + current_key_price
        dp_index = c | x
        if dp[dp_index] > new_price:
            dp[dp_index] = new_price
    # print(dp)
if dp[-1] == float('inf'):
    print(-1)
else:
    print(dp[-1])
### BUGGY CODE ###

def main():
    from collections import Counter as ct
    from bisect import bisect_left as bl

    n = int(input())
    max_a = sorted(ct(list(map(int, input().split()))).values())
    now_a = [i for i in max_a]
    m = len(max_a)
    cnt = m
    ans = 0
    ans_list = [0]*(n-m)

    for use in range(m, 1, -1):
        rest = ans
        nex = now_a[0]
        while rest:
            val = nex
            start = bl(now_a, val+1)
            nex += 1
            for i in range(start-1, max(-1, start-1-rest), -1):
                if now_a[i] == max_a[i]:
                    if start != m:
                        nex = now_a[start]
                    break
                elif now_a[i] == 0:
                    cnt += 1
                now_a[i] += 1
                rest -= 1
        while cnt >= use:
            ans += 1
            rest = use
            nex = now_a[-1]
            end = m
            while rest:
                val = nex
                start = bl(now_a, val)
                if start != 0:
                    nex = now_a[start-1]
                for i in range(start, min(end, start+rest)):
                    if now_a[i] > val:
                        break
                    elif now_a[i] == 1:
                        cnt -= 1
                    now_a[i] -= 1
                    rest -= 1
                end = start
        ans_list.append(ans)
    print(n)
    for i in ans_list[::-1]:
        print(i)


main()


### FIXED CODE ###

def main():
    from collections import Counter as ct
    from bisect import bisect_left as bl

    n = int(input())
    max_a = sorted(ct(list(map(int, input().split()))).values())
    now_a = [i for i in max_a]
    m = len(max_a)
    cnt = m
    ans = 0
    ans_list = []

    for use in range(n, 0, -1):
        rest = ans
        nex = now_a[0]
        # restの分だけ戻す
        while rest:
            val = nex
            start = bl(now_a, val+1)
            nex += 1
            for i in range(start-1, -1, -1):
                if now_a[i] == max_a[i]:
                    if start != m:
                        nex = now_a[start]
                    break
                elif now_a[i] == 0:
                    cnt += 1
                now_a[i] += 1
                rest -= 1
                if rest == 0:
                    break
        # 大きい方から使っていく
        while True:
            if cnt < use:
                ans_list.append(ans)
                break
            ans += 1
            rest = use
            nex = now_a[-1]
            end = m
            while rest:
                val = nex
                start = bl(now_a, val)
                if start != 0:
                    nex = now_a[start-1]
                for i in range(start, end):
                    if now_a[i] > val:
                        break
                    elif now_a[i] == 1:
                        cnt -= 1
                    now_a[i] -= 1
                    rest -= 1
                    if rest == 0:
                        break
                end = start
    for i in ans_list[::-1]:
        print(i)


main()
### BUGGY CODE ###

query=[int(x) for x in input().split()]
N = query[0]
K = query[1]
L = list()
L = [int(x) for x in input().split()]



def prob(x):
    out = 0.0

    out = (1 / x) * (x*(x+1))/2

    return out


final = 0.0
answer=list()
for i in range(0, N):
    final=0.0
    for j in range(i, K+i):
        if K+i<=N:
            div = L[j]
            final = final + prob(div)
    answer.append(final)

print("%14.12f"%max(answer))

### FIXED CODE ###

query=[int(x) for x in input().split()]
N = query[0]
K = query[1]
L = list()
L = [int(x) for x in input().split()]



def prob(x):
    out = 0.0

    out = (x+1)/2

    return out


# final = 0.0
# answer=list()
# for i in range(0, N):
#     final=0.0
#     for j in range(i, K+i):
#         if K+i<=N:
#             div = L[j]
#             final = final + prob(div)
#     answer.append(final)
#
# print("%14.12f"%max(answer))


res=0.0
tres=0.0
for i in range(0,K):
    tres+=prob(L[i])
    res=max(res,tres)
rindex=K
lindex=0
while rindex<N:
    tres=tres-prob(L[lindex])+prob(L[rindex])
    rindex+=1
    res=max(res,tres)
    lindex+=1
print("%14.12f"%res)
### BUGGY CODE ###


[A,B,C,D] = list(map(int,input().split()))
#print(C,D)
#both
import fractions
f=fractions.gcd(C,D)
f2=C*D//f
#print(f2)

i=-1
flag=0
while True:
    i+=1
    if f2*i>=A and flag!=1:
        hajime=i
        flag=1
    elif f2*i>B:
        owari=i
        break
both=owari-hajime
#print('both', both)

#C
i=-1
flag=0
while True:
    i+=1
    if C*i>=A and flag!=1:
        hajime=i
        flag=1
    elif C*i>B:
        owari=i
        break
Ccount=owari-hajime
#print('C', Ccount)

#D
i=-1
flag=0
while True:
    i+=1
    if D*i>=A and flag!=1:
        hajime=i
        flag=1
    elif D*i>B:
        owari=i
        break
Dcount=owari-hajime
#print('D', Dcount)

print(B-A+1 -(Ccount+Dcount-both))

### FIXED CODE ###


[A,B,C,D] = list(map(int,input().split()))
#print(C,D)
#both
import fractions
f=fractions.gcd(C,D)
f2=C*D//f
#print(f2)

both=B//f2 - (A-1)//f2
#print('both', both)

#C
Ccount=B//C - (A-1)//C
#print('C', Ccount)

#D
Dcount=B//D - (A-1)//D
#print('D', Dcount)

print(B-A+1 -(Ccount+Dcount-both))
### BUGGY CODE ###

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

def resolve():
    K = int(input())

    cnt = 0
    X = 1
    while cnt<K:
        if X<=9:
            # print(X)
            cnt += 1
        else:
            ok = True
            Xstr = str(X)
            for i in range(len(Xstr)-1):
                if abs(int(Xstr[i])-int(Xstr[i+1]))>1:
                    ok = False
            if ok:
                # print(X)
                cnt += 1
        X += 1
    print(X-1)

# 32 33 34 43 44 45 87 88 89 98 99 
# 100 101 110 111 112 121 122 123
# 210 211 212 221 222 223 232 233 234
# 321 322 323 332 333 334 343 344 345
# 876 877 878 887 888 889 898 899 
# 987 988 989 998 999

# 9
# 26 (3*9-1)
# 75 (6*9+21)
    # ans = []
    # def dfs(n):
    #     if len(ans)==K:
    #         ans.append(n)
    #     else:

    #         last = int(n[-1])
    #         for i in range(last-1, last, last+1):
    #             if 0<=i<10:
    #                 dfs(n+[i])
    # dfs('0')
    # print(ans)
    # print(ans[K-1])

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

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

def resolve():
    K = int(input())

    def dfs(depth, max_depth, num):
        if depth==max_depth:
            lunlun_temp.append(''.join([str(i) for i in num]))
        elif depth==0:
            for i in range(1, 10):
                dfs(depth+1, max_depth, num+[i])
        else:
            for i in range(3):
                if 0<=num[-1]-1+i<=9:
                    dfs(depth+1, max_depth, num+[num[-1]-1+i])

    lunlun = []

    i = 1
    while len(lunlun)<K:
        lunlun_temp = []
        dfs(0, i, [])
        lunlun += lunlun_temp
        i += 1

    print(lunlun[K-1])

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

import numpy as np
n,k=map(int,input().split())
a=list(map(int,input().split()))

def imo(a):
    imos=[0]*(n+1)

    for i in range(n):
        imos[max(0,i-a[i])]+=1
        imos[min(n,i+a[i]+1)]-=1
    
    arr=np.array(imos)
    cums=np.cumsum(arr)

    return cums[:n].tolist()

for i in range(min(k,35)):
    a=imo(a)
    
print(*a)


### FIXED CODE ###

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

def imo(a):
    imos=[0]*(n+1)

    for i in range(n):
        imos[max(0,i-a[i])]+=1
        imos[min(n,i+a[i]+1)]-=1
    
    immo=[0]*(n+1)
    immo[0]=imos[0]
    for i in range(n):
        immo[i+1]=immo[i]+imos[i+1]

    return immo[:n]

for i in range(min(k,41)):
    a=imo(a)
    
print(*a)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [None] * N

def solve(n):
    if dp[n] is not None:
        return dp[n]

    if n == 0:
        dp[n] = 0
    elif n == 1:
        dp[n] = abs(h[0] - h[1])
    else:
        ans = 10**10
        for i in range(1, K+1):
            if n - i < 0:
                break
            if dp[n - i] is not None:
                temp = dp[n - i]
            else:
                temp = solve(n - i)
            ans = min(ans, temp + abs(h[n - i] - h[n]))
        dp[n] = ans

    return dp[n]

print(solve(N-1))

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0] * n

for i in range(n):
    if i == 0:
        dp[0] = 0
    elif i == 1:
        dp[1] = abs(h[0]-h[1])
    else:
        costs = []
        for j in range(1, k+1):
            if j > i:
                break
            if abs(h[i-j]-h[i]) == 0:
                costs.append(dp[i-j])
                break
            costs.append(dp[i-j] + abs(h[i-j]-h[i]))

        # if i == 3:
        #     print(costs)
        dp[i] = min(costs)

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

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

dp = [0]*(n+1)
dp[0] = 0

for i in range(1,n):
  dp[i] = dp[i-1] + abs(h[i]-h[i-1])
  for j in range(2,min(i+1,k+1)):
    dp[i] = min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))    
  #print(dp[i])
print(dp[n-1])

### FIXED CODE ###

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

dp = [0]*(n+1)
dp[0] = 0

for i in range(1,n):
  dp[i] = dp[i-1] + abs(h[i]-h[i-1])
  for j in range(2,min(i+1,k+1)):
    dp[i] = min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))    
  #print(dp[i])
print(dp[n-1])
### BUGGY CODE ###

N = int(input())
S = [sorted(list(input()))for i in range(N)]
count = 0
for i in range(N):
    for j in range(i+1,N):
        if S[i]==S[j]:
            count+=1
print(count)

### FIXED CODE ###

N = int(input())
s = [sorted(input()) for _ in range(N)]
s.sort()

cnt = 0
ans = 0
for i in range(N-1):
    if s[i] == s[i+1]:
        cnt +=1
        ans += cnt
    else:
        cnt = 0
print(ans)
### BUGGY CODE ###

import sys
from itertools import product


X, Y, Z, K = map(int, input().split())
lst_A = sorted(map(int, input().split()), reverse=True)
lst_B = sorted(map(int, input().split()), reverse=True)
lst_C = sorted(map(int, input().split()), reverse=True)
lst_A_K = lst_A[:K]
lst_B_K = lst_B[:K]
lst_C_K = lst_C[:K]


lst_AB = sorted([a+b for a, b in product(lst_A_K, lst_B_K)], reverse=True)
lst_AB_K = lst_AB[:K]


lst_ABC = sorted([ab+c for ab, c in product(lst_AB_K, lst_C_K)], reverse=True)
lst_ABC_K = lst_ABC[:K]


print(*lst_ABC_K, sep="\n")


### FIXED CODE ###

import sys
from itertools import product


X, Y, Z, K = map(int, input().split())
lst_A = list(map(int, input().split()))
lst_B = list(map(int, input().split()))
lst_C = list(map(int, input().split()))
lst_A.sort(reverse=True)
lst_B.sort(reverse=True)
lst_C.sort(reverse=True)

# lst_A_K = lst_A[:K]
# lst_B_K = lst_B[:K]
lst_C_K = lst_C[:K]


lst_AB = sorted([a+b for a, b in product(lst_A, lst_B)], reverse=True)
lst_AB_K = lst_AB[:K]

lst_ABC = sorted([ab+c for ab, c in product(lst_AB_K, lst_C_K)], reverse=True)
lst_ABC_K = lst_ABC[:K]

print(*lst_ABC_K, sep="\n")
### BUGGY CODE ###

n = int(input())
initial_vals = list(map(int, input().split(" ")))


table = [[None for x in range(n)] for x in range(n)]


def calc(from_stone, to_stone):
    if table[from_stone][to_stone] is not None:
        return table[from_stone][to_stone]
    elif (to_stone - from_stone) == 1:
        table[from_stone][to_stone] = abs(
            initial_vals[from_stone] - initial_vals[to_stone]
        )
        return table[from_stone][to_stone]
    elif (to_stone - from_stone) == 2:
        table[from_stone][to_stone] = min(
            abs(initial_vals[from_stone] - initial_vals[to_stone - 1])
            + abs(initial_vals[to_stone - 1] - initial_vals[to_stone]),
            abs(initial_vals[from_stone] - initial_vals[to_stone]),
        )
        return table[from_stone][to_stone]
    else:
        table[from_stone][to_stone] = min(
            calc(from_stone, to_stone - 1) + calc(to_stone - 1, to_stone),
            calc(from_stone, to_stone - 2) + calc(to_stone - 2, to_stone),
        )
        return table[from_stone][to_stone]


print(calc(0, n - 1))


### FIXED CODE ###

n = int(input())
initial_vals = list(map(int, input().split(" ")))


# print(calc(0, n - 1))


arr = [0 for x in range(n)]

arr[1] = abs(initial_vals[0] - initial_vals[1])

for i in range(2, len(arr)):
    arr[i] = min(
        arr[i - 1] + abs(initial_vals[i - 1] - initial_vals[i]),
        arr[i - 2] + abs(initial_vals[i - 2] - initial_vals[i]),
    )

print(arr[n - 1])
### BUGGY CODE ###

#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

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

upper = []

Ts = 0
for i in range(N):
    upper.append((Ts, V[i]))
    Ts += T[i]
    upper.append((Ts, V[i]))

S = sum(T)
upper.append((0, 0))
upper.append((S, 0))

ans = [0]
Ts = 0
for i in range(N):
    dt = 0
    while True:
        dt += 0.5
        t = Ts + dt
        v = V[i]
        for p in upper:
            v = min(v, p[1] + abs(p[0] - t))
        ans.append(v)
        if dt == T[i]:
            break
    Ts += T[i]

print (sum(ans[1:]) + sum(ans[:-1])) / 4

### FIXED CODE ###

#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

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

upper = []

Ts = 0
for i in range(N):
    upper.append((Ts, V[i]))
    Ts += T[i]
    upper.append((Ts, V[i]))

S = sum(T)
upper.append((0, 0))
upper.append((S, 0))

ans = [0]
Ts = 0
for i in range(N):
    dt = 0
    while True:
        dt += 0.5
        t = Ts + dt
        v = V[i]
        for p in upper:
            v = min(v, p[1] + abs(p[0] - t))
        ans.append(v)
        if dt == T[i]:
            break
    Ts += T[i]

print (sum(ans[1:]) + sum(ans[:-1])) / 4