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: Time Limit Exceeded

Solution code:
[n,t]=list(map(int,input().split()))
alist=list(map(int,input().split()))
salist=[alist[1]-alist[0]]
for i in range(1,n-1):
	saisho=min(alist[0:i])
	salist.append(alist[i+1]-saisho)
saidai=max(salist)
kaisu=salist.count(saidai)
print(kaisu)

Submission status: Time Limit Exceeded

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

B=[0]*(n-1)
for i in range(1,n):
  B[i-1]=A[i]-min(A[:i])
print(B.count(max(B)))

Submission status: Time Limit Exceeded

Solution code:
N,T = map(int, input().strip().split(' '))
A = list(map(int, input().strip().split(' ')))
ans = 1
prev_ans = None
max_score = 0
l_min = float('inf')
r_max = 0
for i in range(1, N):
  if A[i-1] >= r_max:
    r_max = max(A[i:])
  if A[i-1] <= l_min:
    l_min = A[i-1]
  score = r_max - l_min
  if score > max_score:
    max_score = score
    prev_ans = l_min
    ans = 1
  elif score == max_score:
    if prev_ans != l_min:
      prev_ans = l_min
      ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,T = map(int, input().strip().split(' '))
A = list(map(int, input().strip().split(' ')))
ans = set()
max_score = 0
l_min = float('inf')
r_max = 0
for i in range(1, N):
  if A[i-1] >= r_max:
    r_max = max(A[i:])
  if A[i-1] <= l_min:
    l_min = A[i-1]
  score = r_max - l_min
  if score > max_score:
    max_score = score
    ans = {l_min}
  elif score == max_score:
    ans.add(l_min)
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
N,T = map(int, input().strip().split(' '))
A = list(map(int, input().strip().split(' ')))
ans = 1
max_score = 0
for i in range(1, N):
  score = min(A[:i])-max(A[i:])
  if score > max_score:
    max_score = score
    ans = 1
  elif score == max_score:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N,T=list(map(int,input().split(" ")))
A=list(map(int,input().split(" ")))
m=0
for i in range(1,N):
    a=min(A[:i])
    b=max(A[i:])
    if b-a>m:
        m=b-a
        sub=defaultdict(lambda:0)
        sub[str([a,b])]
    elif b-a==m:
        sub[str([a,b])]
c=sub.keys()
print(len(c))

Submission status: Time Limit Exceeded

Solution code:
n, t = map(int, input().split(" "))
list_a = list(map(int, input().split(" ")))
list_profit = []
for i, a in enumerate(list_a[:-1]):
  max_price = max(list_a[(i+1):])
  if a < max_price:
    list_profit.append(max_price - a)
  else:
    list_profit.append(0)
max_profit = max(list_profit)
print(list_profit.count(max_profit))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,t = map(int, input().split())
i =0
As =list(map(int, input().split()))
Cs =[]

while True:
    m = max(As)
    l = As.index(m)

    if As[0] == m:
        As = As[(l+1):]

    else:
        Bs = As[:l]
        Cs.append(m-min(Bs))
        As = As[(l+1):]


    if len(As) == 0:
        break
if len(Cs) == 0:
    print(0)
else:
    print(Cs.count(max(Cs)))

Submission status: Time Limit Exceeded

Solution code:
n,t,*a=map(int,open(0).read().split())
amin = [10**9+1] + [0]*n
amax = [0]*(n+1)
for i,x in enumerate(a):
	amin[i+1] = min(amin[i],x)
for i,x in enumerate(a[::-1]):
	amax[i+1] = max(amax[i],x)
d = max(i-j for i,j in zip(amax[-2::-1], amin[1:]))
dp = [[0]*(n+1) for _ in range(n+1)]
for i in range(n):
	for j in range(n):
		if a[i]-a[j]==d:
			dp[i+1][j+1] = dp[i][j] + 1
		else:
			dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,t = map(int, input().split())
