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

import sys
import math
from collections import defaultdict
from collections import deque
from itertools import permutations

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    N, M, R = NMI()
    targets = NLI()
    targets = [t-1 for t in targets]
    dist = [[10**9] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = NMI()
        dist[a-1][b-1] = c
        dist[b-1][a-1] = c
    for i in range(N):
        dist[i][i] = 0

    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    ans = 10**9
    for case in permutations(targets, R):
        now = case[0]
        cost = 0
        for goto in case[1:]:
            cost += dist[now][goto]
            now = goto
        ans = min(ans, cost)
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import math
from collections import defaultdict
from collections import deque
from itertools import permutations

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    N, M, R = NMI()
    targets = NLI()
    targets = [t-1 for t in targets]
    dist = [[10**9] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = NMI()
        dist[a-1][b-1] = c
        dist[b-1][a-1] = c
    for i in range(N):
        dist[i][i] = 0

    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    ans = 10**9
    for case in permutations(targets, R):
        now = case[0]
        cost = 0
        for goto in case[1:]:
            cost += dist[now][goto]
            now = goto
        ans = min(ans, cost)
    print(ans)

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

def main():
    for _ in range(M):
        A.sort()
        A[-1] = A[-1] // 2

    print(sum(A))


if __name__ == "__main__":
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    main()

### FIXED CODE ###

import heapq


def main():
    for _ in range(M):
        mx = heapq.heappop(A) * -1 // 2 * -1
        heapq.heappush(A, mx)

    print(sum(A) * -1)


if __name__ == "__main__":
    N, M = map(int, input().split())
    A = [int(x) * -1 for x in input().split()]
    heapq.heapify(A)
    main()
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))
A.sort()
F.sort(reverse=True)

