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

k = int(input())
ama = -1
cnt = 1
x = 7
while ama!=0:
    if k % 2 == 0:
        print('-1')
        ama = 0
        break

    if x % k == 0:
        ama = 0
        print(cnt)
        break
        
    x = x*10 + 7
    cnt += 1
        
    
        

### FIXED CODE ###

k = int(input())

x = 7 % k
cnt = 1

while 10000:
    if k % 2 ==0 or k%5==0:
        print('-1')
        break
        
    if x == 0:
        print(cnt)
        break
        
    x = x*10+7
    x = x % k
    
    cnt += 1
### BUGGY CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    t = SI()

    d = {chr(x):[] for x in range(ord('a'),ord('z')+1)}
    p = {chr(x):0 for x in range(ord('a'),ord('z')+1)}
    for i,x in enumerate(s):
        d[x].append(i+1)

    rev = 0
    a = 0
    for x in t:
        if len(d[x]) == 0:
            print(-1)
            return

        c = p[x]
        while d[x][c] <= a:
            c += 1
            if c >= len(d[x]):
                rev += 1
                p = {chr(x): 0 for x in range(ord('a'), ord('z') + 1)}
                a = 0
                c = 0
        a = d[x][c]

    print(rev*len(s) + a)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    ds = s + s
    t = SI()

    z = [0] * 26
    nt = [[] for _ in range(len(ds))]

    for i in range(len(ds),0,-1):
        z[ord(ds[i-1])-ord('a')] = i
        nt[i-1] = copy.copy(z)

    rev = 0
    a = 0
    for x in t:
        x = ord(x) - ord('a')
        a = nt[a][x]
        if a == 0:
            print(-1)
            return
        if a >= len(s):
            a -= len(s)
            rev += 1
    print(rev*len(s)+a)

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

def popcount(n):
    return bin(n).count('1')


def main():
    N = int(input())
    X = input()

    X_int = int(X, 2)
    pcount_X = popcount(X_int)

    for i,bit in enumerate(X):
        bit = int(bit)
        pcount_Xi = pcount_X + (-1)**bit

        if pcount_Xi == 0:
            print(0)
            continue

        n = ((X_int % pcount_Xi) + (pow(2, N-i-1, pcount_Xi) * (-1)**bit)) % pcount_Xi

        ans = 1
        while n > 0:
            ans += 1
            n %= popcount(n)
        print(ans)
        
main()

### FIXED CODE ###

def popcount(n):
    return bin(n).count('1')


def main():
    N = int(input())
    X = input()

    X_int = int(X, 2)

    pcount_X = popcount(X_int)

    pcount_X_pls1 = pcount_X + 1
    pcount_X_mns1 = pcount_X - 1
    
    X_mod_pcount_X_pls1 = X_int % pcount_X_pls1
    if pcount_X_mns1 != 0:
        X_mod_pcount_X_mns1 = X_int % pcount_X_mns1

    for i,bit in enumerate(X):
        bit = int(bit)
        if bit == 0:
            n = (X_mod_pcount_X_pls1 + pow(2, N-i-1, pcount_X_pls1)) % pcount_X_pls1
        else:
            if pcount_X_mns1 == 0:
                print(0)
                continue
            n = (X_mod_pcount_X_mns1 - pow(2, N-i-1, pcount_X_mns1)) % pcount_X_mns1

        ans = 1
        while n > 0:
            ans += 1
            n %= popcount(n)
        print(ans)
        
main()
### BUGGY CODE ###

#初期入力
import sys
N = int(input())
A=[int(i) for i in input().split()]
#

i=0
i_index =0
brick_destroy =0
brick_remain =[]
A_now =A
while i <N:
    i +=1 #探す「文字」
    if i not in A_now:
        break
    else:
        i_index += A_now.index(i)
        brick_remain.append(i_index)
        if i_index >= N-1:
            break
        #print(brick_destroy)
        #print(i,end=" ")
        A_now = A[i_index :] #見つけた字の右側のみ見る

brick_destroy = N - len(brick_remain)
if brick_remain==[]:
    print(-1)
else:
    print(brick_destroy)

### FIXED CODE ###

#初期入力
import sys
N = int(input())
A=[int(i) for i in input().split()]
#


