Harryxun/stf_run huggingface dataset:
#!/usr/bin python3
# -*- coding: utf-8 -*-

####################################################
# LCS(longest common sequence)
# 部分列で最長の共通のもの
####################################################

# dp[i+1][j+1]:= s の i 文字目までと t の j 文字目まででの LCS の長さ

def main():
    S = input()
    T = input()
    ls = len(S)
    lt = len(T)

    dp = [[0]*(lt+1) for _ in range(ls+1)]
    for i in range(ls):
        for j in range(lt):
            if S[i]==T[j]:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1], dp[i][j]+1)
            elif:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
#    print(dp)
#    print(dp[ls][lt])

    # 復元
    res = ''
    i, j = ls, lt
    while (i > 0 and j > 0):
        # (i-1, j) -> (i, j) と更新されていた場合
        if dp[i][j] == dp[i-1][j]:
            i-=1   # DP の遷移を遡る
        # (i, j-1) -> (i, j) と更新されていた場合
        elif dp[i][j] == dp[i][j-1]:
            j-=1   # DP の遷移を遡る
        # (i-1, j-1) -> (i, j) と更新されていた場合
        else:
            res = S[i-1] + res
            # このとき s[i-1] == t[j-1] なので、t[j-1] + res でも OK
            i-=1
            j-=1   # DP の遷移を遡る
    print(res)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

####################################################
# LCS(longest common sequence)
# 部分列で最長の共通のもの
####################################################

# dp[i+1][j+1]:= s の i 文字目までと t の j 文字目まででの LCS の長さ

import numpy as np

def main():
    S = np.array(list(input()), dtype='unicode')
    T = np.array(list(input()), dtype='unicode')
    ls = len(S)
    lt = len(T)

    equal = S[:, None] == T[None,:]
#    print(eq)

    dp = np.zeros((ls + 1, lt + 1), dtype=int)

    for i in range(ls):
        dp[i + 1][1:] = np.maximum(dp[i][1:], dp[i][:-1] + equal[i])
        dp[i + 1] = np.maximum.accumulate(dp[i + 1])

#    for i in range(ls):
#        for j in range(lt):
#            dp[i+1][j+1] = max(dp[i][j+1], dp[i][j]+ eq[i][j])
#            dp[i+1][j+1] = max(dp[i+1][j+1] , dp[i+1][j])

#    print(dp)

    # 復元
    res = ''
    i, j = ls, lt
    while (i > 0 and j > 0):
        # (i-1, j) -> (i, j) と更新されていた場合
        if dp[i][j] == dp[i-1][j]:
            i-=1   # DP の遷移を遡る
        # (i, j-1) -> (i, j) と更新されていた場合
        elif dp[i][j] == dp[i][j-1]:
            j-=1   # DP の遷移を遡る
        # (i-1, j-1) -> (i, j) と更新されていた場合
        else:
            res = S[i-1] + res
            # このとき s[i-1] == t[j-1] なので、t[j-1] + res でも OK
            i-=1
            j-=1   # DP の遷移を遡る
    print(res)

if __name__ == '__main__':
    main()
import sys
readline=sys.stdin.readline

n=int(readline().strip())
a=[int(readline().strip()) for _  in range(n)]
l=[0]*(max(a)+1)
for x in a:
  l[x]^=1
print(sum(l))


### FIXED CODE ###

import sys
from collections import Counter
read=sys.stdin.read

n,*a=map(int,read().split())
x=Counter(a)
print(sum(list(map(lambda n:n%2, list(x.values())))))
k = int(input())
a = int(input())
b = int(input())

for i in range(a,b+1):
  if i % k == 0:
    print("OK")
    break
else :
  print("NG")


### FIXED CODE ###

k = int(input())
abs = [int(e) for e in input().split()]

for i in range(abs[0],abs[1]+1):
  if i % k == 0:
    print("OK")
    break
else :
  print("NG")
import itertools
L, R = map(int, input().split())
 
remainder_list = []
for N in range(L, R+1):
  remainder_list.append(N%2019)

for i, j in list(itertools.combinations(remainder_list, 2)):
  all_list.append((i*j)%2019)
  
print(min(all_list))

### FIXED CODE ###

import itertools
L, R = map(int, input().split())

if R - L + 1 > 2019:
    remainder_list = [N%2019 for N in range(L, L+2019)]