ng = -1
ok = 10**18
while ok - ng > 1:
    mid = (ok + ng) // 2
    c = 0
    for i in range(N):
        c += max(0,A[i]-mid//F[i])
    if c <= K:
        ok = mid
    else:
        ng = mid
print(ok)


### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))
A.sort()
F.sort(reverse=True)

ng = -1
ok = 10**18
while ok - ng > 1:
    mid = (ok + ng) // 2
    c = 0
    for i in range(N):
        c += max(0,A[i]-mid//F[i])
    if c <= K:
        ok = mid
    else:
        ng = mid
print(ok)
### BUGGY CODE ###

num = input().split()
 
n = int(num[0])
y = int(num[1])

m = 0
g = 0
s = 0

flag = False


for i in range(n+1):
    if flag:
        break
    m = i
    
    for e in range(n+1):
        g = e
        
        for w in range (n+1):
            s=w
            
            if m+g+s == n:
                me = m * 10000
                ge = g * 5000
                se = s * 1000
                
                if me + ge + se == y:
                    flag = True
                    ma = m
                    ga = g
                    sa = s
    
if flag:
    print(ma,ga,sa)
else:
    print(-1,-1,-1)

### FIXED CODE ###

num = input().split()
 
n = int(num[0])
y = int(num[1])

m = 0
g = 0
s = 0

flag = False


for i in range(n+1):
    if flag:
        break
    m = i
    
    me = m * 10000
    
    if (y - me) / 5000 <= n: 
    
        for e in range(n+1):
            if flag:
                break
            g = e
            
            ge = g * 5000
            
            tmpS =  y - (me+ge)
            
            if (tmpS / 1000) + (m+g) == n and me+ge+tmpS == y and (tmpS / 1000) >= 0:
                flag = True
                ma = m
                ga = g
                if tmpS / 1000 > 0:
                    sa = tmpS / 1000
                    sa = int(sa)
                else: 
                    sa = 0
if flag:
    print(ma,ga,sa)
else:
    print(-1,-1,-1)
### BUGGY CODE ###

import numpy as np


def prepare(n, MOD):
    f = 1
    for m in range(1, n + 1):
        f = f * m % MOD
    fn = f

    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv = invs[m - 1] = inv * m % MOD
    invs = np.array(invs, dtype=np.int64)

    return fn, invs


n = int(input())
MOD = 998244353
fn, invs = prepare(n, MOD)

n2 = n // 2

# mul = 1
# muls = [0] * n2
# for i in range(n2):
#     mul = muls[i] = mul * 2 % MOD

# mul = 1
# muls = np.zeros(n2, dtype=np.int64)
# for i in range(n2):
#     mul = muls[i] = mul * 2 % MOD

muls = np.zeros(1, dtype=np.int64)
muls[0] = 2
while muls.size < n2:
    muls = np.append(muls, muls * muls[-1] % MOD)
muls = muls[:n2]

impossibles = invs[:n2] * invs[n:n2:-1] % MOD
impossibles = impossibles * muls % MOD
impossible = sum(list(impossibles)) % MOD * fn

print((pow(3, n, MOD) - impossible) % MOD)


### FIXED CODE ###

def prepare(n, MOD):
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f

    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return fn, invs


n = int(input())
MOD = 998244353
fn, invs = prepare(n, MOD)
ans = pow(3, n, MOD)
impossible = 0
mul = 2
for i in range(n // 2):
    tmp = fn * invs[i] * invs[n - i] % MOD * mul
    impossible = (impossible + tmp) % MOD
    mul = mul * 2 % MOD
print((ans - impossible) % MOD)
### BUGGY CODE ###

import collections
def main():

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

    cur = collections.defaultdict(int)
    cur[(A, B, C)] = ""
    for _ in range(N):
        s = input()
        temp = collections.defaultdict(int)
        for a, b, c in cur:
            if s == "AB":
                if b-1>=0:
                    temp[(a+1, b-1, c)] = cur[(a, b, c)] + 'A'
                if a-1>=0:
                    temp[(a-1, b+1, c)] = cur[(a, b, c)] + 'B'
            elif s == "AC":
                if c-1>=0:
                    temp[(a+1, b, c-1)] = cur[(a, b, c)] + 'A'
                if a-1>=0:
                    temp[(a-1, b, c+1)] = cur[(a, b, c)] + 'C'
            else:
                if b-1>=0:
                    temp[(a, b-1, c+1)] = cur[(a, b, c)] + 'C'
                if c-1>=0:
                    temp[(a, b+1, c-1)] = cur[(a, b, c)] + 'B'
        cur = temp

    if len(cur) > 0:
        print("Yes")
        for v in cur:
            for c in cur[v]:
                print(c)
            break
    else:
        print("No")

if __name__ == '__main__':
    main()

### FIXED CODE ###

import collections
def main():

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

    ans = ""
    s = []
    for _ in range(N):
        s.append(input())

    d = dict()
    d['A'] = A
    d['B'] = B
    d['C'] = C
    ans = ""
    for i in range(N):
        if d[s[i][0]] == 0 and d[s[i][1]] == 0:
            break
        elif d[s[i][0]] == 0:
            d[s[i][0]] += 1
            d[s[i][1]] -= 1
            ans += s[i][0]
        elif d[s[i][1]] == 0:
            d[s[i][1]] += 1
            d[s[i][0]] -= 1
            ans += s[i][1]
        else:
            if d[s[i][0]] == 1 and d[s[i][1]] == 1 and d['A'] + d['B'] + d['C'] == 2:
                if i < N-1 and s[i] != s[i+1] and s[i][0] in s[i+1]:
                    d[s[i][0]] += 1
                    d[s[i][1]] -= 1
                    ans += s[i][0]
                else:
                    d[s[i][1]] += 1
                    d[s[i][0]] -= 1
                    ans += s[i][1]
            elif d[s[i][0]] < d[s[i][1]]:
                d[s[i][0]] += 1
                d[s[i][1]] -= 1
                ans += s[i][0]
            else:
                d[s[i][1]] += 1
                d[s[i][0]] -= 1
                ans += s[i][1]

    if len(ans) == N:
        print("Yes")
        for c in ans:
            print(c)
    else:
        print("No")

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

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

dp = [float('inf') for _ in range(H + 1)]

dp[0] = 0

for a, b in M:
    for i in range(H+1):
        d = min(H, i + a)
        dp[d] = min(dp[d], dp[i] + b)

print(dp[H])

### FIXED CODE ###

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

dp = [float('inf') for _ in range(H + 1)]

dp[0] = 0

for a, b in M:
    for i in range(H+1):
        d = min(H, i + a)
        dp[d] = min(dp[d], dp[i] + b)

print(dp[H])
### BUGGY CODE ###

n=int(input())
a=[int(x) for x in input().rstrip().split()]
done=[False for i in range(n)]
if n%2==0:
  for i in range(n//2):
    if done[i]==True:
      continue
    for j in range(i+1,n):
      if done[j]==True:
        continue
      if a[i]%a[j]==0:
        done[i]=True

      if a[j]%a[i]==0:
        done[j]=True

  for i in range(n//2,n):
    if done[i]==True:
      continue
    for j in range(i+1,n):
      if done[j]==True:
        continue
      if a[i]%a[j]==0:
        done[i]=True

      if a[j]%a[i]==0:
        done[j]=True
else:
  for i in range(n//2):
    if done[i]==True:
      continue
    for j in range(i+1,n):
      if done[j]==True:
        continue
      if a[i]%a[j]==0:
        done[i]=True

      if a[j]%a[i]==0:
        done[j]=True
    
  for i in range(n//2,n):
    if done[i]==True:
      continue
    for j in range(i+1,n):
      if done[j]==True:
        continue
      if a[i]%a[j]==0:
        done[i]=True

      if a[j]%a[i]==0:
        done[j]=True
    
  
print(done.count(False))



### FIXED CODE ###

import sys

n=int(input())
a=[int(x) for x in input().rstrip().split()]
a.sort()
max_val=max(a)
dp=[True for i in range(max_val)]
done=[0 for i in range(max_val)]
cnt=0
ans=0

for i in a:

  if 1<=done[i-1]:
    done[i-1]+=1
    continue

  done[i-1]+=1
  cnt=1
  while(i*cnt<=max_val):
    cnt+=1
    if cnt*i<=max_val:
      done[cnt*i-1]+=1

for i in a:
  if done[i-1]==1:
      ans+=1

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

import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    X = i_input()

    Y = X//100
    L = []
    a = [0,1,2,3,4,5]

    for i in range(1,min(100,Y)+1):
        c = list(itertools.combinations_with_replacement(a, i))
        for i in c:
            L.append(sum(i))
    Z = X%100
 
    if Z in L:
        print(1)
    else:
        print(0)


  
if __name__=="__main__":
    main()


### FIXED CODE ###

import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    X = i_input()

    Y = X//100
    L = []
    a = [0,1,2,3,4,5]
 
    for i in range(1,min(20,Y)+1):
        c = list(itertools.combinations_with_replacement(a, i))
        for i in c:
            L.append(sum(i))
    Z = X%100
 
    if Z in L:
        print(1)
    else:
        print(0)


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

#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)


def solve(N: int, T: int, A: "List[int]", B: "List[int]"):
    max_t = T + max(A)
    dp = [-1] * (max_t + 1)
    dp[0] = 0
    p = []
    for i in range(N):
        p.append((A[i], B[i]))
    p.sort()
    for i in range(N):
        for t in range(T - 1, -1, -1):
            if dp[t] >= 0:
                dp[t + p[i][0]] = max(dp[t + p[i][0]], dp[t] + p[i][1])
    ret = 0
    for v in dp:
        ret = max(ret, v)
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, T, A, B)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)


def solve(N: int, T: int, A: "List[int]", B: "List[int]"):
    max_t = T + max(A)
    dp = [-1] * (max_t + 1)
    dp[0] = 0
    p = []
    for i in range(N):
        p.append((A[i], B[i]))
    p.sort()
    for i in range(N):
        for t in range(T - 1, -1, -1):
            if dp[t] >= 0:
                dp[t + p[i][0]] = max(dp[t + p[i][0]], dp[t] + p[i][1])
    ret = 0
    for v in dp:
        ret = max(ret, v)
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, T, A, B)

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

from collections import deque
N, Q = map(int, input().split())
S = input()
l = [0 for i in range(Q)]
r = [0 for i in range(Q)]
ans = r = [0 for i in range(Q)]
for i in range(Q):
    l[i], r[i] = map(int, input().split())

for i in range(Q):
    s = S[l[i]-1:r[i]]
    print(s.count('AC'))


### FIXED CODE ###

n,q = map(int,input().split())
s = list(input())

#a[i]:s[0]~s[i]までに何個ACがあったか
a = [0]*n
#end[i]:s[i]がACの'C'か
end = [False]*n
for i in range(1,n):
    if s[i] == 'C' and s[i-1] == 'A':
        a[i] = a[i-1]+1
        end[i] = True
    else:
        a[i] = a[i-1]

for i in range(q):
    L,R = map(int,input().split())
    L,R = L-1,R-1
    if L == 0:
        print(a[R])
    else:
        if end[L]:
            print(a[R]-a[L-1]-1)
        else:
            print(a[R]-a[L-1])
### BUGGY CODE ###

import copy

s = list(input())

s.reverse()
n = len(s)
MOD = 2019
m = [0] * n
msum = [0] * n
cnt = [0] * (MOD)
t = 0
for i in range(n):
    m[i] = int(s[i]) * 10**i % MOD
    t =  (t + m[i]) % MOD
    msum[i] = copy.deepcopy(t)
    cnt[t] += 1

ans = copy.deepcopy(cnt[0])
for i in range(1,MOD):
    ans += cnt[i] * (cnt[i] - 1) // 2
print(ans)

### FIXED CODE ###

import copy

s = list(input())

s.reverse()
n = len(s)
MOD = 2019
m = [0] * n
msum = [0] * (n+1)
cnt = [0] * (MOD)
cnt[0] = 1
t = 1
for i in range(n):
    m[i] = int(s[i]) * t % MOD
    msum[i+1] = (msum[i] + m[i]) % MOD
    cnt[msum[i+1]] += 1
    t = t * 10 % MOD

ans = 0
for i in range(MOD):
    ans += cnt[i] * (cnt[i] - 1) // 2
print(ans)
### BUGGY CODE ###

import math
n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))
a.sort()
a.reverse()
f.sort()
totalnum=sum(a)
maxproduct=0
for i in range(n):
  maxproduct=max(f[i]*a[i],maxproduct)
l1=0
r1=maxproduct
while True:
  l2=l1
  r2=(l1+r1)//2
  if l2==r2:
    break
  counter=0
  for i in range(n):
    c=math.floor(r2/f[i])
    while (c+1)*f[i]<=r2:
      c+=1
    counter+=max(0,a[i]-c)
  if counter<=k:
    r1=r2
  else:
    l1=r2
if l1==r1:
  print(r2)
else:
  counter=0
  r2=l1
  for i in range(n):
    c=math.floor(r2/f[i])
    while (c+1)*f[i]<=r2:
      c+=1
    counter+=max(0,a[i]-c)
  if counter<=k:
    print(l1)
  else:
    print(r1)

### FIXED CODE ###

import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))
a.sort()
a.reverse()
f.sort()
maxproduct=0
for i in range(n):
  maxproduct=max(f[i]*a[i],maxproduct)
