Harryxun/stf_run huggingface dataset:
import sys


class AlgSegmentTreeMin:
    def __init__(self, n, default_value):
        self.Nelem = n
        self.default_value = default_value
        self.size = 1 << (n.bit_length())
        self.data = [default_value] * (2 * self.size)

    def update(self, i, x):
        i += self.size
        self.data[i] = x
        i >>= 1
        while i:
            x = self.data[i + i]
            y = self.data[i + i + 1]
            self.data[i] = min(x, y)
            i >>= 1

    def get_value(self, left, right):
        left += self.size
        right += self.size + 1
        x = self.default_value
        while left < right:
            if left & 1:
                y = self.data[left]
                x = min(x, y)
                left += 1
            if right & 1:
                right -= 1
                y = self.data[right]
                x = min(x, y)
            left >>= 1
            right >>= 1
        return x


def solve():
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().split()))
    stree = AlgSegmentTreeMin(n, 10 ** 15)
    m = map(int, read().split())
    lrc = zip(m, m, m)
    lrc.sort()
    stree.update(0, 0)
    for l, r, c in lrc:
        l -= 1
        r -= 1
        tm = stree.get_value(l, r)
        now = stree.get_value(r, r)
        tm = tm + c if tm + c < now else now
        stree.update(r, tm)
    mt = stree.get_value(n-1, n)
    print(mt if mt != stree.default_value else -1)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys


class SegTreeMin:

    def __init__(self, n, max_v):
        self.n = n
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [max_v] * (n2 << 1)
        self.INF = max_v

    def update(self, i, x):
        i += self.n2
        self.tree[i] = x
        while i > 1:
            self.tree[i >> 1] = x = min(x, self.tree[i ^ 1])
            i >>= 1

    def get_min(self, a, b):
        result = self.INF
        q = [(1, 0, self.n2)]
        while q:
            k, l, r = q.pop()

            if a <= l and r <= b:
                result = min(result, self.tree[k])
                continue

            m = (l + r) // 2
            k <<= 1
            if a < m and l < b:
                q.append((k, l, m))
            if a < r and l < m:
                q.append((k + 1, m, r))

        return result


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    seg_tree = SegTreeMin(n, 10 ** 15)
    seg_tree.update(0, 0)
    lrc = [list(map(int, input().rstrip('\n').split())) for _ in range(m)]
    lrc.sort()
    for l, r, c in lrc:
        l -= 1
        r -= 1
        tm = seg_tree.get_min(l, r)
        seg_tree.update(r, min(tm + c, seg_tree.get_min(r, r + 1)))
    mt = seg_tree.get_min(n-1, n)
    print(mt if mt != 10 ** 15 else -1)


if __name__ == '__main__':
    solve()
N, M = map(int, input().split())
L = []
R = []
D = []
for i in range(M):
    l, r, d = map(int, input().split())
    L.append(l)
    R.append(r)
    D.append(d)

inf = float("inf")


class WDG():  # 重み付き有向グラフ(隣接リスト表現)
    class node():
        def __init__(self, index=0, weight=0, next=None):
            self.index = index
            self.weight = weight
            self.next = next

    def __init__(self, N, M, L, R, D):
        self.heads = []
        self.x = [None] * N
        self.N = N
        for i in range(N):
            head = WDG.node()
            head.next = head
            head.index = i
            self.heads.append(head)
        for i in range(M):
            new1 = WDG.node(R[i] - 1, D[i], head)
            new2 = WDG.node(L[i] - 1, -D[i], head)
            self.insert(L[i] - 1, new1)
            self.insert(R[i] - 1, new2)

    def insert(self, start, new):
        new.next = self.heads[start].next
        self.heads[start].next = new

    def show_graph(self):
        for i in self.heads:
            node = i.next
            print("{}=>".format(i.index + 1), end="")
            while node != i:
                print("{}({})".format(node.index + 1, node.weight), end=" ")
                node = node.next
            print("")

    def _DFS(self, s_head):  # 始点sから到達できる連結成分を深さ優先探索
        node = s_head.next
        while node != s_head:
            new_x = self.x[s_head.index] + node.weight
            if self.x[node.index] is None:
                #print("node{}".format(node.index + 1))
                self.x[node.index] = new_x
                if not self._DFS(self.heads[node.index]):
                    return False
            elif self.x[node.index] != new_x:
                #print("node{}NG".format(node.index + 1))
                return False
            node = node.next
        return True

    def DFS(self):  # すべての点を訪れるまで深さ優先探索
        for i in range(self.N):
            node = self.heads[i]
            if self.x[node.index] is None:
                self.x[node.index] = 0
                if not self._DFS(self.heads[node.index]):
                    return "No"
        return "Yes"


