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

import sys
input = sys.stdin.readline
n,k = map(int,input().split())
h = tuple(map(int,input().split()))

dp = [0] + [float("inf")]*(n-1)
for i in range(1,n):
    for j in range(max(0,i-k),i):
        dp[i] = min(dp[i],dp[j]+abs(h[i]-h[j]))
print(dp[-1])

### FIXED CODE ###

n, k = map(int,input().split())
h = list(map(int, input().split()))

dp = [0] + [float("inf")]*(n-1)

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

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


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    h,w=map(int,input().split())
    s=[input() for _ in range(h)]

    u=UnionFind(h*w)

    for i in range(h):
        for j in range(w):
            if j !=0:
                if s[i][j-1] != s[i][j]:
                    u.union(i*w+j-1,i*w+j)
            if i !=0:
                if s[i-1][j] != s[i][j]:
                    u.union((i-1)*w+j,i*w+j)
    res = 0
    for i in range(h*w):
        ih=i//w
        iw=i%w
        for j in range(i,h*w):
            if s[ih][iw] != s[j//w][j%w] and u.same(i,j):
                    res += 1
    print(res)

main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

h,w=map(int,input().split())
s=[input() for _ in range(h)]
flag = [[0]*w for _ in range(h)]

def dfs(th,tw):
    global flag,h,w,s
    flag[th][tw] = True
    tblack = 0
    twhite = 0
    if s[th][tw] == "#":
        tblack += 1
    else:
        twhite += 1 
    for x,y in ([0,1],[0,-1],[1,0],[-1,0]):
        nth = th + x
        ntw = tw + y
        if nth >= 0 and nth < h and ntw >= 0 and ntw < w:
            if not flag[nth][ntw] and s[th][tw] != s[nth][ntw]:
                ttb,ttw = dfs(nth,ntw)
                tblack += ttb
                twhite += ttw
    return [tblack,twhite]
                
def main():
    global flag,h,w,s
    res = 0
    for i in range(h):
        for j in range(w):
            if not flag[i][j]:
                black,white = dfs(i,j)
                res += black * white 

    return res
print(main())
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 0
MOD = 1_000_000_007
for i in range(n-1):
    for j in range(i+1,n):
        ans = (ans + (a[i]^a[j])) % MOD
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
tmp = [0]*61
MOD = 1_000_000_007
for i in range(n):
    for j in range(61):
        mask = 1<<j
        if a[i]&mask>0:
            tmp[j]+=1
ans = 0
for i in range(61):
    mask = 1<<i
    ans = (ans + mask*tmp[i]*(n-tmp[i])) % MOD
print(ans)
### BUGGY CODE ###

n = int(input())
phrases = [tuple(map(int, input().split())) for _ in range(n)]
m = int(input())
melodies = [int(input()) for _ in range(m)]

max_length = max(melodies)
dp = [-1] * (max_length + 394)
dp[0] = 0

for i in range(max_length):
    if dp[i] == -1:
        continue
    for s, l, p in phrases:
        for j in range(s, l + 1):
            dp[i + j] = max(dp[i + j], dp[i] + p)

results = [None] * m
for i, melody in enumerate(melodies):
    result = dp[melody]
    if result == -1:
        print(-1)
        break
    results[i] = result
else:
    print('\n'.join(map(str, results)))

### FIXED CODE ###

from collections import defaultdict

max_phrases = defaultdict(int)
n = int(input())
for _ in range(n):
    s, l, p = map(int, input().split())
    for length in range(s, l + 1):
        max_phrases[length] = max(max_phrases[length], p)

m = int(input())
melodies = [int(input()) for _ in range(m)]

max_length = max(melodies)
dp = [-1] * (max_length + max(max_phrases))
dp[0] = 0

for i in range(max_length):
    c = dp[i]
    if c == -1:
        continue
    for length, p in max_phrases.items():
        dp[i + length] = max(dp[i + length], c + p)

results = [dp[melody] for melody in melodies]
print(-1 if -1 in results else '\n'.join(map(str, results)))
### BUGGY CODE ###

def merge(A, left, mid, right):
 global x
 n1 = mid - left
 n2 = right - mid
 L = [0] * (n1+1)
 R = [0] * (n2+1)
 for i in range(n1):
  L[i] = A[left + i]
 for i in range(n2):
  R[i] = A[mid + i]
 L[n1] =  float("inf")
 R[n2] =  float("inf")
 i = 0
 j = 0
 for k in range(left,right):
  if L[i] <= R[j]:
   A[k] = L[i]
   x += 1
   i += 1
  else:
   A[k] = R[j]
   x += 1
   j += 1

def mergeSort(A, left, right):
 global x
 if left+1 < right:
  mid = (left + right)//2
  mergeSort(A,left,mid)
  mergeSort(A,mid,right)
  merge(A,left,mid,right)
 return x

n = int(input())
A = list(map(int, input().split()))
x = 0
x = mergeSort(A, 0, n)
print(" ".join(map(str, A)))
print(str(x))

### FIXED CODE ###

def merge(A, left, mid, right):
	global cnt

	L = A[left:mid] + [1000000001]
	R = A[mid:right] + [1000000001]

	i = j = 0
	for k in range(left, right):
		if L[i] <= R[j]:
			A[k] = L[i]
			i += 1
		else:
			A[k] = R[j]
			j += 1
	cnt += right - left

def mergeSort(A, left, right):
	if left + 1 < right:
		mid = (left + right) // 2
		mergeSort(A, left, mid)
		mergeSort(A, mid, right)
		merge(A, left, mid, right)

if __name__ == '__main__':
	n = int(input())
	A = list(map(int, input().split()))
	cnt = 0
	mergeSort(A, 0, n)
	print(*A)
	print(cnt)
### BUGGY CODE ###

import bisect

LI = lambda: list(map(int, input().split()))

N = int(input())
XD = [LI() for _ in range(N)]

MOD = 998244353


class BIT:

    def __init__(self, n):
        self.n = n
        self.dat = [i - 1 for i in range(self.n + 1)]

    def change(self, i, x):
        i += 1
        while i <= self.n:
            self.dat[i] = max(self.dat[i], x)
            i += i & -i

    def max_num(self, i):
        if i == 0:
            return -1
        return max(self.dat[i], self.max_num(i - (i & -i)))


def main():
    XD.sort()
    x = [None] * N
    d = [None] * N
    for i in range(N):
        x[i], d[i] = XD[i]
    
    bit = BIT(N)
    w = [None] * N
    for i in range(N - 1, -1, -1):
        v = x[i] + d[i]
        j = bit.max_num(bisect.bisect_left(x, v))
        w[i] = j - i
        bit.change(i, j)
    
    dp = [None] * (N + 1)
    dp[-1] = 1
    for i in range(N - 1, -1, -1):
        dp[i] = (dp[i + 1] + dp[i + w[i] + 1]) % MOD
    
    ans = dp[0]
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import bisect

LI = lambda: list(map(int, input().split()))

N = int(input())
XD = [LI() for _ in range(N)]

MOD = 998244353


class BIT:

    def __init__(self, n):
        self.n = n
        self.dat = [i - 1 for i in range(self.n + 1)]

    def change(self, i, x):
        i += 1
        while i <= self.n:
            self.dat[i] = max(self.dat[i], x)
            i += i & -i

    def max_num(self, i):
        if i == 0:
            return -1
        return max(self.dat[i], self.max_num(i - (i & -i)))


def main():
    XD.sort()
    x = [None] * N
    d = [None] * N
    for i in range(N):
        x[i], d[i] = XD[i]
    
    bit = BIT(N)
    w = [None] * N
    for i in range(N - 1, -1, -1):
        v = x[i] + d[i]
        j = bit.max_num(bisect.bisect_left(x, v))
        w[i] = j - i
        bit.change(i, j)
    
    dp = [None] * (N + 1)
    dp[-1] = 1
    for i in range(N - 1, -1, -1):
        dp[i] = (dp[i + 1] + dp[i + w[i] + 1]) % MOD
    
    ans = dp[0]
    print(ans)


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

string=input()
length=len(string)
mod=[0]*2019
mod[0]=1
d=1
s=0
while length > 0:
  s+=int(string[length-1])*d
  mod[s%2019]+=1
  d*=10
  length-=1
print(int(sum([(i*(i-1))/2 for i in mod])))

### FIXED CODE ###

string=input()
length=len(string)
mod=[1]+[0]*2018
s=0
for i in range(length):
  s=(s+int(string[-1-i])*pow(10,i,2019))%2019
  mod[s]+=1
print(sum([i*(i-1)//2 for i in mod]))
### BUGGY CODE ###

N, K = map(int, input().split())
L = [0] * K
R = [0] * K
S = set()
for k in range(K):
    L[k],R[k] = map(int,input().split())
for k in range(K):
    for n in range(L[k], R[k] + 1):
        S.add(n)
dp = [0] * (N+1)
dp[1] = 1
S = sorted(S)
for i in range(1,N+1):
    for s in S:    
        if i-s <= 0:
            break
        dp[i] += dp[i-s]
        if dp[i] >= 498244353:
            dp[i] -= 998244353
while dp[N] >= 998244353:
    dp[N] -= 998244353
while dp[N] < 0:
    dp[N] += 998244353    
print(dp[N])

### FIXED CODE ###

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

dp = [0] * (N + 1)
dp_sums = [0] * (N + 1)
dp[1] = dp_sums[1] = 1

for i in range(2,N+1):
    for l, r in S: 
        if i >= r + 1:
            dp[i] += dp_sums[i - l] - dp_sums[i - r - 1] 
            dp_sums[i] = dp_sums[i-1] + dp[i]
        elif i > l and i < r + 1:
            dp[i] += dp_sums[i - l] 
            dp_sums[i] = dp_sums[i-1] + dp[i]
        elif i <= l:
            dp_sums[i] = dp_sums[i-1] + dp[i]
    dp[i] %= 998244353
    dp_sums[i] %= 998244353
print(dp[N])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
U = [0]*(10**6+1)
for e in A:
    U[e] += 1
ans = 0
for k in range(1,max(A)+1):
    if U[k] == 1:
        ans += 1
    if U[k] > 0:
        for l in range(2*k,max(A)+1,k):
            if U[l] > 0:
                U[l] += 1
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
U = [0]*(10**6+1)
for e in A:
    U[e] += 1
ans = 0
for k in range(1,10**6+1):
    if U[k] == 1:
        ans += 1
    if U[k] > 0:
        for l in range(2*k,10**6+1,k):
            if U[l] > 0:
                U[l] += 1
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0
for i in range(1000):
    i = str(i).zfill(3)
    ind = 0
    a = 0
    for ij in i:
        while(ind < len(s)):
            if s[ind] == ij:
                a += 1
                ind += 1
                break
            ind += 1
    ans += a == 3
print(ans)


### FIXED CODE ###

n = int(input())
s = input()
ans = 0
for i in range(1000):
    i = str(i).zfill(3)
    ind = 0
    a = 0
    for ij in i:
        while(ind < len(s)):
            if s[ind] == ij:
                a += 1
                ind += 1
                break
            ind += 1
    ans += a == 3
print(ans)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

conv = {}
for i in range(13):
  conv[i] = (i * 10) % 13

S = readline().rstrip()
N = len(S)
DIV = 10 ** 9 + 7

dp = [[0] * 13 for i in range(N)]

x0 = S[0]
if x0 == "?":
  for i in range(10):
    dp[0][i] = 1
else:
  dp[0][int(x0)] = 1
  
for i in range(1, N):
  x = S[i]
  if x == "?":
    for j in range(13):
      for k in range(10):
        dp[i][(conv[j] + k) % 13] += dp[i - 1][j]
        dp[i][(conv[j] + k) % 13] %= DIV
  else:
    for j in range(13):
      dp[i][(conv[j] + int(x)) % 13] += dp[i - 1][j]
      dp[i][(conv[j] + int(x)) % 13] %= DIV

print(dp[-1][5])

### FIXED CODE ###

# 各桁についての13で割ったあまりを足し合わせると5になる
# "??"の場合、
# 1桁目が"3"だと、13で割ったあまりは3
# 2桁目が"8"だと、13で割ったあまりは2
# 従い83を13で割ったあまりは5
# 下から数えてN桁目までに、あまりの合計がP(0〜12)になっている数がそれぞれいくつあるかをDPする
# dp[i桁目(下から数える)][あまりの合計]

S = input()
N = len(S)
S = S[::-1] # 逆順にしたほうがやりやすい
dp = [[0] * 13 for i in range(N)]
if S[0] != "?":
  dp[0][int(S[0])] = 1 # 指定の数をとりあえずカウント
else:
  for i in range(10):
    dp[0][i] = 1 # 1桁目は、あまり0〜9になる数が一つずつある
     
# あまりリストの管理 桁数が一つ増えるごとに、各数に対しての13で割ったあまりを計算する
amari = [i for i in range(10)]
amarimap = {1:10,10:9,9:12,12:3,3:4,4:1,2:7,7:5,5:11,11:6,6:8,8:2,0:0}

DIV = 10 ** 9 + 7

# 各桁のあまりの数を更新する
# これにより、桁が増えたときに更新すべきあまりの種類（あまり13種類に対して
# ひと桁は10種類しかない）を管理できる
def update_amari():
  for i in range(len(amari)):
    amari[i] = amarimap[amari[i]]

# 2桁目以降をDP
for i in range(1,N):
  update_amari() # 各桁のあまりをアップデート
  if S[i] == "?":
    # あらゆる数が入る
    # i-1桁目の各数のループと、i桁目のあまりの各数のループ
    for j in range(len(dp[i-1])):
      # 前の桁であまりがjだったとき
      for k in amari:
        dp[i][(j + k) % 13] += dp[i-1][j]
        dp[i][(j + k) % 13] %= DIV
  else:
    # 数が決まっている
    for j in range(len(dp[i-1])):
      # あまりが決まっている
      am = amari[int(S[i])]
      dp[i][(j + am) % 13] += dp[i-1][j]
      dp[i][(j + am) % 13] %= DIV
        
# 最終桁までいったときにあまりが5になる数が必要なので、dp[N-1][5]が答え
print(dp[N-1][5])
### BUGGY CODE ###

#! python3
#  solve_122C.py

N,Q = map(int,input().split())
S = input()

for i in range(Q):
    l,r = map(int,input().split())
    cutted_str = S[l-1:r]
    print(cutted_str.count("AC"))

### FIXED CODE ###

#! python3
#  solve_122C.py

N,Q = map(int,input().split())
S = input()

t = [0]*(N+1) #ACの内Aの番号を格納(?番目形式)

for i in range(N-1):
    if S[i:i+2] == "AC":
        t[i+1] = t[i] + 1
    else:
        t[i+1] = t[i]

for i in range(Q):
    l,r  = map(int,input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

import sys
import numpy as np

N=int(input())
count = 0
j_check = 0
k_check = 0

for i in range(1,N+1):
    i_ins=[]
    for x in range(1,i+1):
        if i//x != 0 and i%x == 0:
            i_ins.append(x)
    for j in range(1,N+1):
        i_j_ins=[]
        for y in i_ins:
            if j//y != 0 and j%y == 0:
                i_j_ins.append(y)
        for k in range(1,N+1):
            i_j_k_ins=[]
            for z in reversed(i_j_ins):
                if k//z != 0 and k%z == 0:
                    i_j_k_ins.append(z)
                    break
            count = count + i_j_k_ins[-1]

print(count)

### FIXED CODE ###

import sys
import numpy as np

N=int(input())
count = 0

for i in range(1,N+1):
    i_ins=[]
    for x in range(1,i+1):
        if i//x != 0 and i%x == 0:
            i_ins.append(x)
    for j in range(1,N+1):
        i_j_ins=[]
        for y in i_ins:
            if j//y != 0 and j%y == 0:
                i_j_ins.append(y)
        if i_j_ins[-1]==1:
            #            print(i,j,i_j_ins[-1])
            count = count + i_j_ins[-1]*N
        else:
            for k in range(1,N+1):
                i_j_k_ins=[]
                for z in reversed(i_j_ins):
                    if k//z != 0 and k%z == 0:
                        i_j_k_ins.append(z)
                        break
            #    print(i,j,k,i_j_k_ins[-1])
                count = count + i_j_k_ins[-1]

print(count)
### BUGGY CODE ###

N = int(input())
s = input()
def solve():
    ans = 0
    for i in range(1000):
        t = str(i).zfill(3)
        t_index = 0 
        for s_index in range(N):
            if s[s_index] == t[t_index]:
                t_index += 1
                if t_index == 3:
                    break
        if t_index == 3:
            ans += 1
    print(ans)
solve()

### FIXED CODE ###

def solve():
    ans = 1
    N = int(input())
    s = input()
    ans = 0
    for i in range(1000):
        t = str(i).zfill(3)
        t_index = 0 
        for s_index in range(N):
            if s[s_index] == t[t_index]:
                t_index += 1
                if t_index == 3:
                    break
        if t_index == 3:
            ans += 1
    print(ans)
solve()
### BUGGY CODE ###

N = int(input())
S = input()


w = S.count('W')
e = N-w
ans = 10**9
for i in range(N):
    tmp = S[0:i].count('W')
    ans = min(e+2*tmp+(S[i]=='W')*1-i-1, ans)
    
print(ans)

### FIXED CODE ###

N = int(input())
S = input()

wcnt = [(S[0]=='W')*1]+[0]*(N-1)
for i in range(1, N):
    wcnt[i] = wcnt[i-1]+(S[i]=='W')*1

w = wcnt[N-1]
e = N-w
ans = 10**9
for j in range(N):
    tmp = wcnt[j]
    ans = min(e+2*wcnt[j]-(S[j]=='W')*1-1-j, ans)
    
print(ans)
### BUGGY CODE ###

n,k,*a=map(int,open(0).read().split())

from fractions import gcd


G=a[0]
for i in a:
    G=gcd(G,i)
    
A=max(a)

while A>0:
    if k==A:
        print("POSSIBLE")
        exit()
    A-=G
print("IMPOSSIBLE")

### FIXED CODE ###

n,k,*a=map(int,open(0).read().split())

from fractions import gcd


G=a[0]
for i in a:
    G=gcd(G,i)
    
A=max(a)
if k>A:
    print("IMPOSSIBLE")
    exit()
    
while A>0:
    if k==A:
        print("POSSIBLE")
        exit()
    A-=G
print("IMPOSSIBLE")
### BUGGY CODE ###

#N = int(input())
INF = 1000000007
N,M = map(int,input().split())
a_list = [-1]
for i in range(M):
    a_list.append(int(input()))
a_list.append(N+1)
a_list.sort()
sa_list = []
for i in range(1,M+2):
    sa_list.append(a_list[i]-a_list[i-1])

def fibonacci(n):
    if (n<=1):
        return (n)
    else:
        return(fibonacci(n-1) + fibonacci(n-2))
n=max(sa_list)+2
fib_list=[]
for i in range(n-1):
    fib_list.append(fibonacci(i))
ans = 1
for sa_i in range(len(sa_list)):
    sa = sa_list[sa_i]
#    print(sa)
    ans = ans*fib_list[sa-1]
    ans = ans % INF
print(ans)

### FIXED CODE ###

#N = int(input())
INF = 1000000007
N,M = map(int,input().split())
a_list = [-1]
for i in range(M):
    a_list.append(int(input()))
a_list.append(N+1)
a_list.sort()
sa_list = []
for i in range(1,M+2):
    sa_list.append(a_list[i]-a_list[i-1])

#def fibonacci(n):
#    if (n<=1):
#        return (n)
#    else:
#        return(fibonacci(n-1) + fibonacci(n-2))
n=max(sa_list)+2
fib_list = []

a, b = 0, 1
for i in range(n):
    fib_list.append(a)
    a, b = b, a + b

#fib_list = [i for i in fib(n)]
#for i in range(n-1):
#    fib_list.append(fibonacci(i))
ans = 1
for sa_i in range(len(sa_list)):
    sa = sa_list[sa_i]
#    print(sa)
    ans = ans*fib_list[sa-1]
    ans = ans % INF
print(ans)
### BUGGY CODE ###

def main4():
    N = int(input())
    S = input()

    R = list()
    G = list()
    B = list()

    for i in range(len(S)):
        if   S[i] == "R":
            R.append(i)
        elif S[i] == "G":
            G.append(i)
        elif S[i] == "B":
            B.append(i)

    ans = 0
    
    for r in R:
        for g in G:
            a, b = sorted([r, g])
            tmp = len(B)

            if ((b + a) % 2 == 0) and ((b + a) // 2) in B:
                tmp -= 1

            if (2*a - b) in B:
                tmp -= 1

            if (2*b - a) in B:
                tmp -= 1

            ans += tmp
                
    print(ans)

if __name__ == "__main__":
    main4()

### FIXED CODE ###

def main4():
    N = int(input())
    S = input()

    R = set()
    G = set()
    B = set()

    for i in range(len(S)):
        if   S[i] == "R":
            R.add(i)
        elif S[i] == "G":
            G.add(i)
        elif S[i] == "B":
            B.add(i)

    ans = 0
    for r in R:
        for g in G:
            a, b = sorted([r, g])
            tmp = len(B)

            if ((b + a) % 2 == 0) and ((b + a) // 2) in B:
                tmp -= 1

            if (2*a - b) in B:
                tmp -= 1

            if (2*b - a) in B:
                tmp -= 1

            ans += tmp
                
    print(ans)

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

S = list(input())

count = 0
i = 0
while len(set(S))>1:
    if S[i] != S[i+1]:
        S.remove('0')
        S.remove('1')
        count += 2
        i = 0
    else:
        i += 1
print(count)

### FIXED CODE ###

S = list(input())
one = S.count('1')
zero = S.count('0')

print(2*min(one,zero))
### BUGGY CODE ###

def main():
    import sys
    sys.setrecursionlimit(100000)
    n, m, *ab, = map(int, open(0).read().split())

    p = [-1] * (n + 1)

    def f(x):
        if p[x] < 0:
            return x
        else:
            return f(p[x])

    def g(x, t):
        if p[x] < 0:
            return
        nx = p[x]
        p[x] = t
        g(nx, t)
        

    ans = -1
    order = set()
    for i, j in zip(ab[::2], ab[1::2]):
        if i > j:
            i, j = j, i
        if (i, j) in order:
            continue

        pi, pj = f(i), f(j)
        if pi == pj:
            continue
        p[pi] += p[pj]
        ans = min(ans, p[pi])
        p[j] = pi
        p[pj] = pi
        g(j, pi)
        order.add((i, j))
    print(-ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, m, *ab, = map(int, open(0).read().split())
    p = [-1] * (n + 1)

    def find(x):
        while p[x] > 0:
            x = p[x]
        return x

    def union(i, j):
        pi, pj = find(i), find(j)
        if pi == pj:
            return
        if p[pi] < p[pj]:
            pi, pj = pj, pi
            i, j = j, i
        p[pi] += p[pj]
        p[pj] = pi
        reconnect(j, pi)

    def reconnect(i, j):
        while p[i] > 0:
            k = p[i]
            p[i] = j
            i = k

    for i, j in zip(ab[::2], ab[1::2]):
        union(i, j)

    print(-min(p))


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

from itertools import product as p

N = int(input())
*V, = map(int, input().split())
*C, = map(int, input().split())
l = [(i, j) for i,j in zip(V, C)]

ans = -10**12
for i in p(range(2), repeat=N):
    X, Y = 0, 0
    for j, k in enumerate(i):
        if k==1:
            X += V[j]
            Y += C[j]
    ans = max(ans, X-Y)
print(ans)

### FIXED CODE ###

from itertools import product as p

N = int(input())
*V, = map(int, input().split())
*C, = map(int, input().split())

ans = 0
for a in p(range(2), repeat=N):
    X, Y = 0, 0
    for i, j in enumerate(a):
        if j:
            X+=V[i]
            Y+=C[i]
    ans = max(ans, X-Y)
print(ans)
### BUGGY CODE ###

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


n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
if 2 not in a:
    print(-1)
else:
    cnt = 0
    before_num = 1
    lighted_bottons = []
    while True:
        cnt += 1
        if a[before_num - 1] == 2:
            print(cnt)
            break
        else:
            if a[before_num - 1] in lighted_bottons:
                print(-1)
                break
            before_num = a[before_num - 1]
            lighted_bottons.append(before_num)

### FIXED CODE ###

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


n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
if 2 not in a:
    print(-1)
else:
    cnt = 0
    before_num = 1
    lighted_bottons = [0 for i in range(n + 1)]
    while True:
        cnt += 1
        if a[before_num - 1] == 2:
            print(cnt)
            break
        else:
            if lighted_bottons[a[before_num - 1]] == 1:
                print(-1)
                break
            before_num = a[before_num - 1]
            lighted_bottons[before_num] = 1
### BUGGY CODE ###

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

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

p, q = 0, 0
for i in range(N):
	for j in range(i+1, N):
		d = A[j] - A[i]
		if d > p:
			p = d
			q = 1
		elif d == p:
			q += 1

print(q)


### FIXED CODE ###

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

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

p, q = 0, 0
r = A[0]

for i in range(1, N):
	if A[i] < r:
		r = A[i]
	elif A[i] - r > p:
		p = A[i] - r
		q = 1
	elif A[i] - r == p:
		q += 1

print(q)