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

n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[1e9]*(n+k)
dp[0]=0
for i in range(n):
    for j in range(1,k+1):
        if i+j<n:
                dp[i+j]=min(dp[i+j],abs(a[i]-a[i+j])+dp[i])
print(dp[n-1])

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[1e9]*(n+k)
dp[0]=0
for i in range(n):
    for j in range(1,k+1):
        if i+j<n:
                dp[i+j]=min(dp[i+j],abs(a[i]-a[i+j])+dp[i])
print(dp[n-1])
### BUGGY CODE ###

from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    dist = [-1] * (w * h)
    que, frag = deque(), set()
    quead, fragad = que.append, frag.add
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[j + (w * i)] = 0
                quead((i, j)), fragad((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if (i, j) in frag:  # 処理済みか否か
                continue
            if 0 <= i < h and 0 <= j < w:
                dist[j + (w * i)] = dist[y + (w * x)] + 1
                quead((i, j)), fragad((i, j))
    return max(dist)


h, w = map(int, input().split())
a = [input() for _ in range(h)]
print(bfs(a))


### FIXED CODE ###

from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    dist = [[-1] * w for _ in range(h)]  # 前処理
    que = deque()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[i][j] = 0
                que.append((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if 0 <= i < h and 0 <= j < w and dist[i][j] < 0:
                dist[i][j] = dist[x][y] + 1
                que.append((i, j))
    return dist[x][y]


h, w = map(int, input().split())
a = [input() for _ in range(h)]
print(bfs(a))
### BUGGY CODE ###

n = int(input())
vlist = list(map(int, input().split()))


a = sorted(vlist[::2], key=vlist[::2].count, reverse=True)
b = sorted(vlist[1::2], key=vlist[1::2].count, reverse=True)


freq_a = a.count(a[0])
freq_b = b.count(b[0])


x = len(a) - freq_a
y = len(b) - freq_b


if len(set(vlist)) == 1:
    print(min(len(a), len(b)))
else:
    print(x+y)


### FIXED CODE ###

from collections import Counter

n = int(input())
vlist = list(map(int, input().split()))

# most_commonを使うためにリストをCounterオブジェクトに渡す
Counter_evens = Counter(vlist[::2])
Counter_odds = Counter(vlist[1::2])


# even_indexes
top2_even = Counter_evens.most_common(2)  # [(一番多い要素,その出現回数),(2番目に多い要素,その出現回数)]

E_most_common = top2_even[0][0]
Emnum = top2_even[0][1]

if len(top2_even) == 2:
    E_2nd_common = top2_even[1][0]
    E2num = top2_even[1][1]
else:
    E_2nd_common = 'foo'
    E2num = 0

# odd_indexes
top2_odd = Counter_odds.most_common(2)

O_most_common = top2_odd[0][0]
Omnum = top2_odd[0][1]

if len(top2_odd) == 2:
    O_2nd_common = top2_odd[1][0]
    O2num = top2_odd[1][1]
else:
    O_2nd_common = 'foo'
    O2num = 0


if E_most_common == O_most_common:  # most commonどうしが衝突してしまっている。
    # もし偶数番目・奇数番目をどちらもmost commonに書き換えると、3つ目の条件「数列は1種類の数ではだめ」が満たされない。
    # なので奇数番目・偶数番目のどちらかは2番目に多いやつに書き換える必要がある

    # 偶数番目をmost commonに、oddsを2nd commonにそろえる場合に書き換えないといけない要素の数
    x = len(vlist[::2]) - Emnum + len(vlist[1::2]) - O2num
    # 逆の場合
    y = len(vlist[::2]) - E2num + len(vlist[1::2]) - Omnum

    print(min(x, y))
else:
    # most common は衝突していない、つまり異なる数。よって3つ目の条件「数列は1種類の数ではだめ」は満たされている。
    # 両方とも most commonに書き換えてOK
    print(len(vlist[::2]) - Emnum + len(vlist[1::2]) - Omnum)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7

table = [0] * 60

for a in A:
    for i in range(60):
        if (a>>i) & 1:
            table[i] += 1

ans = 0
for i ,t in enumerate(table):
    ans += t * (N-t) * 2**i
    ans %= MOD
print(ans)

### FIXED CODE ###

import numpy as np
MOD = 10**9+7
N = int(input())
A = list(map(int,input().split(' ')))
A = np.array(A)

ans = 0
for i in range(60):
    c_1 = int((A&1).sum())
    ans += c_1*(N-c_1)*(2**i)
    A >>= 1

print(ans%MOD)
### BUGGY CODE ###

#! python3
# coding:utf-8
 
def main():
    n = int(input())
    for i in range(1,n+1):
        cnt=0
        for x in range(1,100):
            for y in range(1,100):
                for z in range(1,100):
                    if (x+y+z)>=i:
                        continue
                    eq = x**2 + y**2 + z**2 + x*y + y*z + z*x
                    if eq == i:
                        cnt+=1
        print(cnt)

if __name__ == "__main__":
    main() 

### FIXED CODE ###

#! python3
# coding:utf-8
 
def main():
    n = int(input())
    ans = [0 for _ in range(n)]
    for x in range(1,100):
        for y in range(1,100):
            for z in range(1,100):
                eq = x**2 + y**2 + z**2 + x*y + y*z + z*x
                if eq < n+1:
                    ans[eq-1]+=1
    for i in ans:   
        print(i)

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

s = input()
s2 = s
while "01" in s2 or "10" in s2:
    if "01" in s2:
        s2 = s2.replace("01", "")
    elif "10" in s2:
        s2 = s2.replace("10", "")

print(len(s) - len(s2))

### FIXED CODE ###

s = input()
ans = min(s.count("0"), s.count("1")) * 2
print(ans)
### BUGGY CODE ###

def half_enumeration(a, *, func):
    """正しい英訳は不明"""
    n = len(a)
    h = n // 2

    def enum(h, *, second_half: bool = False):
        p = set()
        if second_half:
            b = a[h:]
        else:
            b = a[:h]

        for x in b:
            q = set()
            for e in p:
                q.add(func(e, x))
            p.add(x)
            p.update(q)
        return p

    return enum(h), enum(h, second_half=True)


def main():
    from itertools import chain, starmap
    from operator import add

    INF = 40 * 100 + 1

    N, Ma, Mb = map(int, input().split())

    def update(e, x):
        return tuple(starmap(add, zip(e, x)))

    xcs = []
    for _ in range(N):
        ai, bi, ci = map(int, input().split())
        x = Ma * bi - Mb * ai  # Σai:Σbi=Ma:Mb<->Ma*Σbi-Mb*Σai=0
        xcs.append((x, ci))

    p1, p2 = half_enumeration(xcs, func=update)

    ans = INF
    for x, c in chain(p1, p2):
        if x == 0 and ans > c:
            ans = c
    for x1, c1 in p1:
        for x2, c2 in p2:
            if x1 + x2 == 0 and ans > c1 + c2:
                ans = c1 + c2
    print(-1 if ans == INF else ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

N, Ma, Mb = map(int, input().split())
e = [tuple(map(int, input().split())) for _ in range(N)]

N_max = 40
a_max = 10
b_max = 10
c_max = 100

inf = N_max * c_max + 1
dp = [[[inf for _ in range(N_max * b_max + 1)] for _ in range(N_max * a_max + 1)] for _ in range(N_max + 1)]
dp[0][0][0] = 0

# print(dp[N])

for i, (aa, bb, cc) in enumerate(e, 1):
    for a in range(a_max * i + 1):
        for b in range(b_max * i + 1):
            dp[i][a][b] = min(dp[i][a][b], dp[i - 1][a][b])
            if a + aa < N_max * a_max + 1 and b + bb < N_max * b_max + 1:
                dp[i][a + aa][b + bb] = min(dp[i][a + aa][b + bb], dp[i - 1][a][b] + cc)

# print(dp[N])

ans = inf
for a in range(N_max * a_max + 1):
    for b in range(N_max * b_max + 1):
        # a:b=Ma:Mb
        # b*Ma=a*Mb
        if b * Ma == a * Mb and a * b > 0:
            ans = min(ans, dp[N][a][b])

print(ans if ans < inf else -1)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
ans = A[0]
cur = 1
count = 1
while True:
    if count <= N - 3:
        ans += A[cur] * 2
        count += 2
        cur += 1
    else:
        ans += A[cur]
        count += 1
    if count == N - 1:
        break
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
ans = A[0]
cur = 1
count = 1
while True:
    if count <= N - 3:
        ans += A[cur] * 2
        count += 2
        cur += 1
    elif count == N - 2:
        ans += A[cur]
        count += 1
    elif count == N - 1:
        break
print(ans)
### BUGGY CODE ###

mod=10**9+7
n=int(input())
T=[int(i) for i in input().split()]
A=[int(i) for i in input().split()]
Chk_T,Chk_A=[False]*n,[False]*n
Max_T,Max_A=[0]*n,[0]*n
Chk_T[0],Chk_A[-1]=True,True
Max_T[0],Max_A[-1]=T[0],A[-1]

for i in range(1,n):
  if T[i]!=T[i-1]:
    Chk_T[i]=True
  Max_T[i]=T[i]
  if A[-i-1]!=A[-i]:
    Chk_A[-i-1]=True
  Max_A[-i-1]=A[-i-1]
ans=1
flag=True
for i in range(n):
  if Chk_T[i]==False and Chk_A[i]==False:
    ans*=min(Max_T[i],Max_A[i])
  elif Chk_T[i]==True and Chk_A[i]==False:
    if Max_T[i]>Max_A[i]:
      flag=False
  elif Chk_T[i]==False and Chk_A[i]==True:
    if Max_T[i]<Max_A[i]:
      flag=False
  else:
    if Max_T[i]!=Max_A[i]:
      flag=False
print(0 if flag==False else ans%mod)


### FIXED CODE ###

mod=10**9+7
n=int(input())
T=[int(i) for i in input().split()]
A=[int(i) for i in input().split()]
Tres=[0]*n
Ares=[0]*n
Tres[0]=(0,T[0])
Ares[n-1]=(0,A[n-1])
for i in range(1,n):
  if T[i]>Tres[i-1][1]:
    Tres[i]=(0,T[i])
  else:
    Tres[i]=(1,T[i])
  if A[n-i-1]>Ares[n-i][1]:
    Ares[n-i-1]=(0,A[n-i-1])
  else:
    Ares[n-i-1]=(1,A[n-i-1])
if Tres[0]<=Ares[0]:
  ans=1
else:
  ans=0
for i in range(1,n):
  ta,tb=Tres[i]
  aa,ab=Ares[i]  
  if ta==aa==1:
    ans=ans*min(tb,ab)%mod
  elif ta==0 and aa==1 and tb>ab:
    ans=0
  elif ta==1 and aa==0 and tb<ab:
    ans=0
  elif ta==0 and aa==0 and tb!=ab:
    ans=0
print(ans%mod)
### BUGGY CODE ###

N, W = map(int, input().split())
item = [[0] * 2 for _ in range(N)]
for i in range(N):
    w, v = map(int, input().split())
    item[i][0], item[i][1] = w, v
dp = [[0] * (W+1) for _ in range(N+1)]
for n in range(1, N+1):
    for w in range(W+1):
        if item[n-1][0] <= w:
            dp[n][w] = max(dp[n-1][w], dp[n-1][w-item[n-1][0]] + item[n-1][1])
        else:
            dp[n][w] = dp[n-1][w]
print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split())
item = [[0] * 2 for _ in range(N)]
for i in range(N):
    w, v = map(int, input().split())
    item[i][0], item[i][1] = w, v
dp = [[0] * (W+1) for _ in range(N+1)]
for n in range(1, N+1):
    for w in range(W+1):
        if item[n-1][0] <= w:
            dp[n][w] = max(dp[n-1][w], dp[n-1][w-item[n-1][0]] + item[n-1][1])
        else:
            dp[n][w] = dp[n-1][w]
print(dp[N][W])
### BUGGY CODE ###

s = input()
ln = len(s)
for _ in range(100000):
    s = s.replace('10', '').replace('01', '')
#print(s)
print(ln - len(s))


### FIXED CODE ###

s = input()

red = s.count('0')
blue = s.count('1')

print(min(red, blue) * 2)
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
INF=10**10
cost=[INF]*(n+1)
cost[0]=0
for i in range(0,n):
    for j in range(1,min(k+1,n-i)):
        cost[i+j]=min(cost[i+j],cost[i]+abs(h[i+j]-h[i]))
print(cost[n-1])

### FIXED CODE ###

import sys
# inputを高速化する。
input = sys.stdin.readline

n,k=map(int,input().split())
h=list(map(int,input().split()))
INF=10**10
cost=[INF]*(n+1)
cost[0]=0

for i in range(0,n):
    for j in range(1,min(k+1,n-i)):
        cost[i+j]=min(cost[i+j],cost[i]+abs(h[i+j]-h[i]))

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

from collections import Counter

n = int(input())

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

ans_dict = {}
for i in range(n):
    buff = a_list[:i]
    buff.extend(a_list[i+1:])
    c = Counter(buff)

    if i in ans_dict.keys():
        print(ans_dict[i])
    else:
        tmp_ans = 0
        for key, value in c.items():
            if value == 1:
                continue
            else:
                tmp_ans += (value * (value - 1))/2
        ans_dict[i] = tmp_ans
        print(int(tmp_ans))




### FIXED CODE ###

from collections import Counter

n = int(input())

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

c = Counter(a_list)

all_count = 0
for value in c.values():
    if value == 1:
        continue
    else:
        tmp = int((value * (value - 1))/2)
        all_count += tmp

for i in a_list:
    print(all_count - c[i] + 1)
### BUGGY CODE ###

import sys
import bisect
from operator import itemgetter


def _i(): return int(sys.stdin.readline().strip())


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    n = _i()
    a = list(_ia())
    l = {}
    for i, ai in enumerate(a):
        aip = ai + i + 1
        l[aip] = l.get(aip, 0) + 1

    r = list(i+1-ai for i, ai in enumerate(a))
    r.sort()
    li = 0
    ans = 0
    for k, v in sorted(l.items(), key=itemgetter(0)):
        r = r[li:]
        li = bisect.bisect_right(r, k)
        ans += v * (li - bisect.bisect_left(r[:li], k))
        if li >= n:
            break
    return ans


if __name__ == "__main__":
    print(main())


### FIXED CODE ###

import sys
from collections import Counter


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    _ = sys.stdin.readline()
    a = list(_ia())
    l = Counter(ai+i+1 for i, ai in enumerate(a))
    r = Counter(i+1-ai for i, ai in enumerate(a))
    return sum(v*r.get(k, 0) for k, v in l.items())


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

a,b,x=map(int,input().split())
c=0
for i in range(a,b+1):
     if i%x==0:
          c+=1
print(c)

### FIXED CODE ###

a, b, x = map(int, input().split())
c = b // x - a // x
if a  % x == 0:
	c += 1
print(c)
### BUGGY CODE ###

from sys import stdin, exit
 
def max_heapify(a, i):
    heap_size = a[0]
 
    L = 2*i
    R = 2*i + 1
    if L <= heap_size and a[L] > a[i]:
        largest = L
    else:
        largest = i
    if R <= heap_size and a[R] > a[largest]:
        largest = R
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        max_heapify(a, largest)
 
 
def main():
    heap = [-1] * 2000001
    heap[0] = 1
    for cmd in stdin:
        if cmd[0] == 'i':
            heap[0] += 1
            i = heap[0]
            heap[i] = int(cmd[7:])
 
            half = i // 2
            while i > 1 and heap[half] < heap[i]:
                heap[i], heap[half] = heap[half], heap[i]
                i //= 2
                half = i // 2
        elif cmd[1] == 'x':
            print(heap[1])
            heap[1] = heap[heap[0]]
            heap[0] -= 1
            max_heapify(heap, 1)
        elif cmd[1] == 'n':
            exit(0)
 
 
main()

### FIXED CODE ###

import heapq
import sys

h = []

for com in sys.stdin.readlines():
    if com[0] == "i":
        heapq.heappush(h, -int(com[7:]))
    elif com[1] == "x":
        print(-heapq.heappop(h))
### BUGGY CODE ###

def choose(n, a):
    global mod
    x, y = 1, 1
    for i in range(a):
        x = x * (n - i) % mod
        y = y * (i + 1) % mod
    return x * pow(y, mod - 2, mod) % mod

k = int(input())
n = len(input())
mod = pow(10,9)+7
ans = 0
for i in range(k+1):
    ans += (choose(i+n-1,n-1)*pow(25,i,mod)*pow(26,k-i,mod))
    ans %= mod
print(ans)

### FIXED CODE ###

def choose(n,a,mod):
    x, y = 1, 1
    for i in range(a):
        x = x * (n - i) % mod
        y = y * (i + 1) % mod
    return x * pow(y, mod - 2, mod) % mod

k = int(input())
n = len(input())
mod = pow(10,9)+7
start = 1
ans = start*pow(26,k,mod)
for i in range(1,k+1):
    start *= (i+n-1)*pow(i,mod-2,mod)
    start %= mod
    ans += (start*pow(25,i,mod)*pow(26,k-i,mod))
    ans %= mod
print(ans)
### BUGGY CODE ###

def dfs(G, C, id, color):
    S = []
    S.append(id)
    C[id] = color

    while S:
        u = S[-1]  # ?????¨?¨????????????????????????°??????
        S = S[:-1]  # pop
        for i in range(len(G[u])):
            v = G[u][i]
            if C[v] == -1:
                C[v] = color
                S.append(v)


if __name__ == '__main__':
    # ??????????????\???
    num_of_users, num_of_links = [int(x) for x in input().split(' ')]
    links = []
    for _ in range(num_of_links):
        links.append(list(map(int, input().split(' '))))
    num_of_queries = int(input())
    queries = []
    for _ in range(num_of_queries):
        queries.append(list(map(int, input().split(' '))))

    # ???????????????
    G = [[] for _ in range(100000)]
    C = [-1] * 100000
    for f, t in links:
        G[f].append(t)
        G[t].append(f)

    color = 1
    for id in range(num_of_users):
        if C[id] == -1:
            dfs(G, C, id, color)
        color += 1

    # ???????????????
    for x, y in queries:
        if C[x] == C[y]:
            print('yes')
        else:
            print('no')

### FIXED CODE ###

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

"""

import sys
sys.setrecursionlimit(1000000)


n,m=[int(i) for i in input().split()]
graph=[[] for i in range(n)]

for i in range(m):
    relation=[int(j) for j in input().split()]
    graph[relation[0]].append(relation[1])
    graph[relation[1]].append(relation[0])


check=[0 for i in range(n)]
rabel=0
stack=[]

#深さ優先探索
def dfs(graph,i):
    global stack
    global n
    global rabel

    if check[i]==0:

        #行った足跡をつける
        check[i]=rabel

        #今いる場所の情報
        now=graph[i]

        #スタックに入れる
        stack.append(now)

        #今いる場所から到達できる地点のうち、まだ行っていないとこ全部でdfs
        for j in now:
            if check[j]==0:
                dfs(graph,j)

        stack.pop()

for i in range(n):
    if check[i]==0:
        rabel+=1
        dfs(graph,i)
# print(check)



num=int(input())
for i in range(num):
    a,b=[int(j) for j in input().split()]
    if check[a]==check[b]:
        print("yes")
    else:
        print("no")
### BUGGY CODE ###

N=int(input())
P=[]
for i in range(N-1):
  P.append(i+2)
P.append(1)
ans=0
for i in range(N):
  ans+=(i+1)%P[i]
print(ans)

### FIXED CODE ###

N=int(input())
print(N*(N-1)//2)
### BUGGY CODE ###

import numpy as np
n=int(input())
action=np.array([list(map(int,input().split())) for _ in range(n)])
# happy[i][j] i日目にaction j を選んだ場合の幸福度の最大値
happy=np.zeros((n+1,3))
for i in range(1,n+1):
    for j in range(3):
        happy[i][j]=max(np.concatenate((happy[i-1][0:j]+action[i-1][j],happy[i-1][j+1:3]+action[i-1][j]),axis=None))
# print(happy)
print(int(max(happy[n])))


### FIXED CODE ###

n=int(input())
action=[list(map(int,input().split())) for _ in range(n)]
# happy[i][j] i日目にaction j を選んだ場合の幸福度の最大値
happy=[[0,0,0]for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(3):
        for k in range(3):
            if j!=k:
                happy[i][j]=max(happy[i][j],happy[i-1][k]+action[i-1][j])
# print(happy)
print(max(happy[n]))
### BUGGY CODE ###

n,m = map(int,input().split())
A = list()
for i in range(m):
    a = int(input())
    A.append(a)
dp = [0]*(n+1)
dp[0] = 1
if 1 not in A:
    dp[1] = 1
for i in range(2,n+1):
    if i not in A:
        dp[i] = dp[i-2] + dp[i-1]
print(dp[-1]%1000000007)

### FIXED CODE ###

n,m = map(int,input().split())
A = list()
for i in range(m):
    a = int(input())
    A.append(a)
dp = [0]*(n+1)
dp[0] = 1
if 1 in A:
  del A[0]
else:
  dp[1] = 1
for i in range(2,n+1):
    if len(A) != 0:        
        if i != A[0]:
            dp[i] = dp[i-2] + dp[i-1]
            dp[i] = dp[i]%1000000007
        else:
          del A[0]
    else:
        dp[i] = dp[i-2] + dp[i-1]
        dp[i] = dp[i]%1000000007
print(dp[-1]%1000000007)
### BUGGY CODE ###

n = int(input())
S = [input() for i in range(n)]
ans = []
cnt = 0
for i in range(n):
    if S[i] not in ans:
        ans.append(S[i])
        cnt += 1

print(cnt)

### FIXED CODE ###

import collections
n = int(input())
S = [input() for i in range(n)]
ans = collections.Counter(S)
print(len(ans))
### BUGGY CODE ###

s = input()
q = int(input())

s = list(s)


def query_1():
    global s
    s = s[-1::-1]


def query_2(s, a, b):
    if a == 2:
        s.append(b)
    elif a == 1:
        s.insert(0, b)


for i in range(q):
    array = list(input().split())
    if len(array) == 1:
        query_1()
    else:
        query_2(s, int(array[1]), array[2])

for i in s:
    print(i, end='')




### FIXED CODE ###

from collections import deque

s = deque(list(input()))
q = int(input())
flg = 1
for i in range(q):
    array = input().split(' ')
    if array[0] == '1':
        flg *= -1
    elif array[0] == '2':
        if array[1] == '1' and flg == 1 or array[1] == '2' and flg == -1:
            s.appendleft(array[2])
        else:
            s.append(array[2])

s = list(s)
if flg == -1:
    s = s[::-1]

s = ''.join(s)
print(s)
### BUGGY CODE ###

import sys


class QueueEmptyError(Exception):
    pass


class PriorityQueue:
    def __init__(self):
        self._nodes = []
        self.size = 0

    def add(self, v):
        self._nodes.append(v)
        self.size += 1

        self._build_up(self.size-1)

    def extract(self):
        if self.size == 0:
            raise QueueEmptyError()

        node = self._nodes[0]
        self.size -= 1
        last = self._nodes.pop()
        if self.size > 0:
            self._nodes[0] = last
            self._build_down(0)

        return node

    def _build_down(self, i):
        top = i
        left = (i+1) * 2 - 1
        right = (i+1) * 2
        if left < self.size and self._nodes[left] > self._nodes[top]:
            top = left
        if right < self.size and self._nodes[right] > self._nodes[top]:
            top = right

        if top > i:
            self._nodes[top], self._nodes[i] = \
                self._nodes[i], self._nodes[top]
            self._build_down(top)

    def _build_up(self, i):
        if i == 0:
            return

        parent = (i-1) // 2
        if self._nodes[parent] < self._nodes[i]:
            self._nodes[parent], self._nodes[i] = \
                    self._nodes[i], self._nodes[parent]
            self._build_up(parent)


def run():
    q = PriorityQueue()

    for line in sys.stdin:
        if line.startswith("insert"):
            q.add(int(line[7:]))
        elif line.startswith("extract"):
            print(q.extract())
        elif line.startswith("end"):
            break
        else:
            ValueError("invalid command")


if __name__ == '__main__':
    run()



### FIXED CODE ###

import sys


def run():
    q = []

    for line in sys.stdin:
        if line.startswith("i"):
            v = int(line[7:])
            q.append(v)
            i = len(q) - 1
            while i > 0:
                p = (i-1) // 2
                vp = q[p]
                if vp < v:
                    q[p], q[i] = v, vp
                    i = p
                else:
                    break
        elif line.startswith("ex"):

            size = len(q) - 1
            if size < 0:
                raise ValueError('get from empty queue')

            v = q[0]
            last = q.pop()
            if size > 0:
                q[0] = last
                i = 0
                while i < size // 2:
                    top, vt = i, last
                    left = (i+1) * 2 - 1
                    right = (i+1) * 2
                    if left < size:
                        vl = q[left]
                        if vl > vt:
                            top, vt = left, vl
                    if right < size:
                        vr = q[right]
                        if vr > vt:
                            top, vt = right, vr

                    if top > i:
                        q[top], q[i] = last, vt
                        i = top
                    else:
                        break
            print(v)
        elif line.startswith("end"):
            break
        else:
            ValueError("invalid command")


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

K = int(input())
p = []
for i in range(1,10):
    p.append(i)
for i in range(K):
    if p[0] % 10 != 0:
        p.append(10*p[0]+p[0]%10-1)
    p.append(10*p[0]+p[0]%10)
    if p[0] % 10 != 9:
        p.append(10*p[0]+p[0]%10+1)
    q = p[0]
    p.remove(p[0])
print(q)

### FIXED CODE ###

K = int(input())
from collections import deque
p = deque()
for i in range(1,10):
    p.append(i)
for i in range(K):
    if p[0] % 10 != 0:
        p.append(10*p[0]+p[0]%10-1)
    p.append(10*p[0]+p[0]%10)
    if p[0] % 10 != 9:
        p.append(10*p[0]+p[0]%10+1)
    q = p[0]
    p.popleft()
print(q)