G = WDG(N, M, L, R, D)
# G.show_graph()
print(G.DFS())


### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(M):
    l, r, d = map(int, input().split())
    G[l - 1].append((r - 1, d))
    G[r - 1].append((l - 1, -d))
q = deque()

x = [None] * N


def _BFS(start):
    q.append(start)
    while len(q) != 0:
        p = q.popleft()
        for index, d in G[p]:
            if x[index] is None:
                x[index] = x[p] + d
                q.append(index)
            elif x[index] != x[p] + d:
                return False
    return True


def BFS():
    for i in range(N):
        if x[i] is None:
            x[i] = 0
            if not _BFS(i):
                return "No"
    return "Yes"


print(BFS())
x, y, z, k = map(int, input().split())
a=list(map(int,input().split())).sort(reverse=True)
b=list(map(int,input().split())).sort(reverse=True)
c=list(map(int,input().split())).sort(reverse=True)

ab=[]

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

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

for i in abc[:k]:
    print(i)

### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

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

ab = sorted(x+y for x in a for y in b)[:-k-1:-1]
abc = sorted(x+y for x in ab[:k] for y in c)[:-k-1:-1]
print(*abc, sep='\n')
import math
a = float(input())
print (a ** 2.0 * math.pi, a * 2.0 * math.pi)



### FIXED CODE ###

