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



Sample input:
3 2
100 50 200


Sample output:
1

Submission status: Accepted

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

max_benefit = 0
a_min = a[0]
ans = 0
for i in range(1, n):
    if a[i] < a_min:
        a_min = a[i]
    benefit = (a[i] - a_min)
    if  benefit == max_benefit:
        ans += 1
    elif benefit > max_benefit:
        ans = 1
        max_benefit = benefit

print(ans)

Submission status: Accepted

Solution code:
n, t = map(int, input().split())
a = [int(x) for x in input().split()]
m = a[0]
d = 0
c = 1
for x in a:
    if x < m: m = x
    elif x - m == d: c += 1
    elif x - m > d:
        d = x - m
        c = 1
print(c)

Submission status: Accepted

Solution code:
from collections import Counter
n,x=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
b=[]
m=10**9
for i in a:
  if i < m:
    m = i
  else:
    b.append(i-m)

ma=max(b)
c=Counter(b)
print(c[ma])

Submission status: Accepted

Solution code:
N,T = map(int,input().split())
A = list(map(int,input().split()))
minP,prof,pc = 10**9+1,0.5,0
for i in range(N):
    minP = min(minP,A[i])
    d = A[i]-minP
    if d > prof:
        prof = d
        pc = 1
    elif d == prof:
        pc += 1
print(pc)

Submission status: Accepted

Solution code:
from collections import defaultdict

if __name__ == '__main__':
    nums = [int(x) for x in input().split()]
    N,T = nums[0],nums[1]
    cities = [int(x) for x in input().split()]

    d = defaultdict(int)

    minPrice = 90000000000
    maxProf = -1
    for city in cities:
        minPrice = min(city, minPrice)
        prof = city - minPrice
        d[prof] += 1
        
        maxProf = max(prof,maxProf)
    print(d[maxProf])

Submission status: Accepted

Solution code:
def get_next_int():
    return int(float(input()))


def get_next_ints(delim=" "):
    return tuple([int(float(x)) for x in input().split(delim)])


def get_next_str():
    return input()


def get_next_strs(delim=" "):
    return tuple(input().split(delim))


def get_next_by_types(*value_types, delim=" "):
    return tuple([t(x) for t, x in zip(value_types, input().split(delim))])


def solve():
    N, T = get_next_ints()
    values = get_next_ints()

    r_values = reversed(values)

    count = 0
    max_val = 0
    max_diff = 0
    for value in r_values:
        if value >= max_val:
            max_val = value
            continue
        diff = max_val - value
        if diff > max_diff:
            max_diff = max_val - value
            count = 1
        elif diff == max_diff:
            count += 1
    print(count)

solve()

Submission status: Accepted

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

maxp = 0
minv = float('inf')
ans = 0
for a in A:
    p = a - minv
    if p > maxp:
        maxp = p
        ans = 1
    elif p == maxp:
        ans += 1

    minv = min(minv, a)

print(ans)

Submission status: Accepted

Solution code:
N, T = map(int, input().split())
A = list(map(int, input().split()))
B = A[::-1]
C = []

maxv = 0
for i in range(N):
    if maxv > B[i]:
        C.append(maxv)
    else:
        maxv = B[i]
        C.append(maxv)

C = C[::-1]

ans = 0
maxv = 0
for i in range(N-1):
    z = C[i] - A[i]
    if maxv > z:
        continue
    elif maxv < z:
        maxv = z
        ans = 1
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N,T=map(int, raw_input().split())
A=map(int, raw_input().split())

A_r=[None for i in range(N)]
n=0
for i in range(N-1,-1,-1):
	n=max(A[i],n)
	A_r[i]=n

B=[]
for i in range(N-1):
	B.append(A_r[i+1]-A[i])


C=Counter(B)

print C[max(B)]

Submission status: Accepted

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

minA = [(-1,-1)] * (N)
maxA = [(-1,-1)] * (N)