if 1 not in A:
    print(-1)
    exit
else:
    i=1 #探す数字
    brick_remain =set() #「1」は入っていること上記で確かめた
    for a in A:
        if a ==i:
            brick_remain.add(a)
            i +=1
    brick_destroy = N - len(brick_remain)       
    print(brick_destroy)
### BUGGY CODE ###

N,Y = map(int,input().split())
res10000 = -1
res5000 = -1
res1000 = -1
for a in range(0,N+1):
    for b in range(0,N+1):
        if N >= (a + b):
            c = N - a - b
        else:
            c = 0
        total = 10000 * a + 5000 * b + 1000 * c
        if a+b+c==N and total == Y:
            res10000 = a
            res5000 = b
            res1000 = c
            break
print(res10000,res5000,res1000)

### FIXED CODE ###

N,Y = map(int,input().split())
ans = [-1,-1,-1]
for x in range(N+1):
    for y in range(N+1):
        z = N - x - y
        if z >=0:
            if 10000 * x + 5000 * y + 1000 * z == Y:
                ans = [x,y,z]
                break

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

n = int(input())

a_str = input()
a = a_str.split(' ')
total = 1

for i in a:
    total *= int(i)

if total <= 1e+18:
    print (total)
else:
    print('-1')

### FIXED CODE ###

def total_power(n, a):
    half_total = []
    start = 0
    end = len(a)
    if n%2 == 0:
        start = 0
    else:
        start = 1 
        half_total.append(a[0])

    for i in range(start, end, 2):
        half_total.append(a[i]*a[i+1])
    if len(half_total) == 1:
        return half_total[0]
    else:
        return total_power(len(half_total), half_total)


n = int(input())

a_str = input()
a_strs = a_str.split(' ')
a = [int(s) for s in a_strs]
total = total_power(n, a)

if total <= 1e+18:
    print (total)
else:
    print('-1')
### BUGGY CODE ###

import bisect
from collections import deque

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

work = [list(map(int,input().split())) for _ in range(N)]

wq = deque(sorted(work))

paytree = []

ans = 0

for day in range(M + 1):
    while len(wq) > 0 and wq[0][0] <= day:
        bisect.insort_right(paytree,wq.popleft()[1])
    if len(paytree) > 0:
        ans += paytree.pop(len(paytree) - 1)

print(ans)

### FIXED CODE ###

import heapq
from collections import deque

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

work = [list(map(int,input().split())) for _ in range(N)]

wq = deque(sorted(work))

paytree = []

ans = 0

for day in range(M + 1):
    while len(wq) > 0 and wq[0][0] <= day:
        heapq.heappush(paytree, wq.popleft()[1] * (-1))
    if len(paytree) > 0:
        ans -= heapq.heappop(paytree)

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

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

S = input()
cnt = 0

# O(N^2)は不可。
# 010がある時、01と10を取り除くパターンを作る？

# 時間超過
s = S
while True:
    c1, c2 = 0, 0
    ls = len(s)
    for i in range(ls-1):
        if s[i] == "0" and s[i+1] == "1":
            c1 += 1
        elif s[i] == "1" and s[i+1] == "0":
            c2 += 1
    if c1 == 0 and c2 == 0:
        break
    elif c1 >= c2:
        s = s.replace("01", "")
        cnt += c1*2
    else:
        s = s.replace("10", "")
        cnt += c2*2

print(cnt)

### FIXED CODE ###

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

S = input()

# 最終出力は1のみか0のみとなるはず
# つまり、0と1の個数をカウントし、その差分から答えが求められる

c0 = S.count("0")
c1 = S.count("1")

fin = abs(c0-c1)    # 最後に残る0か1の個数
res = len(S) - fin

print(res)
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
q = int(input())
bc = list()
sum_a = 0
output = 0
cnt = 0
flag = False
for i in range(q):
  bc.append(list(map(int,input().split())))
a.sort()
for i in range(q):
  for j in range(len(a)):
    if a[j] == bc[i][0]:
      a[j] = bc[i][1]
  print(sum(a))
  a.sort()

  
  

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
BC = [list(map(int,input().split())) for _ in range(Q)]
count = [0]*((10**5)+100)
for i in range(len(A)):
  count[A[i]] += 1