else:
    remainder_list = [N%2019 for N in range(L, R+1)]  
remainder_list = list(set(remainder_list))
all_list = [(i*j)%2019 for i, j in list(itertools.combinations(remainder_list, 2))]
print(min(all_list))
def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

N=one_int()
S=one_str()

def ran(S, N):
    bit_count = S.count("1")

    #bit数
    calc_dict = {i:-1 for i in range(22000)}
    res_dict =  {i:-1 for i in range(2*(10**5))}

    res_dict = {i:-1 for i in range(1001)}
    res_dict[0]=0

    for i in range(1, 1001):
        if calc_dict[i]==-1:
            calc_dict[i] = bin(i).count("1")

        res_dict[i] = i%calc_dict[i]+1


    bit_count = S.count("1")
    for i in range(len(S)):
        if S[i]=="0":

            bit_count+=1
            num = int(S,2) + 2**(N-i-1)
            if num<=0:
                print(0)
            else:
                print(res_dict[num%bit_count]+1)
            bit_count-=1
        else:

            bit_count-=1
            num = int(S,2) - 2**(N-i-1)
            if num<=0:
                print(0)
            else:
                print(res_dict[num%bit_count]+1)
            bit_count+=1

ran(S,N)

### FIXED CODE ###

def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

N=one_int()
S=one_str()

bit_count = S.count("1")
S_num = int(S,2)
S_min = S_num % (bit_count-1) if bit_count-1!=0 else 0
S_plu = S_num % (bit_count+1)




# calc_dict = {i:-1 for i in range(10000)}
# res_dict =  {i:-1 for i in range(10**4)}

# for i in range(1, 10000):
#     if calc_dict[i]==-1:
#         calc_dict[i] = bin(i).count("1")

#     res_dict[i] = i%calc_dict[i]+1

def mods(temp, count):
    count+=1
    if temp!=0:

#         if temp in res_dict:
#             return count+res_dict[temp]
        
#         if temp not in calc_dict:
#             calc_dict[temp]= bin(temp).count("1") 
        count = mods(temp%bin(temp).count("1") , count)

    return count

for i in range(N):
    if S[i]=="0":
        part = pow(2, (N-i-1), bit_count+1)
        num = (S_plu + part ) % (bit_count+1)
        print(mods(num, 0))
    else:
        if S_num == 2**(N-i-1):
            print(0)
            continue
        part = pow(2, (N-i-1), bit_count-1)
        num = (S_min - part)%(bit_count-1)
        print(mods(num, 0))
def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)

def lcm(l):
    def aux(l, i):
        if i == len(l) - 1:
            return l[-1]
        rest = aux(l, i+1)
        return l[i] * rest // gcd(l[i], rest)
    return aux(l, 0)

def modsum(a):
    k = lcm(a) - 1
    return sum(map(lambda x: k % x, a))

if __name__ == '__main__':
    _ = input()
    a = list(map(int, input().split()))
    print(modsum(a))

### FIXED CODE ###

import sys

sys.setrecursionlimit(3100)

def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)

def lcm(l):
    def aux(l, i):
        if i == len(l) - 1:
            return l[-1]
        rest = aux(l, i+1)
        return l[i] * rest // gcd(l[i], rest)
    return aux(l, 0)

def modsum(a):
    k = lcm(a) - 1
    return sum(map(lambda x: k % x, a))

if __name__ == '__main__':
    _ = input()
    a = list(map(int, input().split()))
    print(modsum(a))
# encoding: "utf-8"

from collections import defaultdict

class Stdin:
    @staticmethod
    def read_line(converter=str):
        return [converter(x) for x in input().split()]
    
    @staticmethod
    def read_lines(n, converter=str):
        result = list()
        for _ in range(n):
            result.append(Stdin.read_line(converter))
        return result
    
    @staticmethod
    def convert(data, converter):
        assert(len(data) == len(converter))
        return tuple(map(lambda x, f: f(x), data, converter))

    @staticmethod
    def convert_lines(datas, n, converter):
        return [converter(data, n, converter) for data in datas]


def count_and_del(xs):
    cnt = 0
    fst = xs[-1]
    for x in reversed(xs):
        if x != fst:
            break
        cnt += 1
    del xs[cnt:]
    return cnt   