a, b = map(int, input().split())
print (a // b, a % b , "%.9f" % (a / b))
def main():
    n,h = list(map(int, input().split()))
    bi = []
    max_attack = [0,0]
    for i in range(n):
        a, b = list(map(int, input().split()))
        bi.append(b)
        max_attack[0] = max(a, max_attack[0])
        max_attack[1] = max(b, max_attack[1])
    bi.sort(reverse=True)
    idx = 0
    count = 0
    while h > 0:
        damage = 0
        if max_attack[0] < bi[idx]:
            damage = bi[idx]
            idx += 1
        else:
            # count += max_attack[0] // h
            count += h // max_attack[0]
            break
        h -= damage
        count += 1
    print(count)



if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n,h = list(map(int, input().split()))
    bi = []
    max_attack = [0,0]
    for i in range(n):
        a, b = list(map(int, input().split()))
        bi.append(b)
        max_attack[0] = max(a, max_attack[0])
        max_attack[1] = max(b, max_attack[1])
    bi.sort(reverse=True)
    idx = 0
    count = 0
    while h > 0:
        damage = 0
        if idx < len(bi) and max_attack[0] < bi[idx]:
            damage = bi[idx]
            idx += 1
        else:
            count += h // max_attack[0]
            count += 0 if h % max_attack[0] == 0 else 1
            break
        h -= damage
        count += 1
    print(count)



if __name__ == '__main__':
    main()
i, j = map(int, input().split())
print(max(i + j, i * 2 - 1, j * 2 - 1)

### FIXED CODE ###

i, j = map(int, input().split())
print(max(i + j, i * 2 - 1, j * 2 - 1))
a,b = map(int,input().split( ))
if a>b:
    print('a > b')
elif a<b:
    print('a < b')
else: a == b:
    print('a == b')




### FIXED CODE ###

a,b = map(int,input().split( ))
if a>b:
    print('a > b')
elif a<b:
    print('a < b')
else: 
    print('a == b')
# from operator import mul
from functools import reduce


def com_init():
    for i in range(2, n):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod


def com():
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod


def modpow(a, m):
    ret = 1
    while m > 0:
        if m & 1:
            ret = ret * a % mod
        a = a * a % mod
        m = m >> 1
    return ret


def modinv(a):
    return modpow(a, mod - 2)


def cmb(n, r):
    r = min(r, n - r)
    if r == 0:
        return 1
    over = reduce(lambda a, b: a * b % mod, range(n, n - r, -1))
    under = reduce(lambda a, b: a * b % mod, range(1, r + 1))
    return over * modinv(under) % mod


x, y = [int(i) for i in input().split()]
if (x + y) % 3:
    print(0)
else:
    # n = (x + y) // 3
    # r = min((2 * x - y) // 3, (2 * y - x) // 3)
    mod = 10**9 + 7
    # fac, finv, inv = [1] * (n + 1), [1] * (n + 1), [1] * (n + 1)
    # com_init()
    # print(com())
    # print(factorial(n) // factorial(r) // factorial(n - r))
    print(cmb((x + y) // 3, (2 * x - y) // 3))


### FIXED CODE ###

from functools import reduce

def modpow(a, m):
    ret = 1
    while m > 0:
        if m & 1:
            ret = ret * a % mod
        a = a * a % mod
        m = m >> 1
    return ret

def modinv(a):
    return modpow(a, mod - 2)

def cmb(n, r):
    r = min(r, n - r)
    if r == 0:
        return 1
    over = reduce(lambda a, b: a * b % mod, range(n, n - r, -1))
    under = reduce(lambda a, b: a * b % mod, range(1, r + 1))
    return over * modinv(under) % mod

x, y = [int(i) for i in input().split()]
if (x + y) % 3 or x > 2 * y or y > 2 * x:
    print(0)
else:
    mod = 10**9 + 7
    print(cmb((x + y) // 3, (2 * x - y) // 3))
H,N=map(int,input().split())
A=[]
B=[]
for i in range(N):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)

DP=[10**9]*(H+max(A)-1)#DPの箱をH+max(A)-1個用意する

for Ai,Bi in zip(A,B):#すでにあるものを埋める
    DP[Ai-1]=Bi

for dpi in range(H+max(A)-1):
    #kouho=[]
    #kouho.append(DP[dpi])
    kouho=DP[dpi]
    for Ai,Bi in zip(A,B):
        if dpi-Ai>=0:
            if kouho<DP[dpi-Ai]+Bi:
            #kouho.append(DP[dpi-Ai]+Bi)
    DP[dpi]=kouho


print(min(DP[H-1:]))

### FIXED CODE ###

h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

max_a = max(a for a, _ in ab)
dp = [0] * (h+max_a)

for i in range(0, h+max_a):
    if i <= 0:
        dp[i] = 0
    else:
        dp[i] = min(dp[i-a] + b for a,b in ab) 

print(min(dp[h:]))
N = int(input())

odd = 0
even = 0
for i in range(N-1):
	if i % 2 == 0:
		odd += 1
	else:
		even += 1

print(odd/(even + odd))


### FIXED CODE ###

N = int(input())

odd = 0
even = 0
for i in range(N):
	if i % 2 == 0:
		odd += 1
	else:
		even += 1

print(odd/(odd + even))
n = int(input())
s = input()

l_dict = {}
r_dict = {}

for c in s:
	r_dict[c] = 0
	l_dict[c] = 0

for c in s:
	r_dict[c] += 1

ans = 0
for c in s:
	l_dict[c] += 1
	r_dict[c] -= 1

	count = 0
	for k, v in l_dict.items():
		if v > 0:
			if r_dict[k] > 0
				count += 1

	ans = max(ans, count)

print(ans)
	

### FIXED CODE ###

n = int(input())
s = input()

l_dict = {}
r_dict = {}

for c in s:
	r_dict[c] = 0
	l_dict[c] = 0

for c in s:
	r_dict[c] += 1

ans = 0
for c in s:
	l_dict[c] += 1
	r_dict[c] -= 1

	count = 0
	for k, v in l_dict.items():
		if v > 0:
			if r_dict[k] > 0:
				count += 1

	ans = max(ans, count)

print(ans)
N, A, B = [int(i) for i in input().split()]
    ans = []
    if (B-A)%2 == 0:
        print(int((B-A)/2))
    else:
        print(int((B-A)//2+1+min([A-1,N-B])))

### FIXED CODE ###

N, A, B = [int(i) for i in input().split()]
ans = []
if (B-A)%2 == 0:
    print(int((B-A)//2))
else:
    print(int((B-A)//2+1+min([A-1,N-B])))
import heapq
q = []
heapq.heapify(q)

n = int(input())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))

zeros = [False]*n
Cs = [Bs[(i-1)%n]+Bs[(i+1)%n] for i in range(n)]
Ds = [b-(c+a) for b,c,a in zip(Bs,Cs,As)]
# Dが大きい順に操作していく？
# 初期値
for i,d in enumerate(Ds):
    if d < 0: continue
    heapq.heappush(q,(-d,i))

# print("init",Bs,Cs)
cnt = 0
while len(q) > 0:
    d,i = heapq.heappop(q)
    # 自分と周りの影響を更新
    b_ = Bs[i%n] 
    c_ = Cs[i%n]
    cnt_ =  b_ // c_
    Bs[i%n] -= cnt_ * Cs[i%n]
    Cs[(i-1)%n] = Bs[(i-2)%n]+Bs[i%n]
    Cs[(i+1)%n] = Bs[(i+2)%n]+Bs[i%n]
    # 周りとの差
    d_m = Bs[(i-1)%n]-Cs[(i-1)%n]-As[(i-1)%n] 
    d_p = Bs[(i+1)%n]-Cs[(i+1)%n]-As[(i+1)%n]
    d_ = Bs[i%n] - Cs[i%n] - As[i%n]
    # print("pop",d,i,d_m,d_p)
    if d_ >= 0:
        heapq.heappush(q,(-d_,i))
    if d_m >= 0:
        heapq.heappush(q,(-d_m,i-1))
    if d_p >= 0:
        heapq.heappush(q,(-d_p,i+1))        
    # print("debug",Bs,Cs)
    cnt += cnt_
if As == Bs:
    print(cnt)
else:
    print(-1)

### FIXED CODE ###

import heapq
q = []
heapq.heapify(q)

n = int(input())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))

zeros = [False]*n
Cs = [Bs[(i-1)%n]+Bs[(i+1)%n] for i in range(n)]
# Dが大きい順に操作していく
for i, (b,c,a) in enumerate(zip(Bs,Cs,As)):
    d = b-(c+a) 
    if d < 0: continue
    heapq.heappush(q,(-d,i))

cnt = 0
while len(q) > 0:
    d,i = heapq.heappop(q)
    # 自分と周りの影響を更新
    cnt_ = (Bs[i%n]-As[i%n]) // Cs[i%n]
    Bs[i%n] -= cnt_*Cs[i%n]    
    Cs[(i-1)%n] = Bs[(i-2)%n]+Bs[i%n]
    Cs[(i+1)%n] = Bs[(i+2)%n]+Bs[i%n]
    # 周りとの差
    d_m = Bs[(i-1)%n]-Cs[(i-1)%n]-As[(i-1)%n] 
    d_p = Bs[(i+1)%n]-Cs[(i+1)%n]-As[(i+1)%n]
    if d_m >= 0:
        heapq.heappush(q,(-d_m,i-1))
    if d_p >= 0:
        heapq.heappush(q,(-d_p,i+1))
    cnt += cnt_

if As == Bs:
    print(cnt)
else:
    print(-1)
n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[10**5]*n
dp[0]=0
for i in range(2,n):
        dp[i]=min(dp[i-j]+abs(h[i-j]-h[i]) for j in range(1,k))
        print(dp[n-1])


### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[10**5]*n
dp[0]=0
for i in range(1,n):
    dp[i]=min(dp[j]+abs(h[j]-h[i]) for j in range(max(0,i-k),i))
print(dp[n-1])
l = sorted(ist(map(int, input().split())))
print(l[0] + int(str(l[1]) + str(l[2])))

### FIXED CODE ###

l = sorted(list(map(int, input().split())))
print(l[0] + int(str(l[2]) + str(l[1])))
N = int(input())
p = list(map(int, input().split()))
plen = len(p)

count = 0
for i in range(plen):
    if p[i] == i + 1:
        p[i], p[i + 1] = p[i + 1], p[i]
        count += 1
print(count)


### FIXED CODE ###

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

count = 0

for i in range(plen):
    if p[i] == i + 1:
        if p[i] == N:
            p[i - 1], p[i] = p[i], p[i - 1]
        else:
            p[i], p[i + 1] = p[i + 1], p[i]
        count += 1
    
            
print(count)
a,b = raw_input().split()
if a == 'H':
	print b
else:
	h = {'H':'C', 'C':'H'}
	print h[b]

### FIXED CODE ###

a,b = raw_input().split()
if a == 'H':
	print b
else:
	h = {'H':'D', 'D':'H'}
	print h[b]
import numpy as np
 
N = int(input())
X = [int(i) for i in input().split()]
a = np.eye(N)
b = np.roll(a, 1, axis=1)
A = a + b
 
Y = np.linalg.solve(A, X)
 
Y = list(map(lambda x: str(int(x*2)), Y))
print(' '.join(Y))

### FIXED CODE ###

a = [int(i) for i in input().split()]
x = a[0] * a[1]
y = a[2]

if (x<y):
  print(x)
else:
  print(y)
N = int(input())
xys = [[] for _ in range(N)]
for i in range(N):
    A = int(input())
    for j in range(A):
        x,y = map(int,input().split())
        xys[i].append((x-1,y))

ans = 0
for b in range(1<<N):
    cnt = bin(b).count('1')
    if cnt <= ans: continue
    for i in range(N):
        if b&(1<<i):
        for x,y in xys[i]:
                if y==1 and b&(1<<x): continue
                if y==0 and b&(1<<x)==0: continue
                break
            else:
                continue
            break
    else:
        ans = cnt
print(ans)

### FIXED CODE ###

N = int(input())
xs = [[] for i in range(N)]
for i in range(N):
    a = int(input())
    for j in range(a):
        x,y = map(int,input().split())
        xs[i].append((x-1,y))
ans = 0
for b in range(1<<N):
    mujun = False
    for k,z in enumerate(xs):
        for x,y in z:
            if b&(1<<k):
                if b&(1<<x):
                    if y==0:
                        mujun = True
                else:
                    if y==1:
                        mujun = True
            if mujun:
                break
        if mujun:
            break
    if not mujun:
        tmp = bin(b).count('1')
        ans = max(ans, tmp)
print(ans)
s = str(input())

if s[2] == s[3]:
    if s[4] == s[5]:
        print("Yes")

else:
    print("No")


### FIXED CODE ###

s = str(input())

if s[2] == s[3]:
    if s[4] == s[5]:
        print("Yes")
        quit()

print("No")
from sys import stdin
import numpy as np

N = int(stdin.readline().rstrip().split()[0])
A = [int(x) for x in stdin.readline().rstrip().split()]
# N, X = [int(x) for x in stdin.readline().rstrip().split()]

def G(_a, _b):
  if _a>=_b:
    a, b = _a, _b
  else:
    a, b = _b, _a
  
  while True:
    c = a%b
    if c == 0:
      break
    a,b = b,c
  
  return b

def func(L):
  if len(L)==1:
    return L[0]
  elif min(L)==1:
    return 1
  else:
    g = G(L[-2], L[-1])
    L[-2] = g
    L.pop()
    return func(L)
print(func(list(set(A))))
    

### FIXED CODE ###

from sys import stdin
import numpy as np

N = int(stdin.readline().rstrip().split()[0])
A = [int(x) for x in stdin.readline().rstrip().split()]
# N, X = [int(x) for x in stdin.readline().rstrip().split()]

def G(_a, _b):
  if _a>=_b:
    a, b = _a, _b
  else:
    a, b = _b, _a
  
  while True:
    c = a%b
    if c == 0:
      break
    a,b = b,c
  
  return b

L = np.array(list(set(A)))
mini = np.min(L)
yaku = [1]
i=2
r_mini = np.sqrt(mini)
while i<=r_mini:
  if mini%i==0:
    yaku.append(i)
  i+=1
yaku2 = list(map(lambda x: int(mini/x), yaku))
yaku = yaku[::-1]
yaku2.extend(yaku)
for y in yaku2:
  if np.sum(L%y)==0:
    ans = y
    break

print(ans)
import sys
import math

def prime_calc(n):
    rootN = math.floor(math.sqrt(n))
    prime = [2]
    data = [i + 1 for i in range(2,n,2)]
    while True:
        p = data[0]
        if rootN < p:
            return len(prime + data)
        prime.append(p)
        data = [e for e in data if e % p != 0]

def main():
    l = []

    for line in sys.stdin:
        l.append(int(line))

    for line in l:
        print(prime_calc(line))

if __name__ == "__main__":
    main()


### FIXED CODE ###

import math
import sys

sup = 1000000

is_prime = [0] * sup

count = [0] * sup

def setup():
    is_prime[2] = 1
    for n in range(3,sup,2):
        flag = True
        for i in range(3, int(math.floor(math.sqrt(n) + 1)), 2):
            if n % i == 0:
                flag = False
                break
        if flag:
            is_prime[n] = 1

def precount():
    for n in range(2, sup):
        count[n] = count[n-1] + is_prime[n]

def main():
    setup()
    precount()

    l = []

    for line in sys.stdin:
        l.append(int(line))

    for line in l:
         print(count[line])

if __name__ == "__main__":
    main()
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long
#define All(v) (v).begin(),(v).end()
int main() {
    string s,t;
    int ans=0;
    cin>>s>>t;
    rep(i,3){
        if(s[i]==t[i])ans++;
    }
    cout<<ans<<endl;
}


### FIXED CODE ###

s=input()
t=input()
ans=0
for i in range(3):
    if s[i]==t[i]:
        ans+=1
print(ans)
# そのまま入力文字列の入力
n = int(input())

# 空白区切りの数値をリスト化
an = list(map(int, input().split()))

ans = 0


def search_and_break(blocks, target):
    global  ans
    position = 0
    if len(blocks) == 0:
        return ans

    for i in range(0, len(blocks)):
        if blocks[i] == target:
            return search_and_break(blocks[(position+1):], target + 1)
        else:
            ans += 1
            position += 1

    return -1


print(search_and_break(an, 1))

### FIXED CODE ###

# そのまま入力文字列の入力
n = int(input())

# 空白区切りの数値をリスト化
an = list(map(int, input().split()))

ans = 0

target = 1
has_ans = False
for i in range(0, n):
    if an[i] == target:
        has_ans = True
        target += 1
    else:
        ans += 1

print(ans if has_ans else "-1")
n=int(input())
h=list(map(int,input().split()))
dp=[0]*n
dp[0]=0
dp[1]=abs(h[1]-h[0])
dp[2]=min(abs(h[1]-h[0]),abs(h[2]-h[0]))
for i in range(3,n):
    dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]))
print(dp[n-1])


### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
dp=[0]*n
dp[0]=0
dp[1]=abs(h[1]-h[0])
for i in range(2,n):
  dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]))
print(dp[n-1])
import bisect
N = int(input())
An = list(map(int,input().split(' '))) 

bit_list = [1]
for i in range(100000):
    bit_list.append(bit_list[i]*2)
    if bit_list[i+1] > 10**12:
        break
start_point = bisect.bisect_right(bit_list,max(An))
keta_list = [0] * start_point

for A in An:
    abin = format(A, 'b')
    for i in range(len(abin)):
        if abin[i] == '1':
            keta_list[len(abin)-1-i] += 1
count = 0
for idx,keta_count in enumerate(keta_list):
    count += (N-keta_count) * bit_list[idx] * keta_count
    count = count % (1000000000+7)
print(count)

### FIXED CODE ###

import bisect
N = int(input())
An = list(map(int,input().split(' '))) 

bit_list = [1]
for i in range(100000):
    bit_list.append(bit_list[i]*2)
    if bit_list[i+1] > 2**60:
        break
start_point = bisect.bisect_right(bit_list,max(An))
keta_list = [0] *  start_point

for A in An:
    abin = format(A, 'b')
    for i in range(len(abin)):
        if abin[i] == '1':
            keta_list[len(abin)-1-i] += 1
count = 0
for idx,keta_count in enumerate(keta_list):
    count += (N-keta_count) * bit_list[idx] * keta_count
    count = count % (1000000000+7)
print(count)
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from collections import Counter

def main():
    N = II()
    A = LI()
    idxs = [0] * N
    for i, a in enumerate(A):
        idxs[a] = i
    def func(arr):
        if len(arr) == 0:
            return 0
        a = min(arr)
        idx = idxs[a]
        return (idx + 1) * (len(arr) - idx) * a + func(arr[:idx]) + func(arr[idx + 1:])
    ans = func(A)

    return ans

print(main())


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from collections import Counter

def main():
    N = II()
    A = LI()
    idxs = [0] * (N + 1)
    for i, a in enumerate(A):
        idxs[a] = i
    ll = list(range(N + 1))
    rr = list(range(N + 1))
    ans = 0
    for a in range(N, 0, -1):
        idx = idxs[a]
        l, r = ll[idx], rr[idx]
        ans += (idx - l + 1) * (r - idx + 1) * a
        ll[r + 1] = l
        rr[l - 1] = r

    return ans

print(main())