l1=0
r1=maxproduct
while True:
  l2=l1
  r2=(l1+r1)//2
  if l2==r2:
    break
  counter=0
  for i in range(n):
    c=r2//f[i]
    while (c+1)*f[i]<=r2:
      c+=1
    counter+=max(0,a[i]-c)
  if counter<=k:
    r1=r2
  else:
    l1=r2
if l1==r1:
  print(r2)
else:
  counter=0
  r2=l1
  for i in range(n):
    c=r2//f[i]
    while (c+1)*f[i]<=r2:
      c+=1
    counter+=max(0,a[i]-c)
  if counter<=k:
    print(l1)
  else:
    print(r1)
### BUGGY CODE ###

H,N=map(int,input().split())
magic=[]
for _ in range(N):
    A,B=map(int,input().split())
    magic.append((A,B))

inf=float("inf")
dp=[inf]*(H+1)
dp[0]=0

for i in range(H):
    for a,b in magic:
        d=min(i+a,H)
        dp[d]=min(dp[d],dp[i]+b)
print(dp[H])

### FIXED CODE ###

H,N=map(int,input().split())
magic=[]
for _ in range(N):
    A,B=map(int,input().split())
    magic.append((A,B))

inf=float("inf")
dp=[inf]*(H+1)
dp[0]=0

