Harryxun/stf_run huggingface dataset:
#方針 最短経路以外を黒に塗れば良い
#最短経路が複数あってもその時通る白マスの数は不変なので、黒く塗れる白マスの数も不変である。
#したがって最短経路を求め(この時+1が実際に通る白マスの数になる)元々の白マスの数から
#最短経路+1を減算すれば答えは求まることになる。

from collections import deque

H,W = map(int,input().split())
maze = [list(input()) for _ in range(H)]

white_panel_cnt = 0
for y in range(H):
    for x in range(W):
        if maze[y][x] == '.':
            white_panel_cnt += 1
que = deque()

#スタート位置は(1,1)※list的には(0,0)になっている
sx,sy,gx,gy = (0,0,W-1,H-1)
que.append((sx,sy))
distance_from_start = [[-1]*W for _ in range(H)]
distance_from_start[sy][sx] = 0
move = [[1,0],[-1,0],[0,1],[0,-1]]

def minimum_distance():
    while len(que) != 0:
        x,y = que.popleft()
        #for i in range(len(distance_from_start)):
            #print(distance_from_start[i])
        if x == gx and y == gy:
            return distance_from_start[y][x]
        for i in range(4):
            next_x = x + move[i][0]
            next_y = y + move[i][1]
            #print(next_x,next_y)
            if next_x < 0 or next_x >= W or next_y < 0 or next_y >= H or distance_from_start[next_y][next_x] != -1 or maze[next_y][next_x] == '#':
                continue
            #print(distance_from_start[y][x])
            distance_from_start[next_y][next_x] = distance_from_start[y][x] + 1
            que.append((next_x,next_y))
        #for i in range(len(distance_from_start)):
            #print(distance_from_start[i])

distance = minimum_distance()
#print('distance={}'.format(distance))
if distance == -1:
    score = -1
else :
    score = white_panel_cnt-(distance+1)

print(score)


### FIXED CODE ###

#方針 最短経路以外を黒に塗れば良い
#最短経路が複数あってもその時通る白マスの数は不変なので、黒く塗れる白マスの数も不変である。
#したがって最短経路を求め(この時+1が実際に通る白マスの数になる)元々の白マスの数から
#最短経路+1を減算すれば答えは求まることになる。

from collections import deque

H,W = map(int,input().split())
maze = [list(input()) for _ in range(H)]

white_panel_cnt = 0
for y in range(H):
    for x in range(W):
        if maze[y][x] == '.':
            white_panel_cnt += 1
que = deque()

#スタート位置は(1,1)※list的には(0,0)になっている
sx,sy,gx,gy = (0,0,W-1,H-1)
que.append((sx,sy))
distance_from_start = [[-1]*W for _ in range(H)]
distance_from_start[sy][sx] = 0
move = [[1,0],[-1,0],[0,1],[0,-1]]

def minimum_distance():
    while len(que) != 0:
        x,y = que.popleft()
        #for i in range(len(distance_from_start)):
            #print(distance_from_start[i])
        if x == gx and y == gy:
            return distance_from_start[y][x]
        for i in range(4):
            next_x = x + move[i][0]
            next_y = y + move[i][1]
            #print(next_x,next_y)
            if next_x < 0 or next_x >= W or next_y < 0 or next_y >= H or distance_from_start[next_y][next_x] != -1 or maze[next_y][next_x] == '#':
                continue
            #print(distance_from_start[y][x])
            distance_from_start[next_y][next_x] = distance_from_start[y][x] + 1
            que.append((next_x,next_y))
        #for i in range(len(distance_from_start)):
            #print(distance_from_start[i])

distance = minimum_distance()
#print('distance={}'.format(distance))
if distance == None:
    score = -1
else :
    score = white_panel_cnt-(distance+1)

print(score)
# coding: utf-8
# Your code here!
x=int(input())
ans=[]
for i in range(1,x+1):
    for j in range(2,x+1):
        if i**j<=x:
            ans.append(i**j)
        else:
            break
ans.sort(reverse=True)
print(ans[0])
#print(ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!
x=int(input())
ans=[]
if x==1:
    print(1)
else:
    for i in range(1,x+1):
        for j in range(2,x+1):
            if i**j<=x:
                ans.append(i**j)
            else:
                break
    ans.sort(reverse=True)
    print(ans[0])