maxA[N-1] = (A[-1],1)
minA[0] = (A[0],1)
for i in range(1,N):
	if A[i] == minA[i-1][0]:
		minA[i] = (A[i],minA[i-1][1]+1)
	else:
		minA[i] = (min(minA[i-1][0],A[i]),1)

	if A[N-i-1] == minA[N-i][0]:
		minA[N-i-1] = (A[N-i-1],minA[N-i][1] + 1)
	else:
		maxA[N-i-1] = (max(maxA[N-i][0],A[N-i-1]),1)

pair = {}
prev = maxA[1][0] - minA[0][0]
for i in range(N-1):
	if prev < (maxA[i+1][0] - minA[i][0]):
		pair = {(maxA[i+1][0],minA[i][0]) : min(maxA[i+1][1],minA[i][1])}
		prev = (maxA[i+1][0] - minA[i][0])
	elif prev == (maxA[i+1][0] - minA[i][0]):
		if (maxA[i+1][0],minA[i][0]) in pair:
			pair[(maxA[i+1][0],minA[i][0])] = max(pair[(maxA[i+1][0],minA[i][0])],min(maxA[i+1][1],minA[i][1]))
		else:
			pair[(maxA[i+1][0],minA[i][0])] = min(maxA[i+1][1],minA[i][1])

print(sum(pair.values()))

Submission status: Accepted

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

buy_min=10000000000
max_ben=0
ans=0

for i in range(N):
  if A[i]>buy_min and (A[i]-buy_min)>max_ben:
    ans=1
    max_ben=(A[i]-buy_min)
  elif A[i]>buy_min and (A[i]-buy_min)==max_ben:
    ans+=1
  if buy_min>A[i]:
    buy_min=A[i]
print(ans)

Submission status: Accepted

Solution code:
def d_AnInvisibleHand(N, T, A):
    min_value = A[0]  # 高橋君はA[j]=min_valueとなる町でリンゴを仕入れる
    max_profit = 0  # 利益の最大値
    ans = 0  # 青木君が費やさねばならないコスト
    for i in range(1, N):
        profit = A[i] - min_value  # 町iでリンゴを売ったときの利益
        if profit > max_profit:
            # 利益が最大値を更新した。青木君はA[i]を1下げるかA[j]==min_valueとなる
            # 町jについてA[j]を1上げればいいので、ans=1とする
            max_profit = profit
            ans = 1
        elif profit == max_profit:
            # A[i]は相異なるので、コスト1で2対以上の売買する町のペアに影響を与えることができない
            # ex. 10,20,(11~19),20なら、20の町より10の町にコストを掛けるほうがよい
            ans += 1
        min_value = min(min_value, A[i])
    return ans

N,T = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
print(d_AnInvisibleHand(N, T, A))

Submission status: Accepted

Solution code:
N,T = map(int,input().split())
src = list(map(int,input().split()))
minv = src[0]
maxp = ans = 0
for i in range(1,N):
    profit = src[i] - minv
    if profit == maxp:
        ans += 1
    elif profit > maxp:
        maxp = profit
        ans = 1
    minv = min(minv, src[i])

print(ans)

Submission status: Accepted

Solution code:
n,t = map(int, input().split())
a = list(map(int, input().split()))
max_gain =0 
max_a = 0
max_cnt = 0
for i in range(n-1, -1, -1):
    if a[i] > max_a:
        max_a = a[i]
    elif max_a - a[i] > max_gain:
        max_gain = max_a - a[i]
        max_cnt = 1
    elif max_a - a[i] == max_gain:
        max_cnt += 1
print(max_cnt)

Submission status: Accepted

Solution code:
l = list(map(int, input().split()))
n = l[0]
t = l[1]

l = list(map(int, input().split()))
maxdiff = 0
count = 0
currentmin = 10000000000

for i in l:
    if i - currentmin > maxdiff:
        maxdiff = i - currentmin
        count = 1
    elif i - currentmin == maxdiff:
        count += 1
    elif i < currentmin:
        currentmin = i
print(count)

Submission status: Accepted

Solution code:
N, T = [int(n) for n in input().split()]
A = [int(n) for n in input().split()]

