Problem:
 Score : 400 points    Problem Statement There are N towns located in a line, conveniently numbered 1 through N . Takahashi the merchant is going on a travel from town 1 to town N , buying and selling apples.  Takahashi will begin the travel at town 1 , with no apple in his possession. The actions that can be performed during the travel are as follows:   Move : When at town i ( i < N ), move to town i + 1 .  Merchandise : Buy or sell an arbitrary number of apples at the current town. Here, it is assumed that one apple can always be bought and sold for A_i yen (the currency of Japan) at town i ( 1 ≦ i ≦ N ), where A_i are distinct integers. Also, you can assume that he has an infinite supply of money.   For some reason, there is a constraint on merchandising apple during the travel: the sum of the number of apples bought and the number of apples sold during the whole travel, must be at most T . (Note that a single apple can be counted in both.)  During the travel, Takahashi will perform actions so that the profit of the travel is maximized. Here, the profit of the travel is the amount of money that is gained by selling apples, minus the amount of money that is spent on buying apples. Note that we are not interested in apples in his possession at the end of the travel.  Aoki, a business rival of Takahashi, wants to trouble Takahashi by manipulating the market price of apples. Prior to the beginning of Takahashi's travel, Aoki can change A_i into another arbitrary non-negative integer A_i' for any town i , any number of times. The cost of performing this operation is |A_i - A_i'| . After performing this operation, different towns may have equal values of A_i .  Aoki's objective is to decrease Takahashi's expected profit by at least 1 yen. Find the minimum total cost to achieve it. You may assume that Takahashi's expected profit is initially at least 1 yen.      Constraints  1 ≦ N ≦ 10^5  1 ≦ A_i ≦ 10^9 ( 1 ≦ i ≦ N )  A_i are distinct.  2 ≦ T ≦ 10^9  In the initial state, Takahashi's expected profit is at least 1 yen.         Input The input is given from Standard Input in the following format:  N  T  A_1  A_2  ...  A_N       Output Print the minimum total cost to decrease Takahashi's expected profit by at least 1 yen.        Sample Input 1 3 2
100 50 200      Sample Output 1 1  In the initial state, Takahashi can achieve the maximum profit of 150 yen as follows:   Move from town 1 to town 2 .  Buy one apple for 50 yen at town 2 .  Move from town 2 to town 3 .  Sell one apple for 200 yen at town 3 .   If, for example, Aoki changes the price of an apple at town 2 from 50 yen to 51 yen, Takahashi will not be able to achieve the profit of 150 yen. The cost of performing this operation is 1 , thus the answer is 1 .  There are other ways to decrease Takahashi's expected profit, such as changing the price of an apple at town 3 from 200 yen to 199 yen.       Sample Input 2 5 8
50 30 40 10 20      Sample Output 2 2       Sample Input 3 10 100
7 10 4 5 9 3 6 8 2 1      Sample Output 3 2

Solution (Python):
import sys

def main(apples,ln):
    minp=apples[0]
    profit=[0,0]
    for x in range(1,n):
        minp=min(apples[x],minp)
        if profit[1]<apples[x]-minp:
            profit[0]=1
            profit[1]=apples[x]-minp
        elif profit[1]==apples[x]-minp:
            profit[0]+=1
    return profit[0]

n,t=map(int, sys.stdin.readline().strip().split())
apples=list(map(int,sys.stdin.readline().strip().split()))

print(main(apples,n))

Solution (Python):
n,T=map(int,input().split())
a=list(map(int,input().split()))
b=[0]*n
mn=10**18
for i in range(1,n):
  mn=min(mn,a[i-1])
  b[i]=a[i]-mn

from collections import Counter
c=Counter(b)
ans=0
for k,v in sorted(c.items(),reverse=1):
  ans+=v
  break
print(ans)

Solution (Python):
N, T = map(int,input().split())
AN = list(map(int,input().split()))

maximum = 0
ans = 0
left = AN[0]

for n in range(1,N):
  if AN[n]-left == maximum:
    ans += 1
  elif AN[n]-left > maximum:
    maximum = AN[n]-left
    ans = 1

  left = min(left,AN[n])

print(ans)

Solution (Python):
n,T = map(int,input().split())

a = list(map(int,input().split()))
maxDiff = 0
curMin = a[0]
for i in range(n):
  if curMin > a[i]:
    curMin = a[i]
  if maxDiff < a[i] - curMin:
    maxDiff = a[i] - curMin