#print(ans)
n = int(input())
a = list(map(int, input().split()))
p = 1
for i in range(n):
    p *= a[i]
if p > int(1E18):
    print(-1)
else
    print(p)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
p = 1
if a.count(0):
    print(0)
    exit(0)
for i in range(n):
    p *= a[i]
    if p > int(1E18):
        print(-1)
        exit(0)
print(p)
N,K=map(int,input().split())
P=[int(input()) for _ in range(N)]

pp=[0]*N
for i in range(N):
    pp[i]=(p[i]+1)/2
sum=0
for i in range(0,K):
    sum+=pp[i]
for i in range(0,N-K):
    sum=max(sum,sum-pp[i]+pp[i+K])
print(sum)

    



### FIXED CODE ###

from itertools import accumulate

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

pp=[0]*N
for i in range(N):
  pp[i]=(p[i]+1)/2

sum=0
temp=0
for i in range(0,K):
  temp+=pp[i]
sum=temp
for i in range(0,N-K):
  temp=temp-pp[i]+pp[i+K]
  sum=max(sum,temp)
print(sum)
n, q = map(int, input().split())
g = [[] for i in range(n+1)]
c = [0 for i in range(n+1)]
ans = [0 for i in range(n+1)]
for i in range(n-1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
for i in range(q):
    p, x = map(int, input().split())
    c[p] += x

def dfs(now, fro, point):
    now, fro, point = int(now), int(fro), int(point)
    point += c[now]
    ans[now] = point
    for i in range(len(g[now])):
        if g[now][i]==fro:
            continue
        dfs(g[now][i], now, point)


dfs(1, -1, 0)
for i in range(1, n+1):
    print(ans[i], end='')
    if i!=n:
        print(' ', end='')
print('')


### FIXED CODE ###

def main():
    from collections import deque
    n, q = map(int, input().split())
    g = [[] for i in range(n+1)]
    point = [0 for i in range(n+1)]
    for i in range(n-1):
        a, b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)
    for i in range(q):
        p, x = map(int, input().split())
        point[p] += x

    q = deque([[1,0]])
    for j in range(n):
        now = q.pop()
        point[now[0]] += point[now[1]]
        for i in g[now[0]]:
            if i==now[1]:
                continue
            q.append([i,now[0]])
    for i in range(1, n+1):
        print(point[i], end='')
        if i!=n:
            print(' ', end='')

if __name__ == '__main__':
    main()
import numpy as np

H, W, K = map(int, input().split())

C = np.frombuffer(read(), dtype='S1').reshape(H, -1)
print(C)

### FIXED CODE ###

from itertools import combinations
import numpy as np

H, W, K = map(int, input().split())

C = []
base = 0
for i in range(H):
	string = input()
	string = string.replace('.', '0')
	string = string.replace('#', '1')
	lst = list(string)
	lst = [int(c) for c in lst]
	C.append(lst)
	base += sum(lst)

C = np.array(C)
orig = C.copy()
count = 0

for i in range(H+1):
	for j in range(W+1):
		for c in combinations(range(H), i):
			for d in combinations(range(W), j):
				for row in c:
					C[row] = [0] * W
				for col in d:
					C[:, col] = [0] * H
				if np.sum(C) == K:
					count += 1
				C = orig.copy()

print(count)
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, shortest_path
n, m, *AB = map(int, open(0).read().split())
graph = [[10**9]*n for _ in range(n)]
for a, b in zip(AB[::2], AB[1::2]):
    graph[a-1][b-1] = 1
    graph[b-1][a-1] = 1
G = csgraph_from_dense(graph)
d, p = shortest_path(G, indices=0, method='D', return_predecessors=1)
if np.any(d > 10**9-1):
    print('No')
else:
    print('Yes')
    print(*map(lambda x: int(x)+1, p[1:]), sep='\n')

### FIXED CODE ###

from collections import deque
n, m, *AB = map(int, open(0).read().split())
graph = [[] for _ in range(n)]
for a, b in zip(AB[::2], AB[1::2]):
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

d = [0] * n
queue = deque([0])
while queue:
    current_node = queue.popleft()
    for next_node in graph[current_node]:
        if d[next_node] == 0:
            d[next_node] = current_node+1
            queue.append(next_node)