current_min = 100000000000000000
current_max_diff = -10000000000000000
max_diff_cnt = 0
for a in A:
  if a - current_min == current_max_diff:
    max_diff_cnt += 1
  if a - current_min > current_max_diff:
    current_max_diff = a - current_min
    max_diff_cnt = 1
  if a < current_min:
    current_min = a

print(max_diff_cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict


def main():
    N, T = map(int, input().split())
    a_list = list(map(int, input().split()))
    d = defaultdict(int)
    min_a, min_i = a_list[0], 0
    for i in range(1, len(a_list)):
        a = a_list[i]
        d[a - min_a] += 1
        min_a = min(min_a, a)

    print(d[max(d)])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

max_diff = 0
count = 0
minv = A[0]

for i in range(1, len(A)):
    if max_diff < (A[i]- minv):
        max_diff = A[i]- minv
        count = 1
    elif max_diff == (A[i]- minv):
        count += 1
        
    if minv > A[i]:
        minv = A[i]
        
print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
 
n,t = map(int, raw_input().split())
a = map(int, raw_input().split()) 
 
m = 10**9+1
num = 0
diff = 0
for i in range(n):
    if(a[i]<m):
        m = a[i]
    if(a[i]-m > diff):
        diff = a[i]-m
        num = 1
    elif(a[i]-m == diff):
        num += 1
print(num)

Submission status: Accepted

Solution code:
N, T = list(map(int, input().split()))
ps = list(map(int, input().split()))
min_p = 99999999999999
max_diff = 0
min_n = 0
 
for i in range(0, N):
    if ps[i] < min_p:
        min_p = ps[i]
    elif max_diff == ps[i] - min_p:
        min_n += 1
    elif max_diff < ps[i] - min_p:
        max_diff = ps[i] - min_p
        min_n = 1
 
print(str(min_n))

Submission status: Accepted

Solution code:
import sys

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N, T = map(int, input().split())
    A = [int(i) for i in input().split()]
    min_v = float('inf')
    max_dif = 0
    ans = 0

    for a in A:
        if min_v > a:
            min_v = a
        else:
            max_dif = max(max_dif, a - min_v)

    # debug(max_dif, locals())

    min_v = float('inf')

    for a in A:
        if min_v > a:
            min_v = a
        else:
            if a - min_v == max_dif:
                ans += 1

    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#D    高橋君と見えざる手 / An Invisible Hand
N,T = [int(i) for i in input().split(" ")]
A=[int(i) for i in input().split(" ")]
Max = 0
count = 1
Min = A[0]
for i in range(N):
    if A[i] <= Min :
        Min = A[i]
    else :
        temp = A[i]-Min
        if temp > Max:
            Max = temp 
            count = 1
        elif temp == Max :
            count += 1
print(count)

Submission status: Accepted

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

min_list = [0 for i in range(N)]
max_list = [0 for i in range(N)]
min_list[0] = A[0]
max_list[N-1] = A[N-1]
for i in range(1, N):
	min_list[i] = min(min_list[i-1], A[i])
	max_list[N-i-1] = max(max_list[N-i], A[N-i-1])
prof = max([max_list[i+1]-min_list[i] for i in range(N-1)])
count = 0
for i in range(N-1):
	if max_list[i+1]-min_list[i]==prof:
		if count==0:
			pair = (min_list[i], max_list[i+1])
			count = count+1
		elif pair!=(min_list[i], max_list[i+1]):
			pair = (min_list[i], max_list[i+1])
			count = count+1
print(count)

Submission status: Accepted

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


m = 0
_mini = A[0]
for i in range(1, N):
    _mini = min((_mini, A[i]))
    m = max((m, A[i] - _mini))

ans = 0
mini = A[0]
for i in range(1, N):
    mini = min((mini, A[i]))
    if m == (A[i] - mini):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
nt=input().split(" ")
N=int(nt[0])
T=int(nt[1])


a=input().split(" ")
int_a=[]
maxlist=[]
for i in range(N):
    int_a.append(int(a[i]))

reva=int_a
reva.reverse()
max=0
for i in range(N):
    if reva[i]>max:
        max=reva[i]
    maxlist.append(max)

maxlist.reverse()
int_a.reverse()


max=0
count=1
for i in range(N):
    if maxlist[i]-int_a[i]>max:
        count=1
        max=maxlist[i]-int_a[i]
    elif maxlist[i]-int_a[i]==max:
        count+=1

print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
N, T = map(int, raw_input().split())
A = map(int, raw_input().split())
mini = A[0]
maxdlt = 0
count = 0
for n in A:
    #tmp = maxdlt
    if mini > n:
        mini = n
    dlt = n - mini
    if dlt == maxdlt:
        count = count + 1
    if dlt != 0:
        if maxdlt < dlt:
            maxdlt = dlt
            count = 1
print(count)

Submission status: Accepted

Solution code:
input()
A=list(map(int,input().split()))
d,c,s=0,0,A[0]
for x in A[1:]:
 s=min(s,x)
 D=x-s
 if d<D:
  d,c=D,1
 elif D==d:
  c+=1
print(c)

Submission status: Accepted

Solution code:
raw_input('').split()
A = [int(x) for x in raw_input('').split()]
max = 0
count = 0
pl = 0
msp = A[0]
for i in range(1,len(A)):
  pl_t = pl + A[i] - A[i-1]
  if pl_t <= 0:
    pl = 0
  else:
    pl = pl_t
    if max < pl_t:
      max = pl_t
      count = 1
    elif max == pl_t:
      count += 1
print count

Submission status: Accepted

Solution code:
N,T = [int(x) for x in raw_input().split(" ")]

A = [int(x) for x in raw_input().split(" ")]

mx = -1e10
cnt = 0
X = []

for i in range(len(A)):
	mx = max(A[-i-1],mx)
	
	dif = mx - A[-i-1]
	
	X.append(dif)



mxx = max(X)

for i in X:
	if i == mxx:
		cnt += 1

print cnt

Submission status: Accepted

Solution code:
import sys

N, T = map(int, sys.stdin.readline().split())

A = map(int, sys.stdin.readline().split())

cnt = 0
diff = 0
miniA = A[0]
for i in xrange(1, N):
    if A[i] < miniA:
        miniA = A[i]
    if A[i] - miniA > diff:
        diff = A[i] - miniA
        cnt = 1
    elif A[i] - miniA == diff:
        cnt += 1
print cnt

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N,T=map(int,raw_input().split())
A=map(int,raw_input().split())

minv=A[0]
interval=0
cnt=0
for i in A[1:]:
    if i < minv:
        minv=i
    if i-minv > interval:
        interval=i-minv
        cnt=1
    elif i-minv == interval:
        cnt=cnt+1
print(cnt)

Submission status: Accepted

Solution code:
input()
A=list(map(int,input().split()))
m,B,r=A[0],0,0
for a in A[1:]:
    if a<m:
        m=a
    b=a-m
    if b>B:
        B,r=b,1
    elif b==B:
        r+=1
print(r)

Submission status: Accepted

Solution code:
def solve(a):
    m, diff, ans = 10 ** 10, 0, 0
    for i in range(len(a)):
        if a[i] < m:
            m = a[i]
        elif a[i] - m > diff:
            diff = a[i] - m
            ans = 1
        elif a[i] - m == diff:
            ans += 1

    return ans


def solve2(a):
    if len(a) <= 3:
        return 1

    base = a[-1]
    m = 10 ** 10
    diff_list = []
    for i in range(len(a) - 2, -1, -1):
        if a[i] >= base:
            diff_list.append(base - m)
            base = a[i]
            m = 10 ** 10
        m = min(m, a[i])
    else:
        diff_list.append(base - m)

    return diff_list.count(max(diff_list))


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

    print(solve2(a))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def solve(a):
    m, diff, ans = 10 ** 10, 0, 0
    for i in range(len(a)):
        if a[i] < m:
            m = a[i]
        elif a[i] - m > diff:
            diff = a[i] - m
            ans = 1
        elif a[i] - m == diff:
            ans += 1

    return ans


def main():
    n, t = map(int, input().split())
    a = list(map(int, input().split()))
    print(solve(a))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, t = list(map(int, input().split()))
a = list(map(int, input().split()))
min_a = 1000000000
max_dif = 0
max_dif_c = 0
for i in range(n):
    if a[i] < min_a:
        min_a = a[i]
    elif a[i] - min_a > max_dif:
        max_dif = a[i] - min_a
        max_dif_c = 1
    elif a[i] - min_a == max_dif:
        max_dif_c += 1
print(str(max_dif_c))

Submission status: Accepted

Solution code:
n, t = map(int, input().split())
a = [int(i) for i in input().split()]

count = 0
m = a[0]
maxrieki = 0

for i in range(n):
    if( m > a[i]):
        m = a[i]
    else:
        if(maxrieki < (a[i] - m)):
            maxrieki = a[i] - m
            count = 1
        elif(maxrieki != 0 and maxrieki == (a[i]-m)):
            count+=1

print(count)

Submission status: Accepted

Solution code:
N,T=map(int,raw_input().split())
A=map(int,raw_input().split())
m=A[0]
maxDif=0
c=0
for i in xrange(1,len(A)):
  if A[i]-m>maxDif:
    maxDif=A[i]-m
    c=1
  elif A[i]-m==maxDif:
    c+=1
  m=min(m,A[i])
print c

Submission status: Accepted

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

minA = A[0]
benefit = 0
maxBenefit = 0
cost = 0

for i in range(N):
    if A[i] < minA:
        minA = A[i]
    else:
        benefit = A[i] - minA
        if benefit > maxBenefit:
            maxBenefit = benefit
            cost = 1
        elif benefit == maxBenefit:
            cost += 1

print(cost)

Submission status: Accepted

Solution code:
import numpy as np

if __name__ == "__main__":
	n,t = map(int,raw_input().split())
	li = map(int,raw_input().split())

	minv = li[0]
	dm = 0
	ans = 1
	for i in range(1, len(li)):
		minv = min(minv, li[i])
		if(dm == li[i] - minv):
			ans += 1
		elif(dm < li[i]-minv):
			dm = li[i] - minv
			ans = 1

	print ans

Submission status: Accepted

Solution code:
def r(): return list(map(int,input().split()))
M=9e9
_=r();a=r()
m=M;D=0
for x in a:
    m=min(m,x)
    D=max(D,x-m)
m=M;y=0
for x in a:
    m=min(m,x)
    y+=(x-m==D)
print(y)

Submission status: Accepted

Solution code:
def readints(): return map(int,input().split())

N, T = readints()
a = list(readints())

mdiff = 0
mi = 1145141919
for x in a:
    mi = min(mi, x)
    mdiff = max(mdiff, x - mi)

mi = 1145141919
ans = 0
for x in a:
    mi = min(mi, x)
    ans += (x - mi == mdiff)

print(ans)

Submission status: Accepted

Solution code:
def readints(): return map(int,input().split())

N, T = readints()
a = list(readints())

mdiff = 0
mi = 1145141919
for i in range(N):
    mi = min(mi, a[i])
    mdiff = max(mdiff, a[i] - mi)

mi = 1145141919
ans = 0
for i in range(N):
    mi = min(mi, a[i])
    ans += (a[i] - mi == mdiff)

print(ans)

Submission status: Accepted

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

minAi = A[0]
maxDiff = 0
ans = 0
for ai in A[1:]:
    if ai < minAi:
        minAi = ai
    else:
        diff = ai - minAi
        if diff > maxDiff:
            maxDiff = diff
            ans = 1
        elif diff == maxDiff:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, T = map(int, input().split())
num_list = input().split()
num_list = [int(x) for x in num_list]

count = 0
profit = 0
min_val = num_list[0]

for num in num_list:
    if num < min_val:
        min_val = num
    elif num - min_val == profit:
        count += 1
    elif num - min_val > profit:
        count = 1
        profit = num - min_val

print(count)

Submission status: Accepted

Solution code:
IS=float('inf')

n,t=map(int,raw_input().split())
a=map(int,raw_input().split())
ans=0
chk=1
x=IS
y=0
for i in a:
    if x>i:
        x=i
    elif y<i:
        y=i
    if i-x>chk:
        ans=1
    elif i-x==chk:
        ans+=1
    chk=max(chk,i-x)
print ans

Submission status: Accepted

Solution code:
import sys
lines = sys.stdin.readlines()
sizes = lines[0].split(" ")
N = int(sizes[0])
T = int(sizes[1])
line = lines[1].split(" ")
inp = []
for i in line:
    inp.append(int(i))

check = []
checkMax = []

#for i in range(len(inp)):
#i=0
#c = []
#for j in range(i+1,len(inp)):
    #if inp[i]<inp[j]:
#    c.append(inp[j]-inp[i])
#check.append(c)
#check=c
#checkMax.append(max(check))

#while (len(check)>1):
#    check.pop(0)
#    checkMax.append(max(check))


#for j in range(1,len(inp)):
#    checkMax[j-1] += inp[0]-inp[j]

count=0
for i in range(1,len(inp)):
    if i==1:
        mi = min(inp[0],inp[1])
        ma = inp[1]-inp[0]
        if ma>0:
            count+=1
    elif i>1:
        if ma<inp[i]-mi:
            count=1
            ma=inp[i]-mi
        elif ma==inp[i]-mi:
            count+=1
        mi = min(inp[i],mi)

print (count)


#print (check)
#print (checkMax)
#print (checkMax.count(max(checkMax)))

Submission status: Accepted

Solution code:
def read():
	return [int(i) for i in input().split(' ')]
N, T = read()
A = read()
t_min = A[0]
cost = 1
profit = 0

for p in A:
	if(p < t_min):
		t_min = p
	elif(p - t_min == profit):
		cost += 1
	elif(p - t_min > profit):
		cost = 1
		profit = p - t_min
print(cost)

Submission status: Accepted

Solution 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)