sumA = sum(A)
for q in range(Q):
  count[BC[q][1]] += count[BC[q][0]]
  sumA += (BC[q][1] - BC[q][0])*count[BC[q][0]]
  print(sumA)
  count[BC[q][0]] = 0
### BUGGY CODE ###

k,s = map(int,input().split())

cnt = 0

for x in range(k+1):
    for y in range(k+1):
        if x + y > s:
            break
        z = s-x-y
        if (z>=0) and (z <= k and x+y+z == s):
            cnt +=1
            
            
print(cnt)
    

### FIXED CODE ###

k,s = map(int,input().split())

cnt = 0

for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if (z>=0) and (z <= k):
            cnt +=1
            
            
print(cnt)
### BUGGY CODE ###

n = int(input())
l_li = list(map(int,input().split()))
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if l_li[i] < l_li[j]+l_li[k] and l_li[j] < l_li[i]+l_li[k] and l_li[k] < l_li[i]+l_li[j]:
                ans += 1
print(ans)

### FIXED CODE ###

import bisect
n = int(input())
l_li = list(map(int,input().split()))
l_li.sort()
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        ind = bisect.bisect_left(l_li,l_li[i]+l_li[j])
        num = ind-1 - j
        if num > 0:
            ans += num
print(ans)
### BUGGY CODE ###

import math
H, W, A, B = map(int, input().split())

MOD = 10 ** 9 + 7