print('Yes')
print(*d[1:], sep='\n')
n = int(input())
strs=[]
ind_a=[]
ind_b=[]
ind_both=[]
num=0
for i in range(n):
   str=input()
   num=num+str.count("AB")
   if str[len(str)-1]=="A":
       if str[0]=="B":
           ind_both.append(i)
       else:
           ind_a.append(i)
   elif str[0]=="B":
       ind_b.append(i)
big=0
small=0
both=len(ind_both)
if len(ind_a) > len(ind_b):
    big=len(ind_a)
    small=len(ind_b)
else:
    big=len(ind_b)
    small=len(ind_a)
if (big-small)>=both:
    num=num+small+both
else:
    both=both-(big-small)+1
    num=num+big+int(both/2)
print(num)
   





### FIXED CODE ###

import math

n,k = (int(i) for i in input().split()) 
print(n-k+1)
from collections import defaultdict, deque, Counter
import sys
import heapq
import math

input = sys.stdin.readline

sys.setrecursionlimit(10000000)

MIN = -10 ** 9
MOD = 10 ** 9 + 7


def solve(pre, s):
    if len(s) == 1:
        if pre != s:
            return 1
        return None
    for i in range(1, len(s)):
        if pre == s[:i]:
            continue
        r = solve(s[:i], s[i:])
        if r is not None:
            return r + 1
    if pre != s:
        return 1


def main():
    s = input().strip()
    # N = int(input())
    print(solve("", s))
    # N, A, B = [int(a) for a in input().split()]
    # A = [
    #     [int(a) for a in input().split()]
    #     for _ in range(N)
    # ]


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict, deque, Counter
import sys
import heapq
import math

# input = sys.stdin.readline

sys.setrecursionlimit(1000000000)

MIN = -10 ** 9
MOD = 10 ** 9 + 7


def f(n):
    if n == 0:
        return 0, False
    a = n // 3
    b = n % 3
    if b == 0:
        return a * 2, 0
    if b == 1:
        return a * 2 + 1, 1

    return a * 2 + 1, 2


def solve(s):
    last = s[0]
    c = 1
    res = 0
    last_flag = False
    for cc in s[1:]:
        if last == cc:
            c += 1
            continue

        k, k_flag = f(c)
        if k_flag == 0:
            res += k
        elif k_flag == 1:
            res += k
            last_flag = False
        else:
            if last_flag:
                res += k + 1
                last_flag = False
            else:
                res += k
                last_flag = True
        c = 1
        last = cc
    k, k_flag = f(c)
    if k_flag == 0:
        res += k
    elif k_flag == 1:
        res += k
    else:
        if last_flag:
            res += k + 1
        else:
            res += k
    return res


def main():
    s = input()
    # N = int(input())
    print(solve(s))
    # N, A, B = [int(a) for a in input().split()]
    # A = [
    #     [int(a) for a in input().split()]
    #     for _ in range(N)
    # ]


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

As = sorted(A)
As = [a%As[0] if a%As[0] != 0 else As[0] for a in As]
As = sorted(As)

def judge(tmp_one, tmp_two):
    flg = 1
    
    while flg:
        if tmp_two % tmp_one == 0:
            tmp_two = tmp_one
        else:
            tmp_two = tmp_two % tmp_one
            
        if tmp_one % tmp_two == 0:
            tmp_one = twp_two
        else:
            tmp_one = tmp_one % tmp_two
        if tmp_one == tmp_two:
            flg = 0
            
        return tmp_one
tmp_one = As[0]
for i in range(1, N):
    if i == N  - 1:
        tmp_two = As[i]
    elif As[i] != As[0]:
        tmp_two = As[i]
        break
        
ans = judge(tmp_one, tmp_two)
print(ans)

### FIXED CODE ###

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

As = sorted(A)
As = [a%As[0] if a%As[0] != 0 else As[0] for a in As]
As = sorted(As)

def judge(tmp_one, tmp_two):
    flg = 1

    while flg:
        if tmp_two%tmp_one == 0:
            tmp_two = tmp_one
        else:
            tmp_two = tmp_two%tmp_one

        if tmp_one%tmp_two == 0:
            tmp_one = tmp_two
        else:
            tmp_one = tmp_one%tmp_two
        if tmp_one == tmp_two:
            flg = 0

    return tmp_one