for i in range(H):
    for a,b in magic:
        d=min(i+a,H)
        dp[d]=min(dp[d],dp[i]+b)
print(dp[H])
### BUGGY CODE ###

import sys
from collections import deque
readline = sys.stdin.readline
N = int(readline())

testimonies = [[[], []] for _ in range(N)]
for i in range(N):
    A = int(readline())
    for _ in range(A):
        x, y = map(int, readline().rstrip().split())
        testimonies[i][y].append(x-1)

def check(honest_persons):
    """矛盾がないか検証する"""
    honest_checked = set(honest_persons)  # 宛先を確認済みの正直者の人
    honest_stack = deque(honest_persons)  # 宛先を確認する正直者の人の待ち行列
    honest, liers = set(honest_persons), set()  # 正直者の人, 不親切な人

    # 正直者の人の証言も元に、正直者の人/不親切な人を追加していく
    while len(honest_stack) > 0:
        honest_person = honest_stack.popleft()
        honest_checked.add(honest_person)
        next_honest_persons = testimonies[honest_person][1]

        # 検証済み以外の人をstackする
        for person in next_honest_persons:
            if person not in honest_checked:
                honest_stack.append(person)

        honest |= set(testimonies[honest_person][1])
        liers |= set(testimonies[honest_person][0])

    # 矛盾がなければOK
    if len(honest & liers) == 0:
        return True
    else:
        return False