def main():
    _ = input()
    xs = Stdin.read_line(converter=int)
    xs.sort(reverse=True)
    ys = defaultdict(int)
    while xs:
        key = xs[0]
        cnt = count_and_del(xs)
        ys[key] += cnt
        ys[key-1] += cnt
        ys[key+1] += cnt

    print(max(ys.values()))


if __name__ == "__main__":
    main()

### FIXED CODE ###

# encoding: "utf-8"

class Stdin:
    @staticmethod
    def read_line(converter=str):
        return [converter(x) for x in input().split()]
    
    @staticmethod
    def read_lines(n, converter=str):
        result = list()
        for _ in range(n):
            result.append(Stdin.read_line(converter))
        return result
    
    @staticmethod
    def convert(data, converter):
        assert(len(data) == len(converter))
        return tuple(map(lambda x, f: f(x), data, converter))

    @staticmethod
    def convert_lines(datas, n, converter):
        return [converter(data, n, converter) for data in datas]


def main():
    x, t = Stdin.read_line(converter=int)
    r = x - t
    if r < 0:
        r = 0
    print(r)

if __name__ == "__main__":
    main()
A, B, C, D = [int(input()) for i in range(4)]
if A+B>C+D:
  print('Left')
elif A+B==C+D:
  print('Balanced')
elif A+B<C+D:
  print('Right')


### FIXED CODE ###

A,B,C,D = map(int, input().split())
if A+B>C+D:
  print('Left')
elif A+B==C+D:
  print('Balanced')
elif A+B<C+D:
  print('Right')
N,M=map(int,input().split())
ans=[0 for i in range(N)]
for i in range(M):
  a=int(input())
  ans[a-1]=-1
mod=10**9+7
if ans[0]==-1 and ans[1]==-1:
  print(0)
  exit()
if ans[0]!=-1 and ans[1]==-1:
  ans[0]=1
if ans[0]==-1 and ans[1]!=-1:
  ans[1]=1
else:
  ans[0]=1
  ans[1]=2
for i in range(N-2):
  if ans[i+2]==-1:
    pass
  else:
    if ans[i]==-1 and ans[i+1]==-1:
      print(0)
      exit()
    if ans[i]==-1 and ans[i+1]!=-1:
      ans[i+2]=ans[i+1]
    if ans[i]!=-1 and ans[i+1]==-1:
      ans[i+2]=ans[i]
    if ans[i]!=-1 and ans[i+1]!=-1:
      ans[i+2]=(ans[i+1]+ans[i])%mod
print(ans[N-1])


### FIXED CODE ###

N,M=map(int,input().split())
ans=[0 for i in range(N+1)]
true=[True for i in range(N+1)]
for i in range(M):
  a=int(input())
  true[a]=False
mod=10**9+7
ans[0]=1
ans[1]=1
for i in range(2,N+1):
  for j in range(i-2,i):
    if true[j]:
      ans[i]+=ans[j]%mod
print(ans[N]%mod)
A, B, C = input().split(" ")
 
D = A - B

 
if C - D <= 0:
  print(0)
else:
  print(C-D)


### FIXED CODE ###

A, B, C = (int(i) for i in input().split(" "))
 
D = A - B

 
if C - D <= 0:
  print(0)
else:
  print(C-D)
lst = []
N = int(input("Enter number of elements : "))
for i in range(0,N):
    lst.append(int(input()))
temp = [x for x in lst if lst.count(x)>1]
list_set = set(temp)
dups = (list(list_set))
if (len(dups)<2):
   print('0')
   print('No rectangle can be formed')
else:
    a = dups[0]; b = dups[1]
    n=len(dups)    
    for i in range(0, n):
      for j in range(i + 1, n):
        if (dups[i]*dups[j]>a*b):
             a = dups[i]
             b = dups[j]
    print(a*b)
    print(a,' times ',b,' rectangle can be formed')

### FIXED CODE ###

n=int(input())
a=[int(x) for x in input().split()]
a.sort()
lar=sec=i=0
while(i<n-1):
    if a[i]==a[i+1]:
        i+=1
        if a[i]>lar:
            sec=lar
            lar=a[i]
        elif a[i]>sec:
             sec=a[i]
    i+=1
print(lar*sec)
import sys
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
\# input処理を高速化する
input = sys.stdin.readline

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