tmp_one = As[0]
for i in range(1, N):
    if i == N - 1:
        tmp_two = As[i]
    elif As[i] != As[0]:
        tmp_two = As[i]
        break

ans = judge(tmp_one, tmp_two)
print(ans)
from itertools import permutations

N = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))

l = permutations(range(1,N+1))

print(abs(l.index(P)-l.index(Q)))

### FIXED CODE ###

from itertools import permutations
 
N = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))
 
l = list(permutations(range(1,N+1)))
 
print(abs(l.index(P)-l.index(Q)))
n = int(input())
a_b = [input() for i in range(n)]
min = 1000000001
max = -1
max_point = 0
for i in a_b:
    a, b = map(int, i.split())
    if(min > a):
        min = a
    if(max < a):
        max = a
        max_point = b

num = 0
num += min
num += max - min
num += max_point

print(num)


### FIXED CODE ###

s = str(input())
char = list(s)
num = 0
for c in char:
    if int(c) == 1:
        num += 1

print(num)
s = list(map(int,input().split()))
t = max(s[0]+s[1],s[0]-s[1],s[0]*s[1],s[0]/s[1])
print(t)
print('A+B={0},A-B={1},A*B={2},A/B={3}の中で最大の数{4}はです'.format(s[0]+s[1],s[0]-s[1],s[0]*s[1],s[0]/s[1],t))


### FIXED CODE ###

s = list(map(int,input().split()))
t = max(s[0]+s[1],s[0]-s[1],s[0]*s[1])
print(t)
'''
print('A+B={0},A-B={1},A*B={2},A/B={3}の中で最大の数{4}はです'.format(s[0]+s[1],s[0]-s[1],s[0]*s[1],s[0]/s[1],t))
'''
N=int(input())

R=[[] for i in range(N)]

for i in range(N-1):
    a,b,c=map(int,input().split())
    R[a-1].append([b-1,c])
    R[b-1].append([a-1,c])

Q,K=map(int,input().split())
C=[0]*N
stack=[]
for i in range(N):
    if i==K-1:
        C[i]=0
    else:
        chk = [0] * N
        stack=[[K-1,i,0]]
        f=True
        while stack:
            if f==False:
                break
            s,g,d=stack.pop()
            chk[s]=1
            for j,c in R[s]:
                if chk[j]==1:continue
                if j==g:
                    C[i]=d+c
                    f=False
                    break
                else:
                    stack.append([j,g,d+c])

for i in range(Q):
    x,y=map(int,input().split())
    print(C[x-1]+C[y-1])



### FIXED CODE ###

N = list(input())
if N[0]==N[2]:
    print("Yes")
else:
    print("No")
n = int(input())
p = [list() for _ in range(n)]
for i in range(n-1):
    u, v, w = [int(s) for s in input().split()]
    u -= 1
    v -= 1
    w %= 2
    p[u].append((v, w))
    p[v].append((u, w))

costs = [-1 for _ in range(n)]

def dfs(cur, dist):
    if costs[cur] != -1:
        return
    costs[cur] = dist
    for v, d in p[cur]:
        dfs(v, dist^d)
dfs(0, 0)

for c in costs:
    print(c)


### FIXED CODE ###

import sys
 
sys.setrecursionlimit(10**5)

n = int(input())
p = [list() for _ in range(n)]
for i in range(n-1):
    u, v, w = [int(s) for s in input().split()]
    u -= 1
    v -= 1
    w %= 2
    p[u].append((v, w))
    p[v].append((u, w))

costs = [-1 for _ in range(n)]

def dfs(cur, dist):
    if costs[cur] != -1:
        return
    costs[cur] = dist
    for v, d in p[cur]:
        dfs(v, dist^d)
dfs(0, 0)

for i in range(n):
    print(costs[i])
import sys
from itertools import permutations

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N = int(input())
    assert N <= 8

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

    cnt = 0
    MOD = 10**9 + 7

    for pm in permutations(range(N)):
        goal = [False] * N
        flag = True

        for k in pm:
            mae = 0
            for i in range(k):
                if goal[i]:
                    continue
                
                if X[i] < 2*mae + 1:
                    flag = False
                    break
                else:
                    mae += 1

            if not flag:
                break

            goal[k] = True

        cnt += flag

    print(cnt % MOD)