i =0
As =list(map(int, input().split()))
Bs =[]
z = 0
for i in range(n-1):
    x = As[0]
    As = As[1:]
    y = max(As)-x
    if y >=z:
        z=y
        Bs.append(y)

print(Bs.count(max(Bs)))

Submission status: Time Limit Exceeded

Solution code:
n,t = map(int, input().split())
i =0
As =list(map(int, input().split()))
Bs =[]
z = 0
for i in range(n-1):
    x = As[0]
    As = As[1:]
    y = max(As)-x

    if y >=z:
        z=y
        Bs.append(y)

print(Bs.count(max(Bs)))

Submission status: Time Limit Exceeded

Solution code:
n,t = map(int, input().split())
i =0
As =list(map(int, input().split()))

Bs =[]
for i in range(n-1):
    x = As[0]
    As = As[1:]

    y = max(As)
    Bs.append(y-x)

print(Bs.count(max(Bs)))

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

N, T = map(int, input().split())
l = list(map(int, input().split()))
sagaku_l = []
kouhomati = []
for i in range(N):
    for j in range(N - i - 1):
        sagaku = l[i + j + 1] - l[i]
        if sagaku > 0:
            sagaku_l.append([i, i + j + 1, sagaku])

# sagaku_max = max(zip(*sagaku_l))[0]
sagaku_l.sort(key=itemgetter(2), reverse=True)
# print(sagaku_l)
# print(len(sagaku_l))
for k in range(len(sagaku_l)):
    if sagaku_l[0][2] != sagaku_l[k][2]:
        break
    if not sagaku_l[k][0] in kouhomati:
        kouhomati.append(sagaku_l[k][0])
    if not sagaku_l[k][1] in kouhomati:
        kouhomati.append(sagaku_l[k][1])
print(len(kouhomati)/2)

Submission status: Time Limit Exceeded

Solution code:
N, T = map(int,input().split())
A = list(map(int,input().split()))
p = 0
ans = 0
for i in range(1, N):
    t = max(A[i:]) - A[i-1]
    if p == t:
        ans += 1
    elif p < t:
        p = t
        ans = 1
print(ans)

Submission status: Time Limit Exceeded

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

maxdiff = 0
ct = 0

for i in range(N):
    for j in range(i+1,N):
        if A[j]-A[i] > maxdiff:
            maxdiff = A[j]-A[i]
            ct = 1
        elif A[j]-A[i] == maxdiff:
            ct += 1

print(ct)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

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

diff = sorted([t[1]-t[0] for t in combinations(a, 2)], reverse=True)

print(diff.count(diff[0]))

Submission status: Time Limit Exceeded

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

max_bef = 0
cnt = 0

for i in range(1,N):
    tmp = A[i] - min(A[:i])
    if max_bef < tmp:
        max_bef = tmp
        cnt = 0
    if max_bef == tmp:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# minより右側にあるmaxの差 * Tすれば最大になる。その差が同じペアは別解としてある
# でもこうするとTの値は意味ないよなぁ
# 「自分より左側で最小の数」「自分より右側で最大の数」の配列を作って、再度頭からなめていけば最大の差とそれをとるペアがわかる

# PyPyだとREなって、Pythonだと2問TLEなる....

n, t = map(int, input().split())
arr = list(map(int, input().split()))
min_arr = [10**9+1 for _ in range(n)]
max_arr = [-1 for _ in range(n)]
now_min, now_max = 10**9+1, -1
for i in range(n):
    if now_min > arr[i]:
        now_min = arr[i]
    min_arr[i] = now_min
    if now_max < arr[-i - 1]:
        now_max = arr[-i-1]
    max_arr[-i - 1] = now_max

max_dif = 0
dif_paris = []
for i in range(n):
    if max_arr[i] - min_arr[i] > max_dif:
        max_dif = max_arr[i] - min_arr[i]
        dif_paris.clear()
        dif_paris.append([max_arr[i], min_arr[i]])
    elif max_arr[i] - min_arr[i] == max_dif:
        if [max_arr[i], min_arr[i]] not in dif_paris:
            dif_paris.append([max_arr[i], min_arr[i]])