def main():
    # bit全探索する
    ans = 0
    has_checked = []
    for i in range(1, 2**N):
        comb = bin(i)[2:].zfill(N)
        honest_persons = []
        for p, c in enumerate(comb):
            if c == '1':
                honest_persons.append(p)
        
        flag = False
        for checked in has_checked:
            if checked < set(honest_persons):
                flag = True
                break
        
        if flag:
            continue

        if check(honest_persons):
            ans = max(ans, sum(list(map(int, list(comb)))))
        else:
            has_checked.append(set(honest_persons))

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
N = int(sys.stdin.readline())

testimonies = [[-1 for _ in range(N)] for _ in range(N)]
for i in range(N):
    A = int(sys.stdin.readline())
    for _ in range(A):
        x, y = map(int, sys.stdin.readline().rstrip().split())
        testimonies[i][x-1] = y

def check(honest_persons):
    flag = True
    for i in range(N):
        if honest_persons[i]:
            for j in range(N):
                if testimonies[i][j] == -1:
                    continue
                if testimonies[i][j] != honest_persons[j]:
                    flag = False
                    break
    return flag

def main():
    ans = 0
    for i in range(1, 2**N):
        honest_persons = bin(i)[2:].zfill(N)
        honest_persons = list(map(int, list(honest_persons)))

        if check(honest_persons):
            ans = max(ans, sum(honest_persons))

    print(ans)

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

N = int(input())
aList = list(map(int, input().split()))
tmp = set(aList)
tmpLst = list(tmp)
ans = 0

for i in tmpLst:
    t1 = aList.count(i)
    t2 = t1 - i
    if t2 > 0:
        ans += t2
    elif t2 < 0:
        ans += t1
print(ans)

### FIXED CODE ###

from collections import Counter

N = int(input())
aList = Counter(int(x) for x in input().split())
ans = 0
for i, j in aList.items():
    if i < j:
        ans += j - i
    elif i > j:
        ans += j
print(ans)
### BUGGY CODE ###

from sys import stdin,stdout,setrecursionlimit
from collections import Counter as C
from collections import defaultdict
setrecursionlimit(10**6)
M = 1000000007
input = stdin.readline
def write(n,sep="\n"):
	stdout.write(str(n))
	stdout.write(sep)
def gil():
	return list(map(int, input().split()))
	
n = int(input())
h = gil()

mem = [C() for _ in range(n+2)]
def rp(i, h, n, c, p):
    if c in mem[i]:
        return mem[i][c]
        
    if i >= n:
        ans = c + abs(p - h[n-1])
        mem[n][c] = ans
        return ans
        
    x = abs(p - h[i])
    ans = min(rp(i+1, h, n, c + x, h[i]),rp(i+2, h, n, c + x, h[i]))
    mem[i][c] = ans
    return mem[i][c]
    
ans = min(rp(1, h, len(h), 0, h[0]),rp(2, h, len(h), 0, h[0]))
print(ans)


### FIXED CODE ###

from sys import stdin,stdout,setrecursionlimit
from collections import Counter as C
setrecursionlimit(10**6)
M = 1000000007
input = stdin.readline
def write(n,sep="\n"):
	stdout.write(str(n))
	stdout.write(sep)
def gil():
	return list(map(int, input().split()))
	
n = int(input())
h = gil()
dp = [1e18]*(n+1)
dp[0] = 0
for i in range(n):
    for j in [i+1, i+2]:
        if j < n:
            dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]))
print(dp[n-1])
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*n
for i in range(1,n):
  dp[i]=min(d+abs(hh-h[i])for d,hh in zip(dp[max(i-k,0):i],h[max(i-k,0):i]))
print(dp[n-1])

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*n
for i in range(1,n):
  kk=max(i-k,0)
  dp[i]=min(d+abs(hh-h[i])for d,hh in zip(dp[kk:i],h[kk:i]))
print(dp[n-1])
### BUGGY CODE ###

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

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

A.sort(reverse=True)

for i in range(M):
    A[0] //= 2
    A.sort(reverse=True)

print(sum(A))

### FIXED CODE ###

import heapq
import math

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

A = list(map(lambda x: -x, map(int, input().split())))
heapq.heapify(A)

for i in range(M):
    tmp = heapq.heappop(A)
    tmp = math.ceil(tmp / 2)
    heapq.heappush(A, tmp)

print(-sum(A))