if __name__ == '__main__':
    solve()

### FIXED CODE ###

import sys
from math import factorial

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N = int(input())
    X = [int(i) for i in input().split()]
    MOD = 10**9 + 7
    ans = 1
    stack = 0

    for x in X:
        stack += 1
        if x < 2*(stack - 1) + 1:
            ans *= stack
            ans %= MOD
            stack -= 1

    ans *= (factorial(stack) % MOD)
    ans %= MOD

    print(ans)


if __name__ == '__main__':
    solve()
N = input()
S = N / 2
if N % 2 = 0
	print(S)
else
	print(S + 1)

### FIXED CODE ###

N = int(input())
S = -(-N // 2)
print (S)
from heapq import *
class UnionFind():
  def __init__(self,n):
    self.n=n
    self.parents=[-1]*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 unite(self,x,y):
    x=self.find(x)
    y=self.find(y)
    if x==y:
      return
    if self.parents[x]>self.parents[y]:
      x,y=y,x
    self.parents[x]+=self.parents[y]
    self.parents[y]=x
  def size(self,x):
    return -size.parents[self.find(x)]
  def same(self,x,y):
    return self.find(x)==self.find(y)
  def members(self,x):
    root=self.find(x)
    return [i for i in range(self.n) if self.find(i)==root]
  def roots(self):
    return [i for i,x in enumerate(self.parents) if x<0]
  def group_count(self):
    return len(self.roots())
n=int(input())
X=[[] for i in range(n)]
Y=[[] for i in range(n)]
edge=[[] for i in range(n)] 
for i in range(n):
  x,y=map(int,input().split())
  X.append((x,i))
  Y.append((y,i))
  edge.append((x,y))
X.sort()
Y.sort()
hq=[]
heapify(hq)
for i in range(n-1):
  x1,j1=X[i]
  x2,j2=X[i+1]
  y1,k1=Y[i]
  y2,k2=Y[i+1]
  heappush(hq,(x2-x1,j1,j2))
  heappush(hq,(y2-y1,k1,k2))
uf=UnionFind(n)
ans=0
while hq:
  w,s,t=heappop(hq)
  if uf.find(s)!=uf.find(t):
    uf.unite(s,t)
    ans+=w
print(ans)

### FIXED CODE ###

from heapq import *
class UnionFind():
  def __init__(self,n):
    self.n=n
    self.parents=[-1]*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 unite(self,x,y):
    x=self.find(x)
    y=self.find(y)
    if x==y:
      return
    if self.parents[x]>self.parents[y]:
      x,y=y,x
    self.parents[x]+=self.parents[y]
    self.parents[y]=x
  def size(self,x):
    return -size.parents[self.find(x)]
  def same(self,x,y):
    return self.find(x)==self.find(y)
  def members(self,x):
    root=self.find(x)
    return [i for i in range(self.n) if self.find(i)==root]
  def roots(self):
    return [i for i,x in enumerate(self.parents) if x<0]
  def group_count(self):
    return len(self.roots())
n=int(input())
X=[]
Y=[]
edge=[] 
for i in range(n):
  x,y=map(int,input().split())
  X.append((x,i))
  Y.append((y,i))
  edge.append((x,y))
X.sort()
Y.sort()
hq=[]
heapify(hq)
for i in range(n-1):
  x1,j1=X[i]
  x2,j2=X[i+1]
  y1,k1=Y[i]
  y2,k2=Y[i+1]
  heappush(hq,(x2-x1,j1,j2))
  heappush(hq,(y2-y1,k1,k2))
uf=UnionFind(n)
ans=0
while hq:
  w,s,t=heappop(hq)
  if uf.find(s)!=uf.find(t):
    uf.unite(s,t)
    ans+=w
print(ans)
temp = input()
temp = temp.split(' ')
h = int(temp[0])
n = int(temp[1])
a = input().split(' ')

if h <= sum(int(i) for i in a):
	print('Yes')
else
	print('No')

### FIXED CODE ###

temp = input()
temp = temp.split(' ')
h = int(temp[0])
n = int(temp[1])
a = input().split(' ')

if h <= sum(int(i) for i in a):
	print('Yes')
else:
	print('No')
import math
k = int(input())
ans = 0

for i in range(1,k+1):
	for j in range(1,k+1):
      	for k in range(1,k+1):
          	ans += math.gcd(i,math.gcd(j,k))
print(ans)


### FIXED CODE ###

import math
k = int(input())
ans = 0
if k < 3:
    for i in range(1,k+1):
        for j in range(1,k+1):
            for n in range(1,k+1):
                ans += math.gcd(i,math.gcd(j,n))
else: 
    #i*j
    for n in range(1,k+1):
        for i in range(1,k+1):
            ans += math.gcd(n,i)
            for j in range(i+1,k+1):            
                ans += 2*(math.gcd(math.gcd(i,j),n))

    '''
        for i in range(1,k+1):
            for j in range(i+1,k+1):
                for k in range(j+1,k+1):
                    ans += math.gcd(i,math.gcd(j,k))
    '''
print(ans)
import sys
def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf

s = sinput()
q = iinput()
cnt = 0
for i in range(q):
    try: t,f,c = sarr()
    except: cnt += 1; cnt %= 2; continue
    if cnt:
        if f == "1": s = s + c
        if f == "2": s = c + s
    else:
        if f == "1": s = c + s
        if f == "2": s = s + c
    #print(s)

s = s[::-1] if cnt else s
print(s)



### FIXED CODE ###

import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import cmath as cma
import copy as cp
import sys
def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf

s = col.deque(sinput().split())
q = iinput()
cnt = 0
for i in range(q):
    try: t,f,c = sarr()
    except: cnt += 1; cnt %= 2; continue
    if cnt: #反転の状態
        if f == "1": s.append(c)
        if f == "2": s.appendleft(c)
    else: #ノーマル状態
        if f == "1": s.appendleft(c)
        if f == "2": s.append(c)
    #print(s)

s = "".join(s)
s = s[::-1] if cnt else s
print(s)
n=int(input())
edge=[[]for i in range(n+1)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    if c%2==0:
        edge[a].append((b,1))
        edge[b].append((a,1))
    else:
        edge[a].append((b,-1))
        edge[b].append((a,-1))
        

ans=[None]*(n+1)
check=[None]*(n+1)
check[1]=1


for i in range(1,n+1):
    for j in edge[i]:
        if ans[j[0]] is None:
            ans[j[0]]=check[i]*j[1]
            check[j[0]]=check[i]*j[1]
            
for i in ans[1:]:
    print((i+1)//2)
    

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

n=int(input())

edge=[[] for _ in range(n+1)]

for i in range(n-1):
    v1,v2,w=map(int,input().split())
    if w%2!=0:
        edge[v1].append((v2,-1))
        edge[v2].append((v1,-1))
    else:
        edge[v1].append((v2,1))
        edge[v2].append((v1,1))

color=[None]*(n+1)        
def set_color(x,col):
    color[x]=col
    
    for i,j in edge[x]:
        if color[i] is None:
            set_color(i,j*col)
set_color(1,1)

for x in color[1:]:
    print((x+1)//2)
N =int(input())
H = list(map(int, input().split()))
#総数Nで、N番目の添字はN-1
flog = 0

#メモ化再帰
memo = [-1]*N
def func(n,memo):
  if n == 0:
    min_c = 0
  elif n == 1:
    min_c = abs(H[n]-H[0])
  else:
    if memo[n] != -1:
      return memo[n]
    else:
      min_c = min(func(n-1,memo)+abs(H[n]-H[n-1]),func(n-2,memo)+abs(H[n]-H[n-2]))
  memo[n] = min_c
  return min_c

print(func(N-1,memo))

### FIXED CODE ###

N =int(input())
H = list(map(int, input().split()))
#総数Nで、N番目の添字はN-1
flog = 0

#足場iにたどり着くための最小コストをリスト化
mincost= []
for i in range(N):
  if i == 0:
    c = 0
  elif i == 1:
    c = abs(H[1]-H[0])
  else:
    c = min(abs(H[i]-H[i-1])+mincost[i-1],abs(H[i]-H[i-2])+mincost[i-2])
  mincost.append(c)

print(mincost[N-1])