Submission status: Accepted

Solution code:
dat = raw_input()
(N,T) = dat.split(" ")

N = int(N)
T = int(T)

dat = raw_input()
A = map(int,dat.split(" "))

diffno = 0

mind = A[0]
maxd = 0

for x in range(1,len(A)):
  if maxd < (A[x] - mind):
    maxd = A[x] - mind
    diffno = 1
  elif maxd == (A[x] - mind):
    diffno += 1

  if mind > A[x]:
    mind = A[x]

print diffno

Submission status: Accepted

Solution code:
input()
a=[]
for i in input().split():
	a.append(int(i))

maxp = 0
minp = 10000000000000
maxval=0
c=0
for i in range(len(a)):
	if a[i]<minp:
		minp=a[i]
	val=a[i]-minp
	if val>maxval:
		maxval=val
		c=1
	elif val==maxval:
		c+=1

print(c)

Submission status: Accepted

Solution code:
from collections import defaultdict

n,t=map(int,input().split())
arr=list(map(int,input().split()))
curmax=0
curdiff=0
maxmax=0
dd=defaultdict(int)
for i in range(n):
    curmax=max(arr[n-1-i],curmax)
    curdiff = curmax-arr[n-1-i]
    maxmax=max(maxmax,curdiff)
    if maxmax==curdiff:
        dd[maxmax]+=1