#O(N)
first = []
for i in range(0, H - A):
    if i == 0:
        tmp = 1
        first.append(tmp)
        continue
    tmp = (tmp * (B + i - 1) // i)
    first.append(tmp)

# print (first)

#O(N)
second = []
for i in range(0, H):
    if i == 0:
        tmp = 1
        second.append(tmp)
        continue
    tmp = (tmp * ((W - B) + i - 1) // i)
    second.append(tmp)

# print (second)

#O(N)
ans = 0
for i in range(H - A):
    ans = (ans + first[i] * second[H - 1 -i]) % MOD

print (ans)
#total O(3 * N) --> O(N)

### FIXED CODE ###


def modinv(a, m): #mod. m でのaの逆元 a^{-1}を計算する
    b = m
    u = 1
    v = 0
    while b:
        t = a//b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    
    u %= m
    if u < 0:
        u += m
    return u

H, W, A, B = map(int, input().split())

MOD = 10 ** 9 + 7

#O(N)
first = []
for i in range(0, H - A):
    if i == 0:
        tmp = 1
        first.append(tmp)
        continue
    tmp = (tmp * (B + i - 1) * modinv(i, MOD)) % MOD
    first.append(tmp)

# print (first)

#O(N)
second = []
for i in range(0, H):
    if i == 0:
        tmp = 1
        second.append(tmp)
        continue
    tmp = (tmp * ((W - B) + i - 1) * modinv(i, MOD)) % MOD
    second.append(tmp)

# print (second)

#O(N)
ans = 0
for i in range(H - A):
    ans = (ans + first[i] * second[H - 1 -i]) % MOD

print (ans)
#total O(3 * N) --> O(N)
### BUGGY CODE ###


def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


def main():
    import collections
    N = int(input())
    G = [[-1]*N for i in range(N)]

    ans = 2**(N-1)
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a][b] = i
        G[b][a] = i
    ans = 0
    g = [[0]*N for i in range(N)]
    for i in range(N):
        q = collections.deque()
        q.append((i, 0))
        r = [True]*N
        r[i] = False
        while(q):
            x, s = q.popleft()
            for y in range(N):
                if G[x][y] >= 0 and r[y]:
                    g[i][y] = s | 1 << G[x][y]
                    q.append((y, g[i][y]))
                    r[y] = False
    M = int(input())
    s = [0 for i in range(M)]
    for i in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1

        s[i] = g[u][v]

    # print(s)
    for i in range(2**M):
        tmp = 2**(N-1) - 1
        c = 0
        for j in range(M):
            if (i >> j) % 2 == 1:
                tmp &= ~s[j]
                c += 1
        ans += ((-1)**(c))*(1 << popcount(tmp))

    print(ans)


main()


### FIXED CODE ###

import collections
from itertools import combinations
N = int(input())
ab = [tuple(map(int, input().split())) for i in range(N-1)]
M = int(input())
uv = [tuple(map(int, input().split())) for i in range(M)]


def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


G = [[-1]*N for i in range(N)]
for i in range(N-1):
    a, b = ab[i]
    a -= 1
    b -= 1
    G[a][b] = i
    G[b][a] = i

q = collections.deque()

G2 = [[0 for j in range(N)] for i in range(N)]

for i in range(N):
    q.append((i, 0))
    reached = [False]*N
    reached[i] = True
    while(q):
        x, s = q.popleft()
        for y in range(N):
            if G[x][y] == -1 or reached[y]:
                continue
            else:
                G2[i][y] = s | (1 << G[x][y])
                q.append((y, s | 1 << G[x][y]))
                reached[y] = True


ans = 2**(N-1)
ans2 = 0
for i in range(1, 2**M):
    tmp = 2**(N-1) - 1
    for j in range(M):
        if (i >> j) % 2 == 1:
            u, v = uv[j]
            u -= 1
            v -= 1
            tmp &= ~G2[u][v]
    ans2 += ((-1)**(popcount(i)-1)) * (1 << popcount(tmp))
    # print(ans2, i)
print(ans-ans2)
### BUGGY CODE ###

n = list(map(int, input().split()))
b, m, s = sorted(n)[::-1]
cnt = 0
while not b == m == s:
    m_s = m - s
    b_m = b - m
    if m_s % 2 == 0 and m < b and m_s != 0:
        cnt += m_s // 2
        s += m_s
    elif m_s % 2 == 1 and m < b:
        cnt += 1
        s += 1
        b += 1
    elif m_s == 0 and m < b:
        cnt += b_m
        m += b_m
        s += b_m
print(cnt)


### FIXED CODE ###

a = list(map(int, input().split()))
s, m, b = sorted(a)
cnt = 0
m_s = m - s
cnt += b - m
cnt += m_s // 2

if m_s % 2 == 1:
    cnt += 2
print(cnt)
### BUGGY CODE ###

a, b, n = map(int, input().split())
ans = 0
for x in range(1,n+1):
    f = (x / b - x // b)  
    if ans <= f:
        ans = f
print(int(ans * a //1))

### FIXED CODE ###

a, b, n = map(int, input().split())
M = min(b-1,n)
print(int((M/b-M//b) * a))
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(float, input().split()))

dp = [[0]*3100 for _ in range(3100)]

N = int(input())
P = input_nums()

dp[0][0] = 1.0

for i in range(N):
    for j in range(i+1):
        dp[i+1][j+1] += dp[i][j] * P[i]
        dp[i+1][j] += dp[i][j] * (1-P[i])

res = 0.0
a = ((N+1)//2)
for j in range(a, N+1):
    res += dp[N][j]
print(res)


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(float, input().split()))

dp = [[0]*3100 for _ in range(3100)]

N = int(input())
P = input_nums()

dp[0][0] = 1.0

for i in range(N):
    for j in range(i+1):
        dp[i+1][j+1] += dp[i][j] * P[i]
        dp[i+1][j] += dp[i][j] * (1-P[i])

res = 0.0
a = ((N+1)//2)
for j in range(a, N+1):
    res += dp[N][j]
print(res)
### BUGGY CODE ###

import math
n,m = map(int,input().split())

a = input()
list1 = list(map(int,a.split()))

list1.sort()

for i in range(m):
    list1[-1] = math.floor(list1[-1]/2)
    list1.sort()
print(sum(list1))

### FIXED CODE ###

import math
n,m = map(int,input().split())

a = input()
list1 = list(map(int,a.split()))
list1.sort()
list1.reverse()
i = 0
s = math.floor(list1[0]/2)

if n == 1:
    print(math.floor(list1[0]/(2**m)))
    exit()

while True:
    while True:
        if i+1 > n:
            break
        if list1[i] < s or m == 0:
            break
        list1[i] = math.floor(list1[i]/2)
        m -= 1
        i += 1
    if m == 0:
        break
    list1.sort()
    list1.reverse()
    s = math.floor(list1[0]/2)
    i = 0
print(sum(list1))
### BUGGY CODE ###


class Node:
    def __init__(self, key=-1):
        self.key = key
        self.parent = -1
        self.left = -1
        self.right = -1
    
    def setKey(self, key):
        self.key = key


def insert(T_, z): #(T, Node)
    global T
    y = -1
    x = T_ #Node()
    while x != -1 :
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if y == -1:
        T = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z


def preParse(T):
    if T == -1 :
        return
    print T.key,
    preParse(T.left)
    preParse(T.right)

def inParse(T):
    if T == -1 :
        return
    inParse(T.left) #Node() or -1
    print T.key,
    inParse(T.right)


T = -1

def main():
    com = ''
    m = int(raw_input())
    #for i in xrange(m):
    #    com.append(raw_input())
    for i in xrange(m):
        com = raw_input()
        if com[0] == 'i':
            insert(T,Node(key=int(com[7:])))
        else:
            print '',
            inParse(T)
            print
            print '',
            preParse(T)
            print 
    return 0

main()
            

### FIXED CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin
  
  
class Node(object):
    def __init__(self, key=None):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None
  
  
def tree_insert(top, z):
    y = None
    x = top
    while isinstance(x, Node):
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if y is None:
        top = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z
    return top
  
  
def inorder_walk(node):
    if node.left:
        inorder_walk(node.left)
    print('', node.key, end='')
    if node.right:
        inorder_walk(node.right)
  
  
def preorder_walk(node):
    print('', node.key, end='')
    if node.left:
        preorder_walk(node.left)
    if node.right:
        preorder_walk(node.right)
  
  
n = int(stdin.readline())
  
top = None
for _ in range(n):
    cmd = stdin.readline()
    if cmd.startswith('i'):
        key = int(cmd[7:])
        #assert -2000000000 <= key <= 2000000000
        top = tree_insert(top, Node(key))
    else:
        inorder_walk(top)
        print()
        preorder_walk(top)
        print()
### BUGGY CODE ###

def main():
    def solve(N, W, wv):
        dp = [-1] * (W+1)
        dp[0] = 0

        for i in range(N):
            wi = wv[i][0]
            vi = wv[i][1]

            for j in range(W-wi, -1, -1):
                # print('i, wi, j = {}, {}, {}'.format(i, wi, j))
                if dp[j] == -1:
                    continue
                dp[j+wi] = max(dp[j+wi], dp[j] + vi)
                # print(dp)

        return max(dp)

    N, W = map(int, input().split())
    wv = tuple(tuple(map(int, input().split())) for i in range(N))
    print(solve(N, W, wv))


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


### FIXED CODE ###

def solve(N,W,wv):
    dp=[-1]*(W+1)
    dp[0]=0
    for i in range(N):
        cur_w=wv[i][0]
        cur_v=wv[i][1]
        for j in range(W-cur_w,-1,-1):
            if dp[j]==-1:
                continue
            if dp[j+cur_w]<dp[j]+cur_v:
                dp[j+cur_w]=dp[j]+cur_v
    return max(dp)


N,W=map(int,input().split())
wv=tuple(tuple(map(int,input().split())) for _ in range(N))
print(solve(N,W,wv))
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [float("inf") for _ in range(N)]
dp[0] = 0
for i in range(1, N):
	for j in range(K):
		if i > j:
			dp[i] = min(dp[i], dp[i - (j + 1)] + abs(h[i] - h[i - (j + 1)]))
print(dp[N - 1])

### FIXED CODE ###

N, K = map(int, input().split())
*h, = map(int, input().split())
dp = [float("inf") for _ in range(N)]
dp[0] = 0
for i in range(N - 1):
	for j in range(1, min(K + 1, N - i)):
		dp[i + j] = min(dp[i + j], dp[i] + abs(h[i + j] - h[i]))
print(dp[N - 1])
### BUGGY CODE ###

n = int(input())

a = [int(input()) for i in range(0, n)]
l = []

for j in range(0, n):
    temp = a[j]
    a[j] = 0
    print(max(a))
    a[j] = temp


### FIXED CODE ###

n = int(input())

a = [int(input()) for i in range(0, n)]

m = max(a)
l = [m] * n
index = a.index(m)
a.remove(m)
nm = max(a)
l[index] = nm
for j in range(0, n):
    print(l[j])
### BUGGY CODE ###

N, W = map(int, input().split())
wvs = [tuple(map(int, input().split())) for i in range(N)]
dp = [[0 for j in range(W+1)] for i in range(N)]

for i, wv in enumerate(wvs):
    for j in range(W+1):
        if i == 0:
            if wv[0] < j+1:
                dp[0][j] = wv[1]
        elif wv[0] < j+1:
            dp[i][j] = max(dp[i-1][j-wv[0]] + wv[1], dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[-1][-1])

### FIXED CODE ###

N, W = map(int, input().split())
wvs = [tuple(map(int, input().split())) for i in range(N)]
dp = [[0 for j in range(W+1)] for i in range(N)]

for i, wv in enumerate(wvs):
    for j in range(W+1):
        if i == 0:
            if wv[0] < j+1:
                dp[0][j] = wv[1]
        elif wv[0] < j+1:
            dp[i][j] = max(dp[i-1][j-wv[0]] + wv[1], dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[-1][-1])
### BUGGY CODE ###

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

for i in range(len(a)):
    a_pop = [0] + a[0:i] + a[i+1:len(a)] + [0]
    ans = 0
    for i in range(len(a_pop)-1):
        ans += abs(a_pop[i+1] - a_pop[i])
    print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
total = abs(a[0]) + abs(a[n-1])
for i in range(n-1):
    total += abs(a[i+1] - a[i])
a.insert(0,0)
a.insert(n+1,0)
ans=[]
for i in range(1,n+1):
    if a[i-1]<=a[i]<=a[i+1] or a[i-1]>=a[i]>=a[i+1]:
        ans.append(total)
    else:
        change = total + abs(a[i+1]-a[i-1]) -(abs(a[i]-a[i-1])+abs(a[i+1]-a[i]))
        ans.append(change)
for i in range(n):
    print(ans[i])
### BUGGY CODE ###

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

l = []
if N < B:
    for x in range(N+1):
        l.append(math.floor(A*x/B) - A*math.floor(x/B))
else:
    for x in range(B+1):
        l.append(math.floor(A*x/B) - A*math.floor(x/B))

print(max(l))
# print(l)


### FIXED CODE ###

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

x = min(B-1, N)
print(math.floor(A*x/B) - A*math.floor(x/B))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n=int(input())
g=[[float("inf")]*n for _ in range(n)]
for _ in range(n-1):
    a,b,c=map(int,input().split())
    a,b=a-1,b-1
    g[a][b]=c
    g[b][a]=c
for i in range(n):
    g[i][i]=0
q,k=map(int,input().split())
k-=1

#V=n E=n-1

d=[float("inf")]*n
d[k]=0
used=[0]*n

while True:
    v=-1
    for u in range(n):
        if (not used[u] and (v==-1 or d[u]<d[v])):
            v=u
    if v==-1:
        break
    used[v]=1
    for u in range(n):
        d[u]=min(d[u],d[v]+g[v][u])

for _ in range(q):
    x,y=map(int,input().split())
    x,y=x-1,y-1
    print(d[x]+d[y])


### FIXED CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
n=int(input())
g=[[]for _ in range(n)]
for _ in range(n-1):
    a,b,c=map(int,input().split())
    a,b=a-1,b-1
    g[a].append((b,c))
    g[b].append((a,c))


q,k=map(int,input().split())
k-=1

dist=[float("inf")]*n
dist[k]=0
def dfs(s):
    for v,c in g[s]:
        if dist[v]==float("inf"):
            dist[v]=dist[s]+c
            dfs(v)


dfs(k)

for _ in range(q):
    x,y=map(int,input().split())
    x,y=x-1,y-1
    print(dist[x]+dist[y])
### BUGGY CODE ###

def main():
    n, t, *a = map(int, open(0).read().split())
    a += [-float("Inf")]
    b = [max(a[i + 1:]) for i in range(n)]
    c = []
    for i in range(n):
        x = a[i]
        y = b[i]
        c.append(y - x)

    d = c.count(max(c))
    print(d)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, t, *a = map(int, open(0).read().split())
    b = 0
    c = float("Inf")
    d = 0
    for i in range(n):
        x = a[i]
        if x - c > b:
            b = x - c
            d = 1
        elif x - c == b:
            d += 1
        c = min(c, x)

    print(d)


if __name__ == '__main__':
    main()