isCovered = False
count = 0

curMin = a[0]

for i in range(n):
  if curMin > a[i]:
    curMin = a[i]
    isCovered = False
  if maxDiff == a[i] - curMin:
    if not isCovered:
      count += 1
      isCovered = True

print(count)

Solution (Python):
n,t = map(int,input().split())
a = list(map(int,input().split()))

max1 = [0] * n
max1[-1] = a[-1]

for i in range(1, n):
    max1[-i-1] = max(max1[-i], a[-i-1])

ans = 0
tmp = -1

for i in range(n):
    if max1[i] - a[i] > tmp:
        tmp = max1[i] - a[i]
        ans = 1
    elif max1[i] - a[i] == tmp:
        ans += 1

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n,t=map(int,input().split())
    A=list(map(int,input().split()))
    mlist=[0]*n
    mlist[0]=A[0]
    for i in range(1,n):
        if A[i]<mlist[i-1]:
            mlist[i]=A[i]
        else: mlist[i]=mlist[i-1]
    val=[0]*n
    for i in range(n):
        val[i]=A[i]-mlist[i]

    print(val.count(max(val)))

    
resolve()

Solution (Python):
N,T = map(int,input().split())
A = list(map(int,input().split()))
B = [0 for _ in range(N)]
amax = A[-1]
for i in range(N-2,-1,-1):
    a = A[i]
    if a>amax:
        B[i] = 0
        amax = a
    else:
        B[i] = amax-a
bmax = 0
amax = 0
for i in range(N):
    b = B[i]
    if b>bmax:
        amax = A[i]+b
        bmax = b
Ind = []
for i in range(N):
    if B[i]==bmax:
        Ind.append(i)
cnt = 0
cur = N-1
for i in range(len(Ind)-1,-1,-1):
    j = Ind[i]
    amax = A[j]+B[j]
    for k in range(cur,j,-1):
        if A[k]==amax:
            cnt += 1
    cur = j
print(cnt)

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




now = 10 ** 10
max_sub = 0
count = 1
for i in range(N):
  bb = A[i] - now
  if bb > max_sub:
    max_sub = bb
    count = 1
  elif bb == max_sub:
    count += 1

  now = min(now, A[i])
  
  

print(count)