print(dd[maxmax])

Submission status: Accepted

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

submax = 0
amin=A[0]
total = 0
for i in range(N):
    if A[i] < amin:
        amin = A[i]
    sub = A[i]-amin
    if sub == submax:
        total += 1
    if sub > submax:
        total = 1
        submax = sub

print(total)

Submission status: Accepted

Solution code:
n,t = map(int,input().split())
l = list(map(int,input().split()))

mx = 0
mn = l[0]
r = []
for i in range(1,len(l)):
    if mx <= l[i]-mn:
        mx = l[i]-mn
        r.append(mx)
    mn = min(mn,l[i])

e = sorted(r)[len(r)-1]
print(r.count(e))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

def main():
    n, t = [int(i) for i in raw_input().split()]
    a_list = [int(i) for i in raw_input().split()]
    num_max_gain = 0
    max_gain = 0
    cur_min_cost = a_list[0]
    for i in xrange(1, len(a_list)):
        b_a, a = a_list[i-1], a_list[i]
        if b_a > a:
            cur_min_cost = min(cur_min_cost, a)
        else:
            gain = a-cur_min_cost
            if gain > max_gain:
                num_max_gain = 1
                max_gain = gain
            elif gain == max_gain:
                num_max_gain += 1
    print num_max_gain

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, t = map(int, input().split())
a = list(map(int, input().split()))
maxa = a.pop()
max_rizaya, count = 0, 0
while a:
    ca = a.pop()
    rizaya = maxa - ca
    if rizaya > max_rizaya:
        max_rizaya = rizaya
        count = 1
    elif rizaya == max_rizaya:
        count += 1
    maxa = max(maxa, ca)
