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

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

C = []
for i in range(0, N, 100):
  if N >= i + 101:
    C.append(S[i: i + 101].count('AC'))

for i in range(Q):
  l, r = map(int, input().split())
  if (r - 1) // 100 - (l - 1) // 100 < 2:
    ans = S[l - 1: r].count('AC')
  else:
    ans  = S[l - 1: ((l - 1) // 100) * 100 + 101].count('AC')
    for j in range((l - 1) // 100 + 1, (r - 1) // 100):
      ans += C[j]
    ans += S[((r - 1) // 100) * 100 - 1: r].count('AC')
  print(ans)


### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
LR = [list(map(int,input().split())) for _ in range(Q)]
#print(LR)

C = [0 for _ in range(N+1)]
for i in range(1,N):
  if S[i-1] == 'A' and S[i] == 'C':
    C[i+1] = C[i] + 1
  else:
    C[i+1] = C[i]
#print(C)
for l,r in LR:
  print(C[r]-C[l])
### BUGGY CODE ###

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

B = []

if len(A) %2 ==0:
    for idx, a in enumerate(A):

        if idx % 2 == 0:
            B.append(a)
        else:
            B.insert(0, a)

else:
    for idx, a in enumerate(A):

        if idx % 2 == 0:
            B.insert(0, a)
        else:
            B.append(a)
print(*B)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
from collections import deque

B = deque()

if len(A) %2 ==0:
    for idx, a in enumerate(A):

        if idx % 2 == 0:
            B.append(a)
        else:
            B.appendleft(a)

else:
    for idx, a in enumerate(A):

        if idx % 2 == 0:
            B.appendleft(a)
        else:
            B.append(a)
print(*B)
### BUGGY CODE ###

from fractions import gcd
n,m = map(int,input().split())
a = list(map(int,input().split()))
cnt = 0
while(True):
  flg = 0
  for i in range(n):
    if a[i]%2 == 0:
      if flg == 0:
        flg = 1
    if flg and a[i]%2:
      print(0)
      exit()
  if flg:
    a = [i//2 for i in a]
  else:
    break
  cnt += 1
lcm = a[0]
for i in range(n-1):
  lcm =a[i+1]*lcm//gcd(a[i+1],lcm)
print((m//(lcm*2**(cnt-1))+1)//2)

### FIXED CODE ###

from fractions import gcd
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = list(map(int,input().split()))
cnt = 0
while(True):
  flg = 0
  for i in range(n):
    if a[i]%2 == 0:
      if flg == 0:
        flg = 1
    if flg and a[i]%2:
      print(0)
      exit()
  if flg:
    a = [i//2 for i in a]
  else:
    break
  cnt += 1
lcm = a[0]
for i in range(n-1):
  lcm=a[i+1]*lcm//gcd(a[i+1],lcm)
  if lcm>m:
    print(0)
    exit()
print((m//(lcm*2**(cnt-1))+1)//2)
### BUGGY CODE ###

from collections import Counter

N = int(input())
A = [int(a) for a in input().split()]

A1 = [0]*N
A2 = [0]*N

for i in range(N):
    A1[i] = A[i] + (i+1)
    A2[i] = (i+1) - A[i]

cnt = 0
for i in range(N):
    cnt += Counter(A2[i:])[A1[i]]

print(cnt)

### FIXED CODE ###

from collections import Counter
# import sys

# input = sys.stdin.readline

N = int(input())
A = [int(a) for a in input().split()]

A1 = [0]*N
A2 = [0]*N

for i in range(N):
    A1[i] = A[i] + i
    A2[i] = i - A[i]

c = Counter(A2)

cnt = 0
for i in range(N):
    cnt += c[A1[i]]

print(cnt)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
ans = []
cost = 0
now = 0
for po in A[1:]:
    cost += abs(po-now)
    now = po
cost += abs(now)
ans.append(cost)

for i in range(1,N-1):
    cost = 0
    now =  0
    for po in A[:i]+A[i+1:]:
        cost += abs(po-now)
        now = po
    cost += abs(now)
    ans.append(cost)

cost = 0
now =  0
for po in A[:N-1]:
    cost += abs(po-now)
    now = po
cost += abs(now)
ans.append(cost)


print(*ans,sep="\n")

### FIXED CODE ###

from array import array   
N = int(input())
A = [int(i) for i in input().split()]
# 何も取りやめないときの総コスト
now = 0
cost = 0
for po in A:
    cost += abs(now - po)
    now = po
cost += abs(now)

dist = array('l',[0]+A+[0,0])
# i番目を取りやめる
for i in range(N):
    ans = cost
    ans += (abs(dist[i]-dist[i+2])) - (abs(dist[i]-dist[i+1])+abs(dist[i+1]-dist[i+2]))
    print(ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, D, A = map(int, input().split())
    monster = {}
    X = []
    for _ in range(N):
        x, h = map(int, input().split())
        monster[x] = h
        X.append(x)

    X.sort()
    ans = 0
    for i in range(N):
        k = X[i]
        v = monster[k]
        if v <= 0:
            continue

        cnt = (v + A - 1) // A
        ans += cnt

        for j in range(i + 1, N):
            x = X[j]
            if k + 2 * D < x:
                break
            monster[x] -= A * cnt

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, D, A = map(int, input().split())
    monster = {}
    X = []
    for _ in range(N):
        x, h = map(int, input().split())
        monster[x] = h
        X.append(x)

    X.sort()

    # x, damage
    q = deque([])

    acc_damage = 0

    ans = 0
    for i in range(N):
        x = X[i]
        h = monster[x]

        while q and q[0][0] < x:
            p, damage = q.popleft()
            acc_damage -= damage

        if h - acc_damage <= 0:
            continue

        cnt = (h - acc_damage + A - 1) // A
        ans += cnt
        acc_damage += cnt * A

        q.append((x + 2 * D, cnt * A))

    print(ans)


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

K, N = map(int, input().split())
A = list(map(int,input().split()))
for i in range(N):
  A.append(A[i]+K)
d = 0; ans = float("INF")
for i in range(N):
  d = 0
  for j in range(N-1):
    d += A[i+j+1] - A[i+j]
  ans = min(ans, d)
print(ans)

### FIXED CODE ###

K, N = map(int, input().split())
A = list(map(int,input().split()))
for i in range(N):
  A.append(A[i]+K)
d = [0]*(N)
max_d, max_i = 0, -1
for i in range(N):
  d[i] = A[i+1] - A[i]
  if d[i] > max_d:
    max_d = d[i]
    max_i = i + 1
ans = 0
for i in range(N-1):
  ans += A[i+max_i+1] - A[i+max_i]
print(ans)
### BUGGY CODE ###

a, b, k = map(int, input().split())
for i in range(a, b + 1):
    if i < a + k or i > b - k:
        print(i)

### FIXED CODE ###

a, b, k = map(int, input().split())
if (b - a + 1) <= 2 * k:
  for i in range(a, b + 1):
    print(i)
else:
  for i in range(a, a + k):
    print(i)
  for i in range(b - k + 1, b + 1):
    print(i)
### BUGGY CODE ###

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

m = {}
for a in sorted(set(A)):
	m[a] = A.count(a)

r = 0
for n in m:
	t = m[n]
	if n + 1 in m:
		t += m[n + 1]
	if n + 2 in m:
		t += m[n + 2]
	r = max(r, t)

print(r)


### FIXED CODE ###

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

m = {}
for a in A:
	if a not in m:
		m[a] = 1
	else:
		m[a] += 1

r = 0
for n in m:
	t = m[n]
	if n + 1 in m:
		t += m[n + 1]
	if n + 2 in m:
		t += m[n + 2]
	r = max(r, t)

print(r)
### BUGGY CODE ###

n=int(input())
s=str(input())
import itertools
ans = set(itertools.combinations(s, 3))
print(len(ans))


### FIXED CODE ###

'''
暗証番号3桁はたかだか10**3の候補。これを全探索で調べるだけ
pythonのindex関数を使用するとオブジェクト内に要素が存在しない場合エラーになる
'''
n = int(input())
s = [int(i) for i in input()]

def my_index(l,x,ind):
    '''
    l: イテラブル(for inで取り出せる)オブジェクト
    x: 探し出す大賞
    ind: イテラブルで探し始める位置（インデックス）
    返り値: 存在する場合はそのインデックス、存在しない場合は-1
    '''
    global n #入力のnと同一のものであるという意味
    if ind == n: #探索するものがない場合
        return -1
    for i in range(ind, n):
        if l[i] == x:
            return i
    else:
        return -1
c = 0
for i in range(10):
    x1 = my_index(s,i,0)
    if x1 != -1:
        for j in range(10):
            x2 = my_index(s,j,x1+1)
            if x2 != -1:
                for k in range(10):
                    x3 = my_index(s,k,x2+1)
                    if x3 != -1:
                        c += 1
print(c)
### BUGGY CODE ###

import sys
import math
import heapq
from collections import deque
from itertools import combinations
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

H,W=LI()
MP=[input() for _ in range(H)]
CORD=[(i,j) for i in range(H) for j in range(W)]

max_dist = 0
visited=set()
for st, en in combinations(CORD, 2):
    if MP[st[0]][st[1]] == "." and MP[en[0]][en[1]] == ".":
        QUE=deque()
        visited.add(st)
        QUE.append((st[0], st[1], 0))
        res = 0
        while QUE:
            ii, jj, dist = QUE.popleft()
            if (ii, jj) == en:
                res = dist
                visited.clear()
                # print("st:{} en:{} dist:{}".format(st, en, dist))
                break
            for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
                iii,jjj = ii+di, jj+dj
                if iii >= 0 and jjj >= 0 and iii < H and jjj < W and MP[iii][jjj] != '#' and not (iii, jjj) in visited:
                    QUE.append((iii, jjj, dist+1))
                    visited.add((iii, jjj))

        max_dist = max(res, max_dist)

print(max_dist)


### FIXED CODE ###

import sys
import math
import heapq
from collections import deque
from itertools import combinations
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

H,W=LI()
MP=[input() for _ in range(H)]
CORD=[(i,j) for i in range(H) for j in range(W)]

max_dist = 0
for i in range(len(CORD)):
    st = CORD[i]
    if MP[st[0]][st[1]] == ".":
        QUE=deque()
        visited = [[0]*W for i in range(H)]
        visited[st[0]][st[1]] = 1
        QUE.append((st[0], st[1], 0))
        res = 0
        while QUE:
            ii, jj, dist = QUE.popleft()
            max_dist = max(max_dist, dist)
            for iii, jjj in [(ii-1,jj),(ii+1,jj),(ii,jj-1),(ii,jj+1)]:
                if iii >= 0 and jjj >= 0 and iii < H and jjj < W and MP[iii][jjj] != '#' and not visited[iii][jjj]:
                    QUE.append((iii, jjj, dist+1))
                    visited[iii][jjj] = 1


print(max_dist)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()

def is_integer_num(n):
    if isinstance(n, int):
        return True
    if isinstance(n, float):
        return n.is_integer()
    return False

def main():
    X = int(input())
    ROOT = 1/5
    for a in range(-10000000, 10000000):
        a5 = a ** 5
        b = a5 - X
        b_root = abs(b)**ROOT
        if not is_integer_num(b_root):
            continue
        if b < 0:
            if a5 + b_root ** 5 == X:
                print(a, -int(b_root))
                exit()
        else:
            if a5 - b_root ** 5 == X:
                print(a, int(b_root))
                exit()

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    X = int(input())
    for a in range(-120, 120):
        a5 = a ** 5
        for b in range(-120, 120):
            if a5 - b ** 5 == X:
                print(a, b)
                exit()

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

n = []
for z in range(1, 59, 1):
    for y in range(1, 59, 1):
        for x in range(1, 59, 1):
            tmp = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
            if x ** 2 + y ** 2 + z ** 2 > 10 ** 4:
                break
            else:
                n.append(tmp)
N = int(input())
for i in range(1, N+1, 1):
    print(n.count(i))

### FIXED CODE ###

n = [0 for i in range(10001)]
for z in range(1, 100, 1):
    for y in range(1, 100, 1):
        for x in range(1, 100, 1):
            tmp = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
            if tmp > 10 ** 4:
                break
            else:
                n[tmp] += 1
N = int(input())
for i in range(1, N+1, 1):
    print(n[i])
### BUGGY CODE ###

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

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, Ma, Mb = map(int, input().split())
l = [[0] * 3 for i in range(N)]
for i in range(N):
    l[i][0], l[i][1], l[i][2] = map(int, input().split())

memo = [[[INF] * 401  for i in range(401)] for i in range(N+1)]
def dfs(cur, a, b, c):
    if memo[cur][a][b] < c:
        return memo[cur][a][b]
    mn = 10000
    if b != 0 and a / b == Ma / Mb:
        mn = min(c, mn)
    if cur == N:
        return mn
    mn = min(dfs(cur+1, a+l[cur][0], b+l[cur][1], c+l[cur][2]), mn)
    mn = min(dfs(cur+1, a, b, c), mn)
    memo[cur][a][b] = mn
    return mn

ans = dfs(0, 0, 0, 0)
if ans == 10000:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

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

"""
参考：https://img.atcoder.jp/abc054/editorial.pdf
・3次元DP
・送るDP
"""
 
import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7
 
N, Ma, Mb = map(int, input().split())
l = [[0] * 3 for i in range(N)]
for i in range(N):
    l[i][0], l[i][1], l[i][2] = map(int, input().split())

# 不可能な組み合わせは0とは区別するのでINF初期化
dp = [[[INF] * 401  for i in range(401)] for i in range(N+1)]
dp[0][0][0] = 0
for i in range(N):
    for j in range(401):
        for k in range(401):
            # あり得ない組み合わせの時は送らない
            if dp[i][j][k] == INF: continue
            dp[i+1][j][k] = min(dp[i][j][k], dp[i+1][j][k])
            dp[i+1][j+l[i][0]][k+l[i][1]] = min(dp[i][j][k] + l[i][2], dp[i+1][j+l[i][0]][k+l[i][1]])

ans = INF
for j in range(1, 401):
    for k in range(1, 401):
        # j/k == Ma/Mb だと分母0が心配なので
        if j * Mb == k * Ma:
            ans = min(dp[N][j][k], ans)

if ans == INF:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

N = int(input())
mod = 10 ** 9 + 7
power = 1
for i in range(N):
    power = power * (i + 1)
print(power % mod)

### FIXED CODE ###

N = int(input())
mod = 10 ** 9 + 7
power = 1
for i in range(N):
    power = power * (i + 1) % mod
print(power)
### BUGGY CODE ###

import itertools
import numpy as np
N, K, *XY = [int(_) for _ in open(0).read().split()]
X = sorted(XY[::2])
Y = sorted(XY[1::2])
XY = np.array(XY, dtype=np.int64).reshape((N, 2)).T
ans = float('inf')
for x, y in itertools.product(itertools.combinations(X, 2), itertools.combinations(Y, 2)):
    F = (x[0] <= XY[0]) * (XY[0] <= x[1]) * (y[0] <= XY[1]) * (XY[1] <= y[1])
    if sum(F) < K:
        continue
    ans = min(ans, (x[1] - x[0]) * (y[1] - y[0]))
print(ans)


### FIXED CODE ###

import itertools
N, K = [int(_) for _ in input().split()]
XY = [[int(_) for _ in input().split()] for _ in range(N)]
X, Y = [x for x, y in XY], [y for x, y in XY]
X_s, Y_s = sorted(X), sorted(Y)
ans = float('inf')
for x1, x2 in itertools.combinations(X_s, 2):
    for y1, y2 in itertools.combinations(Y_s, 2):
        k = sum([x1 <= X[i] <= x2 and y1 <= Y[i] <= y2 for i in range(N)])
        if k >= K:
            ans = min(ans, (x2 - x1) * (y2 - y1))
print(ans)
### BUGGY CODE ###

from collections import Counter
from math import factorial


def perm(n, r):
    return factorial(n) // factorial(n - r)


def comb(n, r):
    if n < r:
        return 0
    return perm(n, r) // factorial(r)


N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
D = {k: comb(v, 2) for k, v in C.items()}
_all = sum(D.values())
for a in A:
    print(_all - D[a] + comb(C[a] - 1, 2))


### FIXED CODE ###

from collections import Counter

N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
combinations = [0] + [c * (c - 1) // 2 for c in range(1, 1 + max(C.values()))]
_all = sum([combinations[c] for c in C.values()])
for a in A:
    print(_all - combinations[C[a]] + combinations[C[a] - 1])
### BUGGY CODE ###

class DList:
    class Cell:
        def __init__(self, k):
            self.key  = k
            self.prev = None
            self.next = None

    def __init__(self):
        self.head = DList.Cell(None)
        self.last = DList.Cell(None)
        self.head.next = self.last
        self.last.prev = self.head

    def insert(self, x):
        c = DList.Cell(x)
        c.prev = self.head
        c.next = self.head.next
        c.next.prev = c
        self.head.next = c

    def delete(self, x):
        c = self.__find(x)
        if c != None:
            self.__delete(c)

    def __delete(self, c):
        c.prev.next = c.next
        c.next.prev = c.prev

    def __find(self, x):
        c = self.head.next
        while c != None and c.key != x:
            c = c.next
        return c

    def deleteFirst(self):
        self.__delete(self.head.next)
    def deleteLast(self):
        self.__delete(self.last.prev)

    def print(self):
        c = self.head.next
        sep = ''
        while c != self.last:
            print(sep, end='')
            print(c.key, end='')
            c = c.next
            sep = ' '
        print()

dlist = DList()

n = int(input())
for i in range(n):
    cmd = tuple(input().split())
    if   cmd[0] == 'insert':
        dlist.insert(int(cmd[1]))
    elif cmd[0] == 'delete':
        dlist.delete(int(cmd[1]))
    elif cmd[0] == 'deleteFirst':
        dlist.deleteFirst()
    elif cmd[0] == 'deleteLast':
        dlist.deleteLast()

dlist.print()



### FIXED CODE ###

from sys import stdin

class DList:
    class Cell:
        def __init__(self, k):
            self.key  = k
            self.prev = None
            self.next = None

    def __init__(self):
        self.head = DList.Cell(None)
        self.last = DList.Cell(None)
        self.head.next = self.last
        self.last.prev = self.head

    def insert(self, x):
        c = DList.Cell(x)
        c.prev = self.head
        c.next = self.head.next
        c.next.prev = c
        self.head.next = c

    def delete(self, x):
        c = self.__find(x)
        if c != None:
            self.__delete(c)

    def __delete(self, c):
        c.prev.next = c.next
        c.next.prev = c.prev

    def __find(self, x):
        c = self.head.next
        while c != None and c.key != x:
            c = c.next
        return c

    def deleteFirst(self):
        self.__delete(self.head.next)
    def deleteLast(self):
        self.__delete(self.last.prev)

    def __iter__(self):
        self.it = self.head.next
        return self
    def __next__(self):
        if self.it == self.last:
            raise StopIteration
        k = self.it.key
        self.it = self.it.next
        return k

dlist = DList()

n = int(stdin.readline())
for i in range(n):
    cmd = stdin.readline()
    if   cmd.startswith('insert'):
        dlist.insert(cmd[7:-1])
    elif cmd.startswith('deleteFirst'):
        dlist.deleteFirst()
    elif cmd.startswith('deleteLast'):
        dlist.deleteLast()
    elif cmd.startswith('delete'):
        dlist.delete(cmd[7:-1])

print(' '.join(dlist))
### BUGGY CODE ###

N = int(input())
A_list = list(map(int,input().split()))

sw = 0
for i in range(len(A_list)):
  for j in range(i+1, len(A_list)):
    if A_list[i] == A_list[j]:
      sw = 1
      break
if sw == 1:
  print('NO')
else:
  print('YES')

### FIXED CODE ###

N = int(input())
A_list = list(map(int,input().split()))
A_list.sort()
sw = 0
for i in range(len(A_list)-1):
  if A_list[i] == A_list[i+1]:
    sw = 1
    break
if sw == 0:
  print('YES')
else:
  print('NO')
### BUGGY CODE ###

def main():
    N,M,X=map(int, input().split())
    A=[list(map(int, input().split())) for _ in range(N)]
    ans=10**10**10
    for i in range(2**N):
        b=i+2**N
        c=0
        l=[0]*M
        ok=True
        for j in range(N):
            if b>>j&1 == 1:
                c+=A[j][0]
                for k in range(M):
                    l[k]+=A[j][k+1]
        for x in l:
            if x < X: ok = False 
        if ok:
            ans = min(ans, c)
    if ans==10**5*N: print('-1')
    else: print(ans)

if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    N,M,X=map(int, input().split())
    A=[list(map(int, input().split())) for _ in range(N)]
    ans=10**10
    for i in range(2**N):
        b=i+2**N
        c=0
        l=[0]*M
        ok=True
        for j in range(N):
            if b>>j&1 == 1:
                c+=A[j][0]
                for k in range(M):
                    l[k]+=A[j][k+1]
        for x in l:
            if x < X: ok = False 
        if ok:
            ans = min(ans, c)
    if ans==10**10: print('-1')
    else: print(ans)

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

N,T = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
ind = 0
rieki = []
if N == 2:
    print(1)
    exit()
while True:
    ma = max(a[ind+1:N])
    kioku = ind+1
    ind = a.index(ma)
    if kioku != ind:
        mi = min(a[kioku:ind])
        rieki.append(ma-mi)
    if ind == N-1:
        break
rieki.sort(reverse = True)
ans = 1
for i in range(len(rieki)-1):
  if rieki[i] == rieki[i+1]:
    ans += 1
  else:
    break
print(ans)

### FIXED CODE ###

N,T = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
ans = []
mi = 10**9
for i in range(N):
    mi = min(mi,a[i])
    ans.append(a[i]-mi)
print(ans.count(max(ans)))
### BUGGY CODE ###

n,k = map(int,input().split())
l = list(map(int, input().split()))
def counter(l):
    count = {}
    for i in l:
        count[i] = l.count(i)
    return sorted(count.values())

freq = counter(l)
vf = len(freq) - k if len(freq)> k else 0
print(sum(freq[:vf]))

### FIXED CODE ###

n,k = map(int,input().split())
l = list(map(int, input().split()))
freq = [0]*(n+1)
for i in l:
    freq[i]+=1
freq.sort()
vf = len(freq) - k if len(freq)> k else 0
print(sum(freq[:vf]))
### BUGGY CODE ###

from collections import Counter
n, m = map(int, input().split())
A = list(map(int, input().split()))
cA = Counter(A)
mA = min(cA)
B = [[] for _ in range(m)]
for i in range(m):
    B[i] = list(map(int, input().split()))
B.sort(reverse=True)

for (b,c) in B:
    while b>0 and mA<c:
        if b>cA[mA]:
            cA[c] += cA[mA]; b -= cA[mA]
            del cA[mA]
            mA = min(cA)
        else:
            cA[mA] -= b
            cA[c] += b
            b = 0
ans = 0
for key, val in cA.items():
    ans += key*val
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
A = list(map(int, input().split()))

B = [[] for _ in range(m)]
for i in range(m):
    B[i] = list(map(int, input().split()))
B.sort(key=lambda x: -x[1])

_A = []
cnt = 0
for i in range(m):
    _A.extend([B[i][1]]*B[i][0])
    cnt += B[i][0]
    if cnt > n:
        break
A += _A
A.sort(reverse=True)
print(sum(A[:n]))
### BUGGY CODE ###

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

res = 0
pn = n
for i in range(10**18):
    if n % K == 0:
        res = 0
        break
    if abs(pn - K) > pn:
        res = pn
        break
    else:
        pn = n
        n = abs(pn - K)

print (res)

### FIXED CODE ###

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

res = 0
if n % K > abs((n % K) - K):
    res = abs((n % K) - K)
else:
    res = n % K
    
print (res)