Solution (Python):
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 unite(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 isSame(self, x, y):
        return self.find(x) == self.find(y)

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

    uf = UnionFind(N)

    mn_idx_list = []
    mn = float('inf')
    max_diff = 0
    for i in range(N):
        mn = min(mn, A[i])
        if mn == A[i]:
            mn_idx_list.append(i)
        else:
            mn_idx_list.append(mn_idx_list[-1])

        max_diff = max(max_diff, A[i] - mn)
    
    for i in range(N):
        if A[i] - A[mn_idx_list[i]] == max_diff:
            uf.unite(i, mn_idx_list[i])
    
    parents_set = set()
    for i in range(N):
        if uf.size(i) == 1:
            continue
        parents_set.add(uf.find(i))
    
    print(len(parents_set))

if __name__ == '__main__':
    solve()

Solution (Python):



from collections import Counter
N,T=map(int,input().split())
A=list(map(int,input().split()))

mini=10**9
maxi=0
m = [0]*N
M = [0]*N
z = [0]*N
for i in range(N):
    mini=min(mini,A[i])
    maxi=max(maxi,A[i])
    m[i]= mini
    M[i]= maxi
    z[i]= A[i]-mini
k=Counter(z)
l=sorted(k,reverse=True)

print(k[l[0]])

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, t = map(int, readline().split())
    a = list(map(int, readline().split()))

    cum_max = [0] * n
    cum_max[-1] = a[-1]

    for i in range(n - 2, -1, -1):
        cum_max[i] = max(cum_max[i + 1], a[i])

    profit = [0] * n
    for i in range(n-1):
        profit[i] = cum_max[i+1] - a[i]

    print(profit.count(max(profit)))


if __name__ == '__main__':
    main()

Solution (Python):
N,T = map(int,input().rstrip().split(" "))
A = list(map(int,input().rstrip().split(" ")))
max_ra = [0 for i in range(len(A)+1)]
ans = 0
k = 0
for i in range(len(A)-1,-1,-1):
    if max_ra[i+1] < A[i]:
        max_ra[i] = A[i]
    else:
        max_ra[i] = max_ra[i+1]
for i in range(len(A)):
    if max_ra[i] - A[i] > k:
        ans = 1
        k = max_ra[i] - A[i]
    elif max_ra[i] - A[i] == k:
        ans += 1
print(ans)

Solution (Python):





import math
import fractions
import sys
import bisect
import heapq  
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr



def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod



def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


inf = 10 ** 18
mod = 10 ** 9 + 7

n,t = lr()
a = lr()
min_num = inf
ans = 0
max_num = 0
for num in a:
    if max_num == num-min_num:
        ans+=1
    elif max_num < num-min_num:
        ans = 1
        max_num = num-min_num
    min_num = min(num,min_num)
print(ans)

Solution (Python):
N, T = map(int, input().split())
A = list(map(int, input().split()))
C = 0
L = 10 ** 9 + 5
S = 0
for a in A:
    if a < L:
        L = a
    elif a > L:
        St = a - L
        if St == S:
            C += 1
        elif St > S:
            C = 1
            S = St
print(C)

Solution (Python):
n, t = map(int, input().split())
A = list(map(int, input().split()))
d = {}
min_ = 10**18
for a in A:
    p = a-min_
    if p not in d:
        d[p] = 1
    else:
        d[p] += 1
    if a <= min_:
        min_ = a
M = max(d.keys())
print(d[M])

Solution (Python):
n, t = map(int, input().split())
A = list(map(int, input().split()))
d = {}
min_ = 10**18
for a in A:
    p = a-min_
    if p not in d:
        d[p] = 1
    else:
        d[p] += 1
    if a <= min_:
        min_ = a
M = max(d.keys())
print(d[M])

Solution (Python):
from operator import add
from collections import defaultdict

class SegTree():
    def __init__(self, N, e, operator_func=add):
        self.e = e 
        self.size = N
        self.node = [self.e] * (2*N)
        self.operator_func = operator_func 

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.operator_func(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size-1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.operator_func(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        
        x = self.e
        l += self.size
        r += self.size

        while l<r:
            if l&1:
                x = self.operator_func(x, self.node[l-1])
                l += 1
            if r&1:
                r -= 1
                x = self.operator_func(x, self.node[r-1])
            l >>= 1
            r >>= 1
        return x

N, T = map(int, input().split())
*A, = map(int, input().split())
tree = SegTree(N, 0, max)
tree.set_list(A)
d = defaultdict(int)
for i in range(N-1):
    d[(tree.get(i+1, N)-A[i])] += 1
print(d[max(d.keys())])

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print(*a, **dict(file=sys.stderr, **kw))

N, T = inm()
A = inl()
assert N > 1
assert len(A) == N


def solve():
    lmin = [None] * N
    lmin[0] = A[0]
    for i in range(1, N):
        lmin[i] = min(lmin[i - 1], A[i])

    rmax = [None] * N
    rmax[N - 1] = A[N - 1]
    for i in range(N - 2, -1, -1):
        rmax[i] = max(rmax[i + 1], A[i])

    gap = -1
    gmin = set()
    for i in range(N - 1):
        g = rmax[i + 1] - lmin[i]
        if g <= 0:
            continue
        if g > gap:
            gap = g
            gmin = {lmin[i]}
            
        elif g == gap and lmin[i] not in gmin:
            gmin.add(lmin[i])
    buy = len(gmin)
    assert buy > 0
    return buy


print(solve())

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




N,T = IL()
A = IL()
ans = []
MIN = A[0]
for i in range(N):
  MIN = min(MIN,A[i])
  ans.append(max(A[i]-MIN,0))
M = max(ans)
count = 0
for a in ans:
  if a == M:
    count += 1
print(count)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




N,T = IL()
A = IL()
ans = []
MAX = A[-1]
for i in range(N)[::-1]:
  MAX = max(MAX,A[i])
  ans.append(max(MAX-A[i],0))
M = max(ans)
count = 0
for a in ans:
  if a == M:
    count += 1
print(count)

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

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
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()

Solution (Python):
import math


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, T = read_ints()
    A = read_ints()
    MAX_OF_REST = []
    MAX = -math.inf
    for i in range(N-1, -1, -1):
        MAX = max(MAX, A[i])
        MAX_OF_REST.append(MAX)
    MAX_OF_REST.reverse()
    max_profit = 0
    max_count = 0
    for i in range(N-1):
        profit = MAX_OF_REST[i+1]-A[i]
        if profit > max_profit:
            max_profit = profit
            max_count = 1
        elif profit == max_profit:
            max_count += 1
    return max_count


if __name__ == '__main__':
    print(solve())

Solution (Python):
def resolve():
    N, T = list(map(int, input().split()))
    A = list(map(int, input().split()))
    counts = {}
    a_max = -float("inf")
    a_min = A[0]
    for i in range(1, len(A)):
        if a_min < A[i] and a_max < A[i]:
            a_max = A[i]
            counts.setdefault(a_max-a_min, 0)
            counts[a_max-a_min] += 1
        if a_min > A[i]:
            a_min = A[i]
            a_max = -float("inf")
    
    maxdiff = max(counts.keys())
    print(counts[maxdiff])


if __name__ == '__main__':
    resolve()

Solution (Python):
def main():
    N, T = map(int, input().split())
    A = list(map(int, input().split()))

    mi = 10**10
    diff = 0
    r = 0
    for a in A:
        if a < mi:
            mi = a
        elif a - mi == diff:
            r += 1
        elif a - mi > diff:
            r = 1
            diff = a - mi
    return r

print(main())

Solution (Python):
class SegTree:
    def __init__(self, a, func):
        self.n = 2**(len(a) - 1).bit_length()
        self.f = func
        self.d = [0] * (2 * self.n - 1)
        self.d[self.n - 1:self.n - 1 + len(a)] = a
        for i in reversed(range(self.n - 1)):
            self.d[i] = self.f(self.d[2 * i + 1], self.d[2 * i + 2])

    def update(self, i, v):
        i += self.n - 1
        self.d[i] = v
        while i:
            i = (i - 1) // 2
            self.d[i] = self.f(self.d[2 * i + 1], self.d[2 * i + 2])
    
    def query(self, l, r):
        assert l <= r
        l += self.n
        r += self.n
        s = self.d[l - 1]
        while l < r:
            if l & 1:
                s = self.f(s, self.d[l - 1])
                l += 1
            if r & 1:
                r -= 1
                s = self.f(s, self.d[r - 1])
            l //= 2
            r //= 2
        return s
def main():
    N, T = map(int, input().split())
    A = list(map(int, input().split()))
    if N == 2:
        return 1
    def func(a, b):
        if a >= b:
            return a
        return b
    s = SegTree(A, func)
    d = {}
    for i in range(N):
        t = s.query(i+1, N) - A[i]
        d[t] = d.get(t, 0) + 1
    m = 0
    for i in d:
        if i > m:
            m = i
    return d[m]
print(main())

Solution (Python):
N, T = map(int, input().split())
A = [int(i) for i in input().split()]

Amin = 10**10
P = -10**10
c = 0
for i in range(N):
    if A[i] < Amin:
        Amin = A[i]

    if A[i]-Amin == P:
        c += 1
    elif A[i]-Amin > P:
        P = A[i]-Amin
        c = 1
print(c)

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,t=map(int,input().split())
a=list(map(int,input().split()))
lst=[0]*(n+1)

for i in range(n):
    lst[-2-i]=max(lst[-1-i],a[-1-i])


sa=0
cnt=0
for i in range(n):
    if sa<lst[i]-a[i]:
        sa=lst[i]-a[i]
        cnt=1
    elif sa==lst[i]-a[i]:
        cnt+=1
    else:
        pass
print(cnt)

Solution (Python):
import sys
readline = sys.stdin.readline







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

minval = 10 ** 9 + 1 
maxdiff = 0 
ans = 0
for a in A:
  if a < minval:
    minval = a
    continue
  diff = a - minval
  if diff > maxdiff:
    maxdiff = diff
    ans = 1
  elif diff == maxdiff:
    ans += 1

print(ans)

Solution (Python):
n,t=map(int,input().split())
a=list(map(int,input().split()))
b=[]
min_a=a[0]
cnt_min=1
for ai in a[1:]:
  if min_a<ai:
    b.append([ai,ai-min_a,cnt_min])
  elif min_a==ai:
    cnt_min+=1
  elif min_a>ai:
    cnt_min=1
    min_a=ai

b.sort(key=lambda x:x[1])
max_v=b[-1][1]
ans={}
while b and max_v==b[-1][1]:
  d,v,e=b.pop()
  if d in ans:
    if e==ans[d][0]:
      ans[d]=[e,ans[d][1]+1]
    elif e>ans[d][0]:
      ans[d]=[e,1]
    else:
      pass
  else:
    ans[d]=[e,1]
tmp=0
for v in ans.values():
  tmp+=min(v)
print(tmp)

Solution (Python):
n,t=list(map(int,input().split()))
a=list(map(int,input().split()))

dp={}
mina=a[0]
maxdiff=0

for i in range(1,n):
    if a[i]>mina:
        diff=a[i]-mina
        maxdiff=max(maxdiff,diff)

        if diff in dp:
            dp[diff]+=1
        else:
            dp[diff]=1
        
    mina=min(mina,a[i])

print(dp[maxdiff])

Solution (Python):
import numpy as np
import sys
def sinput(): return sys.stdin.readline()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(): return list(imap())
def farr(): return list(fmap())
def sarr(): return sinput().split()

n, t = imap()
a = iarr()
b = []
minv = a[0]
for i in a:
    minv = min(i, minv)
    b.append(i - minv)
b.sort(reverse=True)
ans = 0
while b[ans]==b[0]: ans+=1
print(ans)

Solution (Python):
from collections import defaultdict
n,t = map(int,input().split())
a = [int(i) for i in input().split()]
dct = defaultdict(int)
mv = mk = 0
for i in range(n)[::-1]:
    k = mv-a[i]
    if k > 0: dct[k] += 1
    mk = max(mk,k)
    mv = max(mv,a[i])
print(dct[mk])

Solution (Python):
n, t = map(int, input().split())
a = list(map(int, input().split()))
m = [a[i] for i in range(n)]
for i in range(n - 2, -1, -1):
  m[i] = max(m[i], m[i + 1])
d = 0
ans = 0
for i in range(n):
  if d < m[i] - a[i]:
    d = m[i] - a[i]
    ans = 1
  elif d == m[i] - a[i]:
    ans += 1
print(ans)

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

m = A[0]
l = []
for i in range(1, N):
    if A[i] < m:
        m = A[i]
    else:
        d = A[i] - m
        l.append(d)
print(l.count(max(l)))

Solution (Python):
def main():
    N, T = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    score_list = [0 for _ in range(N)]
    min_price = A[0]
    for i in range(N):
        a = A[i]
        score_list[i] = a - min_price
        min_price = min(a, min_price)
    max_score = max(score_list)
    ans = 0
    for i in range(N):
        if score_list[i] == max_score:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N, T = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    target_list = list()
    price_buy, town_num_buy = A[N - 1], 1
    price_sell, town_num_sell = A[N - 1], 1
    for t in range(N - 2, -1, -1):
        price = A[t]
        if price < price_buy:
            price_buy = price
            town_num_buy = 1
        elif price == price_buy:
            town_num_buy += 1
        elif price == price_sell:
            town_num_sell += 1
        elif price > price_sell:
            target_list.append({
                'score': price_sell - price_buy,
                'town_num_buy': town_num_buy,
                'town_num_sell': town_num_sell
            })
            price_buy, town_num_buy = price, 1
            price_sell, town_num_sell = price, 1
    target_list.append({
        'score': price_sell - price_buy,
        'town_num_buy': town_num_buy,
        'town_num_sell': town_num_sell
    })
    max_score = max([target['score'] for target in target_list])
    ans = 0
    for target in target_list:
        if target['score'] < max_score:
            continue
        ans += min(target['town_num_buy'], target['town_num_sell'])
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n, t = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

max_list = []
tmp = A[0]
max_tmp = -1011100011
for num in A[1:]:
	diff = num - tmp
	max_tmp = max(diff, max_tmp)
	tmp = min(num, tmp)
	max_list.append(diff)

max_val = max(max_list)
c = max_list.count(max_val)
print(c)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7







N, T = getNM()
price = getList()
max_list = [0] * N


def maximizer(num_list):
    num_N = len(num_list)
    res = 0
    for i in range(1, num_N + 1):
        res = max(res, price[-i])
        num_list[-i] = res
maximizer(max_list)


def margin_checker():
    margin = 0
    for i in range(N - 1):
        margin = max(max_list[i] - price[i], margin)
    return margin

max_margin = margin_checker()

cnt = 0

while True:
    for i in range(N - 1):
        if max_list[i] - price[i] == max_margin:
            price[i] += 1
            cnt += 1
    if margin_checker() < max_margin:
        break
    
    maximizer(max_list)
    max_margin = margin_checker()
print(cnt)