print(count)

Submission status: Runtime Error

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

dp = [[0] * (N + 1) for _ in range(N + 1)]

max_num = max(A)
max_index = A.index(max_num)

idx = 0
dfe = 0
count = 0
while True:
    print(idx)
    if idx >= len(A) - 1:
        break
    max_num = max(A[idx:])
    max_index = A.index(max_num)

    min_num = min(A[idx:max_index + 1])
    if dfe == max_num - min_num:
        count += 1
    elif dfe < max_num - min_num:
        dfe = max_num - min_num
        count = 1

    idx = max_index + 1

print(count)

Submission status: Runtime Error

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n,t = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]
    d = []
    u = []
    pv = 1000000
    for i in range(n-1):
        if pv > a[i] < a[i+1]:
            d.append(a[i])
        elif pv < a[i] > a[i+1]:
            u.append(a[i])
        if a[i] != a[i+1]:
            pv = a[i]

    if pv < a[-1]:
        u.append(a[-1])

    ds = []
    if len(u) != len(d):
        print(asdasd)
    for ui,di in zip(u,d):
        ds.append(ui-di)
    dma = max(ds)
    cnt = 0
    for i in ds:
        if dma == i:
            cnt += 1
    print(cnt)
    return None

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
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])
    # l <= i < r
    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()))
    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())