print(len(dif_paris))

Submission status: Time Limit Exceeded

Solution code:
# minより右側にあるmaxの差 * Tすれば最大になる。その差が同じペアは別解としてある
# でもこうするとTの値は意味ないよなぁ
# 「自分より左側で最小の数」「自分より右側で最大の数」の配列を作って、再度頭からなめていけば最大の差とそれをとるペアがわかる
n, t = map(int, input().split())
arr = list(map(int, input().split()))
min_arr = [10**9 for _ in range(n)]
max_arr = [-1 for _ in range(n)]
now_min, now_max = 10**9, -1
for i in range(n):
    if now_min > arr[i]:
        now_min = arr[i]
    min_arr[i] = now_min
    if now_max < arr[-i - 1]:
        now_max = arr[-i-1]
    max_arr[-i - 1] = now_max

max_dif = 0
dif_paris = []
for i in range(n):
    if max_arr[i] - min_arr[i] > max_dif:
        max_dif = max_arr[i] - min_arr[i]
        dif_paris.clear()
        dif_paris.append([max_arr[i], min_arr[i]])
    elif max_arr[i] - min_arr[i] == max_dif:
        if [max_arr[i], min_arr[i]] not in dif_paris:
            dif_paris.append([max_arr[i], min_arr[i]])

print(len(dif_paris))

Submission status: Time Limit Exceeded

Solution code:
# minより右側にあるmaxの差 * Tすれば最大になる。その差が同じペアは別解としてある
# でもこうするとTの値は意味ないよなぁ
# 「自分より左側で最小の数」「自分より右側で最大の数」の配列を作って、再度頭からなめていけば最大の差とそれをとるペアがわかる
n, t = map(int, input().split())
arr = list(map(int, input().split()))
min_arr = [10**9 for _ in range(n)]
max_arr = [-1 for _ in range(n)]
now_min, now_max = 10**9, -1
for i in range(n):
    if now_min > arr[i]:
        now_min = arr[i]
    min_arr[i] = now_min
    if now_max < arr[-i - 1]:
        now_max = arr[-i-1]
    max_arr[-i - 1] = now_max


max_dif = 0
dif_paris = []
for i in range(n):
    if max_arr[i] - min_arr[i] > max_dif:
        max_dif = max_arr[i] - min_arr[i]
        dif_paris.clear()
        dif_paris.append([max_arr[i], min_arr[i]])
    elif max_arr[i] - min_arr[i] == max_dif:
        if [max_arr[i], min_arr[i]] not in dif_paris:
            dif_paris.append([max_arr[i], min_arr[i]])

print(len(dif_paris))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, T = map(int, input().split())

dp_matrix = np.zeros((N, 1))
price_list = np.array(list(map(int, input().split() )))
price_list = price_list.reshape((N, 1))

def max_selecting(m1, m2):
    '''
    input:
    m1, m2: np matrix (same size)
    output:
    m: np matrix
    '''
    m_bool1 = m1 > m2
    m_bool2 = m1 <= m2
    m = m1 * m_bool1 + m2 * m_bool2
    return m
  
for i in range(1, N+1):
    diff = (price_list[:] - price_list[i - 1]) * -1
    diff[i:] = 0
    dp_matrix[:] = max_selecting(dp_matrix[:], diff)
    
print(np.sum(dp_matrix[:] == np.max(dp_matrix[:])))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

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

cand = 0
cand_val = 0
for i in range(n):
    for j in range(i+1,n):
        if cand < a[j]-a[i]:
            cand = a[j]-a[i]
            cand_val = 1
        elif cand == a[j]-a[i]:
            cand_val += 1

print(cand_val)

Submission status: Time Limit Exceeded