lst_edge = [[] for _ in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    lst_edge[x-1].append(y-1)

dp = [-1] * N

# rec(v) 頂点vを始点としたとき有効パスの長さの最大値
def rec(v):
    #print(dp, v)
    if dp[v] != -1:
        return dp[v] # 既に更新済み

    ans = 0
    lst_nv = lst_edge[v]
    for nv in lst_nv:
        ans = max(ans, rec(nv) + 1)
    dp[v] = ans # メモしながらリターン
    return dp[v]

ans_memo = 0
for i in range(N):
    ans_memo = max(ans_memo, rec(i))

print(ans_memo)

### FIXED CODE ###

import sys
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
# input処理を高速化する
input = sys.stdin.readline

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

lst_edge = [[] for _ in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    lst_edge[x-1].append(y-1)

dp = [-1] * N

# rec(v) 頂点vを始点としたとき有効パスの長さの最大値
def rec(v):
    #print(dp, v)
    if dp[v] != -1:
        return dp[v] # 既に更新済み

    ans = 0
    lst_nv = lst_edge[v]
    for nv in lst_nv:
        ans = max(ans, rec(nv) + 1)
    dp[v] = ans # メモしながらリターン
    return dp[v]

ans_memo = 0
for i in range(N):
    ans_memo = max(ans_memo, rec(i))

print(ans_memo)
n, z, w = map(int, input().split())
a = list(map(int, input().split()))

print(max(abs(a[n-1] - w), abs(a[n-2] - a[n-1])

### FIXED CODE ###

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

print(max(abs(a[n-1] - w), abs(a[n-2] - a[n-1])))
import fractions
def main():
    n,m=map(int,input().split())
    s=input()
    t=input()
    ans=-1
    gcd0=fractions.gcd(n,m)
    lcm=n*m//gcd0
    flg=1
    for i in range(gcd0):
        if s[n*i//gcd0]!=t[m*i//gcd0]:
            flg=0
            break
    if flg==1:
        ans=lcm
print(ans)
if __name__=="__main__":
    main()

### FIXED CODE ###

import fractions
def main():
    n,m=map(int,input().split())
    s=input()
    t=input()
    ans=-1
    gcd0=fractions.gcd(n,m)
    lcm=n*m//gcd0
    flg=1
    for i in range(gcd0):
        if s[n*i//gcd0]!=t[m*i//gcd0]:
            flg=0
            break
    if flg==1:
        ans=lcm
    print(ans)
if __name__=="__main__":
    main()
a, b, c, d = int(input())

train = [a,b]
bus = [c,d]

print(min(train) + min(bus))

### FIXED CODE ###

A = int(input())
B = int(input())
C = int(input())
D = int(input())

train = [A,B]
bus = [C,D]

print(min(train) + min(bus))
n=int(input())
p=list(map(int,input().split()))
ct=1
maxn=p.index(1)
while True:
    if maxn==0:
        break
    p=p[0:maxn]
    i+=1
    maxn=p.index(min(p))
    ct+=1
print(ct)

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
ct=1
minn=p[0]
for i in range(1,n):
    if minn==1:
        #ct+=1
        break
    elif minn>p[i]:
        minn=p[i]
        ct+=1
print(ct)
s = str(input())
j = list(set(list(s)))
c1 = j[0]
c2 = j[1]
if len(j) == 2 and s.count(c1) == 2 and s.count(c2) == 2:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s = str(input())
j = list(set(list(s)))
c1 = j[0]
try:
    c2 = j[1]
except:
    print("No")
    exit()
if len(j) == 2 and s.count(c1) == 2 and s.count(c2) == 2:
    print("Yes")
else:
    print("No")
S = input()
print("No" if S.count(A) == 3 or S.count(B)  ==3 else "Yes")

### FIXED CODE ###

S = input()
print("No" if S.count("A") == 3 or S.count("B")  ==3 else "Yes")
from scipy.special import comb

### FIXED CODE ###

#156D
p=7+10**9
def comb(n,r):
  bunshi = 1
  for i in range(n-r+1, n+1):
    bunshi =bunshi * i % p
  bunbo = 1
  for i in range(1, r+1):
    bunbo = bunbo * i % p
  return bunshi * pow(bunbo, p-2, p)
n,a,b=map(int,input().split())
s=-1+pow(2,n,p)-comb(n,a)-comb(n,b)
print(s%p)
s,t=input().splitlines()
c=0
for i in range(3):
  if s[i]==t[i]:c+=1
print(c)

### FIXED CODE ###

s=input()
t=input()
c=0
for i in range(3):
  if s[i]==t[i]:c+=1
print(c)
n, m = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

key = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
#k = [1, 7, 4, 5, 3, 2, 9, 6, 8]

dpi = [-1<<50] * 9 + [0]
def dp(i):
    '''i should be started from 1'''

    ans = []
    for j in a:
        ans.append(dpi[len(dpi) - key[j]] + 1)
    dpi.append(max(ans))

    if i == n:
        return dpi[len(dpi) - 1]
    else:
        return dp(i + 1)

i = dp(1)
a.sort()

s = ''
cur = -1
for j in range(i):
    for k in reversed(a):
        if dpi[cur-key[k]] == dpi[cur] - 1:
            s += str(k)
            cur -= key[k] 
            break
        else:
            continue

print(int(s))


### FIXED CODE ###

import sys
sys.setrecursionlimit(15000)

n, m = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

key = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
#k = [1, 7, 4, 5, 3, 2, 9, 6, 8]

dpi = [-1<<50] * 9 + [0]
def dp(i):
    '''i should be started from 1'''

    ans = []
    for j in a:
        ans.append(dpi[len(dpi) - key[j]] + 1)
    dpi.append(max(ans))

    if i == n:
        return dpi[len(dpi) - 1]
    else:
        return dp(i + 1)

i = dp(1)
a.sort()

s = ''
cur = -1
for j in range(i):
    for k in reversed(a):
        if dpi[cur-key[k]] == dpi[cur] - 1:
            s += str(k)
            cur -= key[k] 
            break
        else:
            continue

print(int(s))
K, S = map(int, input().split())

count = 0
for x in K+1:
  for y in K-x:
    z = K - x - y
    if (x>=0) and (y>=0) and (z>=0):
      count += 1
      
print(count)

### FIXED CODE ###

K, S = map(int, input().split())
 
count = 0

for x in range(K+1):
  for y in range(K+1):
    z = S - x - y
    if (z>=0) and (z<=K):
      count += 1

print(count)
# -*- coding: utf-8 -*-

import sys

for i in sys.stdin:
    a, b, c, d, e, f = map(int, line.split())
    print "%f %f" %((d*c-a*f)/(b*d-a*e), (b*f-c*e)/(b*d-a*e))

### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys

for line in sys.stdin:
    a, b, c, d, e, f = map(float, line.split())
    print "%.3f %.3f" %(round(b*f-c*e)/(b*d-a*e)+0, (c*d-a*f)/(b*d-a*e)+0)
n = int(input())
A = [map(int,input().split())]
print(max(A) - min(A))


### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
print(max(A) - min(A))
# -*- coding: utf-8 -*-
a, b, c = map(int, raw_input().split())
sum = a+b+C
if sum == 17:
  	print "YES"
else 
	print "NO"


### FIXED CODE ###

# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
a, b, c = map(int, raw_input().split())
sum = a+b+c
if sum == 17:
  print "YES"
else: 
  print "NO"
N, K = map(int, input().split())
P = map(int, input().split())

P.sort()
s = 0
for i in range(K):
	s += P[i]

print(s)

### FIXED CODE ###

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

P.sort()
s = 0
for i in range(K):
	s += P[i]

print(s)
s = list(input())
t = list(input())
ing_total = 0

for x in range(2):
    if s[x] == t[x]:
        ing_total+=1
    else:
        ing_total+=0
     print(ing_total)



### FIXED CODE ###

s = list(input())
t = list(input())
ing_total = 0

for x in range(3):
    if s[x] == t[x]:
        ing_total+=1
    else:
        ing_total+=0
print(ing_total)
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,k,c = LI()
s = input()
t = []
for i in range(n):
    if s[i] == 'o':
        t.append(1)
    else:
        t.append(0)

r = [False]*n
l = [False]*n
flag = True
for i in range(n):
    if flag and t[i] == 1:
        flag = False
        l[i] = True
        cnt = 0
        continue
    elif not flag and cnt == c-1:
        flag = True
    cnt += 1

flag = True
for i in range(n)[::-1]:
    if flag and t[i] == 1:
        flag = False
        r[i] = True
        cnt = 0
        continue
    elif not flag and cnt == c-1:
        flag = True
    cnt += 1

for i in range(n):
    if r[i] and l[i]:
        print(i+1)

### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,k,c = LI()
s = input()
l,r = [0]*k, [0]*k
i = 0
cnt = 0
while i < n:
    if s[i] == 'o':
        if cnt >= k:
            quit()
        l[cnt] = i
        cnt += 1
        i += c
    i += 1
i = n-1
cnt = k-1
while i >= 0:
    if s[i] == 'o':
        if cnt < 0:
            quit()
        r[cnt] = i
        cnt -= 1
        i -= c
    i -= 1
for i in range(k):
    if l[i] == r[i]:
        print(l[i]+1)
H,N=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(N)]
x=max(a for a,b in ab)
dp=[0]*(H+10)
for i in range (1,H+1):
    dp[i]=min(dp[i-a]+b for a,b in ab)
print(dp[H])

### FIXED CODE ###

H,N=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(N)]
x=max(a for a,b in ab)
dp=[0]*(H+x)
for i in range (1,H+x):
    dp[i]=min(dp[i-a]+b for a,b in ab)
print(dp[H])
# coding=utf-8

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    A_modify = [A[j] - j - 1 for j in range(N)]
    A_modify.sort()

    if N % 2 == 0:
        mid1 = A_modify[N//2]
        mid2 = A_modify[mid1-1]
        A_modify1 = [abs(elm - mid1) for elm in A_modify]
        A_modify2 = [abs(elm - mid2) for elm in A_modify]
        print(min(sum(A_modify1), sum(A_modify2)))
    else:
        mid = N//2
        b = A_modify[mid]
        A_modify = [abs(elm - b) for elm in A_modify]
        print(sum(A_modify))


### FIXED CODE ###

# coding=utf-8

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    A_modify = [A[j] - j - 1 for j in range(N)]
    A_modify.sort()

    mid1 = A_modify[N//2]
    A_modify1 = [abs(elm - mid1) for elm in A_modify]
    print(sum(A_modify1))
S = list(str(input()))

count = 0
count_bef = 0
count_list=[]
count_list2=[]
minus = []
for i in range(len(S)-1):
  if S[i] == S[i+1]:
    count += 1
  elif not S[i] ==S[i+1]:
    count_list.append(int((count+1)*(count+2)/2))
    count_list2.append(count+1)
    count = 0
count_list.append(int((count+1)*(count+2)/2))
count_list2.append(count+1)
if S[0] == "<":
  for i in range(len(count_list2)//2):
    minus.append(min(count_list2[2*i], count_list2[2*i+1]))
elif S[0] == ">":
  for i in range(len(count_list2)//2):
    minus.append(min(count_list2[2*i+1], count_list2[2*i+2]))
    
#print(count_list)
#print(count_list2)
#print(minus)
print(sum(count_list)-sum(minus))

### FIXED CODE ###

S = list(str(input()))

count = 0
count_bef = 0
count_list=[]
count_list2=[]
minus = []
for i in range(len(S)-1):
  if S[i] == S[i+1]:
    count += 1
  elif not S[i] ==S[i+1]:
    count_list.append(int((count+1)*(count+2)/2))
    count_list2.append(count+1)
    count = 0
count_list.append(int((count+1)*(count+2)/2))
count_list2.append(count+1)
if S[0] == "<":
  for i in range(len(count_list2)//2):
    minus.append(min(count_list2[2*i], count_list2[2*i+1]))
elif S[0] == ">":
  try:
    for i in range(len(count_list2)//2):
      minus.append(min(count_list2[2*i+1], count_list2[2*i+2]))
  except IndexError:
    pass
#print(count_list)
#print(count_list2)
#print(minus)
print(sum(count_list)-sum(minus))
n = int(raw_input())
minv = int(raw_input())
maxv = -1*10**9
  
for j in range(n-1):
  nums = int(raw_input())  
  diff = nums - minv
  if maxv < diff:
    maxv = diff
  if num < minv:
    minv = nums
  
print maxv

### FIXED CODE ###

n = int(raw_input())
minv = int(raw_input())
maxv = -1*10**9
  
for j in range(n-1):
  nums = int(raw_input())  
  diff = nums - minv
  if maxv < diff:
    maxv = diff
  if nums < minv:
    minv = nums
  
print maxv