Submission status: Runtime Error

Solution code:
n, t = map(int, input().split())
l = [int(i)for i in input().split()]

if t <= 1 or all(b >= a for a, b in zip(l, l[1:])):
    print(0)
else:
    mini = float("inf")
    maxp = 0
    maxc = 0
    for n in l:
        if n - mini > maxp:
            maxp = n - mini
            maxc = 1
        elif n - mini == maxp:
            maxp = n - mini
            maxc += 1
        mini = min(mini, n)
print(maxc)

Submission status: Runtime Error

Solution code:

def main():
    n,t = map(int,input().split())
    lst = list(map,int(input().split()))
    mn = 999999999999999999999999999
    counter = 0
    diff = 0

    for m in lst:
        if m < mn: #最小値の更新
            mn = m
        elif m - mn == diff: #最大値が同じものの数を+1
            counter += 1
        elif m - mn > diff: #最大値を更新
            counter = 1
            diff = m - mn

    print(counter)




if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# ABC047D

import sys# ABC047D

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


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

M = -1
m = 10**10
best = 0
count = 0
for num in a[::-1]:
    if M<num:
        M = num
        m = M
    elif num<m:
        m = num
    if best<(M-m):
        best = M - m
        count = 1
    elif best==(M-m):
        count += 1
#     print(M, m, count, best)
print(count) if t%2==0 else print(1)
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


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

M = -1
m = 10**10
best = 0
count = 0
for num in a[::-1]:
    if M<num:
        M = num
        m = M
    elif num<m:
        m = num
    if best<(M-m):
        best = M - m
        count = 1
    elif best==(M-m):
        count += 1
#     print(M, m, count, best)
print(count)