Solution code:
def solve():
  n,t = (int(i) for i in input().split())
  a = list(int(i) for i in input().split())
  query = [-1*10**15]
  minA = a[0]
  for i in range(1,n):
    if minA < a[i]:
      if min(query) <= a[i]-minA:
        query.append(a[i]-minA)
    
    
    minA = min(minA,a[i])
  print(query.count(max(query)))
    
solve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

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

apple_price = list(map(int, input().split()))
price_diff = []

for i in range(n):
    if(i <= n-2):
        if(apple_price[i] < apple_price[i+1]):
            for j in range(i,n):
                diff = apple_price[j] - apple_price[i]
                if(diff>0):
                    price_diff.append(diff)
    else:
        for j in range(i, n):
            diff = apple_price[j] - apple_price[i]
            if (diff > 0):
                price_diff.append(diff)

if(price_diff):
    print(price_diff.count(max(price_diff)))
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

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

apple_price = list(map(int, input().split()))
price_diff = []

for i in range(n):
    for j in range(i,n):
        diff = apple_price[j] - apple_price[i]
        if(diff>0):
            price_diff.append(diff)

print(price_diff.count(max(price_diff)))

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, T = MAP()
A = LIST()
B = [sorted(A[i+1:N])[-1]-A[i] for i in range(N-1)]
# print(B)
print(B.count(max(B)))

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, T = MAP()
A = LIST()
B = [max(A[i+1:N])-A[i] for i in range(N-1)]
# print(B)
print(B.count(max(B)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

d = 0
c = 1

m = 0
while m < n - 1:
    i = np.argmax(a[m:])
    if i == 0:
        m += 1
        continue
    #print(i,m, a[i], a[m:m+i])
    j = np.argmin(a[m:m+i])
    x = a[m+j]
    y = a[m+i]
    #print(x, y, i, j, y - x)
    if y - x == d:
        c += 1
    elif y - x > d:
        d = y - x
        c = 1
    m += i
    #print(m, a[m:])

print(c)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

d = 0
c = 1

m = 0
while m < n - 1:
    y = np.max(a[m:])
    i = a.index(y)
    if i == m:
        m += 1
        continue
    x = np.min(a[m:i])
    if y - x == d:
        c += 1
    elif y - x > d:
        d = y - x
        c = 1
    m = i + 1

print(c)

Submission status: Time Limit Exceeded

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

b = dict()
for i in range(n):
    b[i] = a[i]

d = 0
c = 1

m = 0
while m < n - 1:
    y = max(a[m:])
    i = a.index(y)
    if i == m:
        m += 1
        continue
    x = min(a[m:i])
    if y - x == d:
        c += 1
    elif y - x > d:
        d = y - x
        c = 1
    m = i + 1

print(c)

Submission status: Time Limit Exceeded

Solution code:
n, T=map(int,input().split())
A = list(map(int,input().split()))
max_diff=0
cnt = 1
for i in range(n-1):
    for j in range(i+1,n):
        tmp_diff = A[j]-A[i]
        if max_diff < tmp_diff:
            max_diff  = tmp_diff
            cnt = 1
        elif max_diff == tmp_diff:
            cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n,t=map(int,input().split())
a=list(map(int,input().split()))
saisyo=min(a)
saidai=0
count=0

for i in range(n-1):
    x=a.pop()
    if x==saisyo:
        saisyo=min(a)
    elif x-saisyo>=saidai:
        mouke=x-saisyo
        if mouke>saidai:
            saidai=mouke
            count=1
        elif mouke==saidai:
            count+=1
    
print(count)

Submission status: Time Limit Exceeded

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

saisyo=min(a)
saidai=0
count=0

for i in range(n-1):
    x=a.pop()
    if x==saisyo:
        saisyo=min(a)
    elif x-saisyo>=saidai:
        mouke=x-saisyo
        if mouke>saidai:
            saidai=mouke
            count=1
        elif mouke==saidai:
            count+=1
    
print(count)

Submission status: Time Limit Exceeded

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

saisyo=min(a)
saidai=0
count=0

for i in range(n-1):
    x=a.pop()
    if x==saisyo:
        saisyo=min(a)
    elif x>saisyo:
        mouke=x-saisyo
        if mouke>saidai:
            saidai=mouke
            count=1
        elif mouke==saidai:
            count+=1
    
print(count)

Submission status: Time Limit Exceeded

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

def calc(a,i,saidai):
    if a[i]+saidai>big:return 0
    x=a[i]
    if i==len(a)-1:return 0
    else:return max(a[i+1:])-x

saidai=0
count=0
for i in range(n):
    ans=calc(a,i,saidai)
    if saidai<ans:
        saidai=ans
        count=1
    elif saidai==ans:count+=1
    
print(count)

Submission status: Time Limit Exceeded

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

def calc(a,i):
    x=a[i]
    if i==len(a)-1:return 0
    else:
        nokori=a[i+1:]
        return max(nokori)-x

saidai=0
count=0
for i in range(n):
    ans=calc(a,i)
    if saidai<ans:
        saidai=ans
        count=1
    elif saidai==ans:count+=1
    
print(count)

Submission status: Time Limit Exceeded

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

from collections import defaultdict
mouke=defaultdict(int)
def calc(a,i):
    x=a[i]
    if i==len(a)-1:return 0
    else:
        nokori=a[i+1:]
        return max(nokori)-x

saidai=0
for i in range(n):
    ans=calc(a,i)
    if saidai<ans:saidai=ans
    mouke[ans]+=1
    
print(mouke[saidai])

Submission status: Time Limit Exceeded

Solution code:
indexes = []


def dfs(Ds, s, e, v=None):
    if e - s == 1:
        if v == Ds[s]:
            indexes.append((s, e))
        return Ds[s]
    else:
        center = (s + e) // 2
        left = dfs(Ds, s, center, v=v)
        right = dfs(Ds, center, e, v=v)

        left_m = - (10 ** 9)
        li = -1
        for i in range(s, center):
            su = sum(Ds[i:center])
            if left_m != max(left_m, su):
                left_m = max(left_m, su)
                li = i

        right_m = -(10 ** 9)
        ri = -1
        for i in range(center + 1, e + 1):
            su = sum(Ds[center:i])
            if right_m != max(right_m, su):
                right_m = max(right_m, su)
                ri = i

        if left_m + right_m == v:
            indexes.append((li, ri))

        m = max(left, right, left_m + right_m)
        return m

def solve(N, T, As):
    Ds = [As[i + 1] - As[i] for i in range(N - 1)]
    max_v = dfs(Ds, 0, N - 1)
    dfs(Ds, 0, N - 1, v=max_v)
    return len(indexes)

if __name__ == "__main__":
    N, T = map(int, input().split(" "))
    As = list(map(int, input().split(" ")))
    print(solve(N, T, As))

Submission status: Time Limit Exceeded

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

MAX=[A[-1]]

for i in range(N-2,-1,-1):
    MAX.append(max(MAX[-1],A[i]))

MAX=MAX[::-1]
SABUN=[MAX[i]-A[i] for i in range(N)]

#print(MAX)
#print(SABUN)
MAXSA=max(SABUN)

SEG=[]
for i in range(N):
    if SABUN[i]==MAXSA:
        SEG.append(i)

SE=[SEG[0]]
for i in range(1,len(SEG)):
    if A[SEG[i]]!=A[SEG[i-1]]:
        SE.append(SEG[i])
    
SE.append(N)
#print(SEG)
#print(SE)

ANS=0
for i in range(1,len(SE)):
    x=SE[i-1]
    y=SE[i]

    ANSS=float("inf")
    for l in range(x+1,y):

        count1=A[x:l].count(A[x])
        if count1==0:
            continue

        for j in range(l,y):
            if A[j]==A[x]:
                count2=A[j:y].count(A[x]+MAXSA)

                if ANSS>count1+count2:
                    ANSS=count1+count2
                break

        else:
            if A[x]+MAXSA in A[x:l]:
                continue
            else:
                count3=A[l:y].count(A[x]+MAXSA)

                if ANSS>min(count1,count3):
                    ANSS=min(count1,count3)

        #print(l,ANSS,count1,count2)

    #print(ANSS)

    ANS+=ANSS

print(ANS)

Submission status: Time Limit Exceeded

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

aa = A[:]
aa.sort()
num = []
for i in range(N-1):
    aa.remove(A[i])
    num.append(aa[-1]-A[i])
    
print(num.count(max(num)))

Submission status: Time Limit Exceeded

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

num = []
for i in range(N-1):
    a = A[i+1:]
    num.append(max(a)-A[i])
print(num.count(max(num)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import defaultdict
N,T = map(int,input().split())
A = list(map(int,input().split()))
d = defaultdict(lambda:0)
for i in range(N-1):
    a = A[i+1:]
    d[max(a)-A[i]] += 1
print(d[max(d.keys())])

Submission status: Time Limit Exceeded

Solution code:
iN,iT = [int(_) for _ in input().split()]
aA = [int(_) for _ in input().split()]
iL = len(aA)

aMaxD = [0]
aMin=[aA[0]]
iV = 0

def checkMax(aMaxD,aMin,iB):
    iMaxD = 0
    for iMin in aMin:
        iMaxD = max(iMaxD,iB - iMin)
    if aMaxD[0] < iMaxD:
        aMaxD = [iMaxD]
    elif aMaxD[0] == iMaxD:
        aMaxD.append(iMaxD)
    return aMaxD

for i in range(1,iL):
    iB = aA[i-1]
    iN = aA[i]
    if iB - iN > 0:
        if iV >= 0:
            aMaxD = checkMax(aMaxD,aMin,iB)
        iV = -1
    elif iB - iN < 0:
        if iV <= 0:
            aMin.append(iB)
        if i == iL -1 :
            aMaxD = checkMax(aMaxD,aMin,iN)
        iV = 1
print( len(aMaxD) )

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys
sdin = sys.stdin.readline

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

# iまででの最高と最低
diff_list = [] # iを含むiまでの最低
max_list = [] # iを含まないiからの最高

mini = max(a)
maxi = max(a)

# iまでの最低と最高を更新
for i in range(n-1):
    if a[i] < mini:
        mini = a[i]
    
    if a[i] == maxi:
        maxi = max(a[i+1:])
        
    diff_list.append(maxi-a[i])
    
cnt = Counter(diff_list)

# 最大値の個数
print(cnt[max(cnt.keys())])

Submission status: Time Limit Exceeded

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

benefit = []
for i in range(len(a)):
    if i != 0:
        b = a[i] - min(a[:i])
        if not b <= 0:
            benefit.append(a[i] - min(a[:i]))

ans = Counter(benefit)
for _, c in ans.most_common(1):
    print(c)
    exit(0)

Submission status: Time Limit Exceeded

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

re = 0
max_dif = 0
for i in range(1, N):
    dif = A[i] - min(A[0:i])
    if max_dif < dif:
        max_dif = dif
        re = 1
    elif dif == max_dif:
        re += 1

print(re)

Submission status: Time Limit Exceeded

Solution code:
N, T = map(int, input().split())
A = [int(Ai) for Ai in input().split()]
B = [0] * len(A)
for i in range(1, len(A)):
    B[i] = A[i] - min(A[:i])
print(sum([Bi == max(B) for Bi in B]))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

c = defaultdict(int)
for i in range(N - 1):
    x = max(A[i + 1:])
    c[x - A[i]] += 1
print(c[max(c)])

Submission status: Time Limit Exceeded

Solution code:
a,b=map(int,input().split())
k=list(map(int,input().split()))

sa=0
ans=1
ma=max(k)

for i in range(a-1):
    if k[i]==ma:
        ma=max(k[i+1:a])
    tmp=ma-k[i]
    if tmp>sa:
        sa=tmp
        ans=1
    elif tmp==sa:
        ans+=1

    

print(ans)

Submission status: Time Limit Exceeded

Solution code:
a,b=map(int,input().split())
k=list(map(int,input().split()))

sa=[0]*a
ma=max(k)

for i in range(a-1):
    if k[i]==ma:
        ma=max(k[i+1:a])
    sa[i]=ma-k[i]

sa.sort()
sa.reverse()

ans=1
now=1

while sa[now]==sa[0]:
    ans+=1
    now+=1
    

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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


a_min = float("inf")
a_max = 0
a_diff = 0

counter = Counter([])

for a in A:
    hasModefied = False
    if a_min > a:
        a_min = a
        a_max = a
    if a_max < a:
        a_max = a
        hasModefied = True
        
    if hasModefied:        
        a_diff = a_max - a_min
        counter += {a_diff: 1}

keys = list(counter.keys())
max_key = max(keys)
print(counter[max_key])

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

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

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

# for i in range(n)
#     if a[i] > a[i + 1]:
#         continue
#     else:
#         benefits.append(max([a[j] - a[i]]))
# 

print(benefits.count(max(benefits)))

Submission status: Time Limit Exceeded

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

benefits = [max([a[j] - a[i] for j in range(i, n)]) for i in range(n)]

print(benefits.count(max(benefits)))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

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()]

    profs = {}
    for i in range(len(cities)):
        h = i + cities[i:].index(max(cities[i:]))
        #print("highest",i,h)
        profs[(i,h)] = T * (cities[h] - cities[i])

    maxProf = max(profs.values())
    ans = 0
    for v in profs.values():
        if v == maxProf:
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

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

B = [max(A[i:]) for i in range(1, N)]

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

print(ans)

Submission status: Time Limit Exceeded

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

B = [A[i:] for i in range(1, N)]

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

print(ans)

Submission status: Time Limit Exceeded

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

q=deque(A)
max_n=max(q)


b=[]
for i in range(N-1):
	q.popleft()
	if A[i]==max_n:
		max_n=max(q)

	b.append(max_n-A[i])

C=Counter(b)
max_key=max(C.keys())

print C[max_key]

Submission status: Time Limit Exceeded

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

q=deque( sorted(A, key=lambda x: x,reverse=True) )


b=[]
for i in range(N-1):
	q.remove(A[i])
	max_n=q[0]
	b.append(max_n-A[i])

C=Counter(b)
max_key=max(C.keys())

print C[max_key]

Submission status: Time Limit Exceeded

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

b=[]
for i in range(N-1):
	max_n=max(A[i+1::])
	b.append(max_n-A[i])

C=Counter(b)
max_key=max(C.keys())

print C[max_key]

Submission status: Time Limit Exceeded

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

l = list(map(int, input().split()))
maxdiff = 0
count = 0
startindex = 0
endindex = 0

i = 0
while i < n:
    # 最大値を見つける
    maxnum = 0
    maxindex = 0
    for j in range(i, n):
        if l[j] > maxnum:
            maxnum = l[j]
            maxindex = j
    #print("max: " + str(maxnum))
    #print("index: " + str(maxindex))
    if maxindex == i:
        i += 1
        continue
    # 最大の差を見つける
    for j in range(i, maxindex):
        if maxnum - l[j] > maxdiff:
            maxdiff = maxnum - l[j]
            count = 1
            #print("maxdiff: " + str(maxdiff))
            #print("count: " + str(count))
        elif maxnum - l[j] == maxdiff:
            count += 1
            #print("maxdiff: " + str(maxdiff))
            #print("count: " + str(count))
    i = maxindex + 1
print(count)