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

from sys import stdin
input = stdin.readline
import numpy as np
from collections import deque
H,W = map(int, input().rstrip().split())
CH,CW = map(int, input().rstrip().split())
DH,DW = map(int, input().rstrip().split())
[CH,CW,DH,DW] = [CH-1,CW-1,DH-1,DW-1]
S = np.array([list(input().rstrip()) for i in range(H)])
INF = 10 ** 9
Distance = np.ones((H,W))*INF
Distance[CH,CW] = 0
[nowH,nowW] = [CH,CW]
q = deque([])
q.append([nowH,nowW])
while len(q) != 0:
  [nowH,nowW] = q.popleft()
  if [nowH,nowW] == [DH,DW]:
    break
  for i in range(-1,2):
    for j in range(-1,2):
      if nowH+i < 0 or nowW+j < 0 or nowH+i >= H or nowW+j >= W:
        continue
      if S[nowH+i,nowW+j] != '.':
        continue
      if abs(i) + abs(j) != 1:
        continue
      if Distance[nowH,nowW] < Distance[nowH+i,nowW+j]:
        Distance[nowH+i,nowW+j] = Distance[nowH,nowW]
        if [nowH+i,nowW+j] in q:
          q.remove([nowH+i,nowW+j])
        q.appendleft([nowH+i,nowW+j])
  for i in range(-2,3):
    for j in range(-2,3):
      if nowH+i < 0 or nowW+j < 0 or nowH+i >= H or nowW+j >= W:
        continue
      if S[nowH+i,nowW+j] != '.':
        continue
      if abs(i) + abs(j) < 2:
        continue
      if Distance[nowH,nowW] + 1 < Distance[nowH+i,nowW+j]:
        Distance[nowH+i,nowW+j] = Distance[nowH,nowW] + 1
        q.append([nowH+i,nowW+j])
if Distance[DH,DW] == INF:
  print(-1)
else:
  print(int(Distance[DH,DW]))

### FIXED CODE ###

from collections import deque
H,W = map(int, input().split())
CH,CW = map(lambda x: int(x) - 1, input().split())
DH,DW = map(lambda x: int(x) - 1, input().split())
S = [input() for i in range(H)]
INF = 10 ** 9
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]
h = CH
w = CW
Distance = [[INF] * W for _ in range(H)]
Distance[h][w] = 0
q = deque(())
q.append((h,w))
while q:
  h,w = q.popleft()
  if [h,w] == [DH,DW]:
    break
  for i,j in walk:
    hwalk = h + i
    wwalk = w + j
    if 0 <= hwalk < H and 0 <= wwalk < W and S[hwalk][wwalk] == '.' and Distance[h][w] < Distance[hwalk][wwalk]:
      Distance[hwalk][wwalk] = Distance[h][w]
      q.appendleft((hwalk,wwalk))
  for i,j in warp:
    hwalk = h + i
    wwalk = w + j
    if 0 <= hwalk < H and 0 <= wwalk < W and S[hwalk][wwalk] == '.' and Distance[h][w] + 1 < Distance[hwalk][wwalk]:
      Distance[hwalk][wwalk] = Distance[h][w] + 1
      q.append((hwalk,wwalk))
print(int(Distance[DH][DW]) if Distance[DH][DW] != INF else -1)
### BUGGY CODE ###

n,*p=map(int,open(0).read().split())
cnt=0
flg=True
for i in range(n):
  flg=True
  for j in range(0,i):
    if p[i]>p[j]:
      flg=False
      break
  if flg:
    cnt+=1
print(cnt)    
   

### FIXED CODE ###

n,*p=map(int,open(0).read().split())
_min=max(p)
cnt=0
for i in p:
  _min=min(_min,i)
  if i>_min:
    cnt+=1
print(n-cnt)
### BUGGY CODE ###

from itertools import combinations

N,K=map(int,input().split())
o=[tuple(map(int,input().split())) for _ in range(N)]
ans=float("inf")

for i,j in combinations(o,2):
    x1,y1=i
    x2,y2=j
    xmax,xmin=max(x1,x2),min(x1,x2)

    for k,l in combinations(o,2):
        x3,y3=k
        x4,y4=l
        ymax,ymin=max(y3,y4),min(y3,y4)

        v=0
        for m in o:
            x5,y5=m
            if xmin<=x5<=xmax and ymin<=y5<=ymax:
                v+=1
        
        if v>=K:
            ans=min(ans,(ymax-ymin)*(xmax-xmin))


print(ans)

### FIXED CODE ###

from itertools import combinations as comb
n,k=map(int,input().split())
f=lambda x,y:(min(x,y),max(x,y))
o=[tuple(map(int,input().split())) for _ in range(n)]

v=float("inf")
for (a,b) in comb(range(n),2):
  for (c,d) in comb(range(n),2):
    lx,rx=f(o[a][0],o[b][0])
    dy,uy=f(o[c][1],o[d][1])
    cnt=0
    for i in o:
      if lx<=i[0]<=rx and dy<=i[1]<=uy:
        cnt+=1
    if cnt>=k:
      v=min(v,(rx-lx)*(uy-dy))
print(v)
### BUGGY CODE ###

# 初期入力
#棒を長さでソートし、
N = int(input())
L = list(map(int, input().split()))
L_sorted =sorted(L)

#3本選ぶ組み合わせ,1番長いもの2本決めると、短いものは最低の長さが決まる=0
import bisect

count =[]
for i in range(N-1,1,-1): #一番長い
    for j in range(i-1,0,-1):#真ん中
        x =L_sorted[i] - L_sorted[j]
        index =bisect.bisect_right(L_sorted,x,lo=0,hi=j)
        a=0
        if 0<=index +a and index + a <= N:
            count.append(j-(index+a))
           # print(L_sorted[i],L_sorted[j],L_sorted[index+a],index,x)

print(sum(count))

### FIXED CODE ###

import bisect

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

count  =0
L.sort()
for i in range(0, N - 1):
  for j in range(i + 1, N):
    index = bisect.bisect_left(L, L[i] + L[j]) #AC:約2.9秒
    count += max(0, index - j - 1)

"""
    失敗:回答は出るがTLE:ランダム配列1000本で約6.2秒
    index = bisect.bisect_left(L[j+1:],L[i] + L[j]) #TLEの原因?
    count += index
"""
print(count)
### BUGGY CODE ###

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

t = 1
for _ in range(k):
    t = a[t-1]

print(t)

### FIXED CODE ###

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

pos = 0
visit = [0]*n
move = []
roop = []
while visit[pos] != 2:
    if visit[pos] == 0:
        move.append(pos)
    else:
        roop.append(pos)
    visit[pos] += 1
    pos = a[pos] - 1
if len(move) > k:
    print(move[k]+1)
else:
    print(roop[(k-(len(move)-len(roop))) % len(roop)]+1)
### BUGGY CODE ###

l, r = map(int, input().split())

if l - r >= 2019:
    print(0)
else:
    n = range(l, r+1)
    min_x = 2018
    for i in range(len(n)-1):
        for j in range(i+1, len(n)):
            cur_x = n[i]*n[j] % 2019
            min_x = min(cur_x, min_x)
            if min_x == 0:
                break
    print(min_x)

### FIXED CODE ###

l, r = map(int, input().split())
if l - r >= 2019:
    print(0)
else:
    n = range(l, r+1)
    min_x = 2018
    for i in range(len(n)-1):
        for j in range(i+1, len(n)):
            cur_x = ((n[i]%2019)*(n[j]%2019))%2019
            min_x = min(cur_x, min_x)
            if min_x == 0:
                break
        if min_x == 0:
                break
    print(min_x)
### BUGGY CODE ###

h = int(input())
n = 0
while True:
    h = h//2
    n += 1
    if h == 1:
        break
        
print(2**(n+1)-1)

### FIXED CODE ###

h = int(input())
n = 0
import math
while h > 0:
    h = math.floor(h/2)
    n += 1
        
print(2**(n)-1)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
s = [0]
sum = 0
for i in range(len(a)):
    sum += a[i]
    s.append(sum)
ans = 0
for s_ in set(s):
    k = s.count(s_)
    ans += k*(k-1)//2
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
s = [0]
sum = 0
for i in range(len(a)):
    sum += a[i]
    s += [sum]
s.sort()
ans = 0
k = 1
for i in range(1,len(s)):
    if s[i]==s[i-1]:
        k+=1
        if i==len(s)-1:
            ans += k*(k-1)//2
    else:
        if k>1:
            ans += k*(k-1)//2
        k = 1
print(ans)
### BUGGY CODE ###

n = int(input())
ans = 0
for a in range (1,n):
    for b in range(1, n):
        if n <= a * b:
            break
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
for a in range (1,n):
    for b in range(a, n, a):
        ans += 1
print(ans)
### BUGGY CODE ###

H, N = map(int, input().split())
magics = []
min_cost = (0, 100000)
max_attack = (0, 100000)
for i in range(N):
    attack, cost = map(int, input().split())
    magics.append((attack,cost))
    if cost < min_cost[1]:
        min_cost = (attack, cost)
    if max_attack[0] < attack:
        max_attack = (attack, cost)
    

dp = [0]
dp.extend([min_cost[1]] * min_cost[0])
for i in range(min_cost[0]+1, H + max_attack[0] + 1):
    minc = 100000000000
    for magic in magics:
        cost = magic[1]
        if 0 < i - magic[0]:
            cost += dp[i - magic[0]]
        if cost < minc:
            minc = cost
    dp.append(minc)
print(min(dp[H:]))

### FIXED CODE ###

H, N = map(int, input().split())
magics = []
min_cost = (0, 100000)
max_attack = (0, 100000)
for i in range(N):
    attack, cost = map(int, input().split())
    magics.append((attack,cost))
    if cost < min_cost[1]:
        min_cost = (attack, cost)
    if max_attack[0] < attack:
        max_attack = (attack, cost)
    

dp = [0]
dp.extend([min_cost[1]] * min_cost[0])
for i in range(min_cost[0]+1, H + max_attack[0] + 1):
    minc = 100000000000
    for magic in magics:
        cost = magic[1]
        if 0 < i - magic[0]:
            cost += dp[i - magic[0]]
        if cost < minc:
            minc = cost
    dp.append(minc)
print(min(dp[H:]))
### BUGGY CODE ###

#import sys
#input = sys.stdin.readline

S = input()
Q = int(input())
W = 0
ans = S

for _ in range(Q):
#    print(W,ans)
    qry = list(input().split())
    if qry[0] == "1":
        W = 1-W
        continue
    T,F,C = qry
    T = int(T)
    F = int(F)
    if (W == 0 and F==2) or (W==1 and F==1):
        ans = ans+C
    else:
        ans = C+ans
if W == 1:
    ans = ans[::-1]
print(ans)

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())
W = 0
ans = deque(list(S.rstrip()))

for _ in range(Q):
#    print(W,ans)
    qry = list(input().rstrip().split())
    if qry[0] == "1":
        W = 1-W
        continue
    T,F,C = qry
    C.rstrip()
    if (W == 0 and F=="2") or (W==1 and F=="1"):
        ans.append(C)
    else:
        ans.appendleft(C)
ans = "".join(map(str,ans))
if W == 1:
    ans = ans[::-1]
print(ans)
### BUGGY CODE ###

n, x, y = map(int, input().split())
ans = [0] * n
a = [n] * n
x -= 1
y -= 1
for i in range(0, n):
    a = [n] * n
    a[i] = 0
    for j in range(i, 0, -1):
        if j == x:
            a[y] = min(a[y], a[j] + 1)
        if j == y:
            a[x] = min(a[x], a[j] + 1)
        a[j - 1] = min(a[j - 1], a[j] + 1)
    for j in range(i, n - 1):
        if j == x:
            a[y] = min(a[y], a[j] + 1)
        if j == y:
            a[x] = min(a[x], a[j] + 1)
        a[j + 1] = min(a[j + 1], a[j] + 1)
    for j in range(x, 0, -1):
        if j == x:
            a[y] = min(a[y], a[j] + 1)
        if j == y:
            a[x] = min(a[x], a[j] + 1)
        a[j - 1] = min(a[j - 1], a[j] + 1)
    for j in range(x, n - 1):
        if j == x:
            a[y] = min(a[y], a[j] + 1)
        if j == y:
            a[x] = min(a[x], a[j] + 1)
        a[j + 1] = min(a[j + 1], a[j] + 1)
    for j in range(y, 0, -1):
        if j == x:
            a[y] = min(a[y], a[j] + 1)
        if j == y:
            a[x] = min(a[x], a[j] + 1)
        a[j - 1] = min(a[j - 1], a[j] + 1)
    for j in range(y, n - 1):
        if j == x:
            a[y] = min(a[y], a[j] + 1)
        if j == y:
            a[x] = min(a[x], a[j] + 1)
        a[j + 1] = min(a[j + 1], a[j] + 1)
    for k in range(0, n):
        if k != i:
            ans[a[k]] += 1
for i in range(1, n):
    print(ans[i] // 2)


### FIXED CODE ###

n, x, y = map(int, input().split())
ans = [0] * n
a = [n] * n
x -= 1
y -= 1
for i in range(0, n):
    a = [n] * n
    a[i] = 0
    b = [i, x, y, x, y]
    for k in b:
        for j in range(k, 0, -1):
            if j == x:
                a[y] = min(a[y], a[j] + 1)
            if j == y:
                a[x] = min(a[x], a[j] + 1)
            a[j - 1] = min(a[j - 1], a[j] + 1)
        for j in range(k, n - 1):
            if j == x:
                a[y] = min(a[y], a[j] + 1)
            if j == y:
                a[x] = min(a[x], a[j] + 1)
            a[j + 1] = min(a[j + 1], a[j] + 1)
    for k in range(0, n):
        ans[a[k]] += 1
for i in range(1, n):
    print(ans[i] // 2)
### BUGGY CODE ###

n,k = map(int, input().split())
H = [0]+list(map(int, input().split()))
dp = [float("inf")]*(n+1)
dp[0] = 0
dp[1] = 0

for i in range(1, n):
  for k_i in range(1, k+1):
    if i+k_i<=n:
      dp[i+k_i] = min(dp[i+k_i], dp[i]+abs(H[i+k_i]-H[i]))
      
print(dp[-1])

### FIXED CODE ###

n,k = map(int, input().split())
H = [0]+list(map(int, input().split()))
dp = [float("inf")]*(n+1)
dp[0] = 0
dp[1] = 0

for i in range(1, n):
  for k_i in range(1, k+1):
    if i+k_i<=n:
      dp[i+k_i] = min(dp[i+k_i], dp[i]+abs(H[i+k_i]-H[i]))
      
print(dp[-1])
### BUGGY CODE ###

import sys

fin = sys.stdin.readline

N, M = map(int, fin().split())
As = list(map(int, fin().split()))
BC = [tuple(map(int, fin().split())) for _ in range(M)]

As = sorted(As)
# BC = sorted(BC, key=lambda x: x[1], reverse=True)

BC_ = {}
for num, val in BC:
    if val in BC_:
        BC_[val] += num
    else:
        BC_[val] = num

BC_ = sorted(BC_.items(), reverse=True)

#
# def f(a, n, v):
#     if a[min(n-1, len(a)-1)] < v:
#         return v * min(n, len(a)), a[n:]
#     count = 0
#     for i in range(min(n, len(a))):
#         if a[i] < v:
#             count += 1
#         else:
#             break
#     return v * count, a[count:]


sum__ = 0
for val, num in BC_:
    if len(As) == 0 or As[0] >= val:
        break

    if As[min(num - 1, len(As) - 1)] < val:
        sum_, As = val * min(num, len(As)), As[num:]
    else:
        count = 0
        for i in range(min(num, len(As))):
            if As[i] < val:
                count += 1
            else:
                break
        sum_, As = val * count, As[count:]
    sum__ += sum_

print(sum__ + sum(As))


### FIXED CODE ###

import sys

fin = sys.stdin.readline

N, M = map(int, fin().split())
As = list(map(int, fin().split()))
BC = [tuple(map(int, fin().split())) for _ in range(M)]

As = sorted(As)
# BC = sorted(BC, key=lambda x: x[1], reverse=True)

BC_ = {}
for num, val in BC:
    if val in BC_:
        BC_[val] += num
    else:
        BC_[val] = num

BC_ = sorted(BC_.items(), reverse=True)

#
# def f(a, n, v):
#     if a[min(n-1, len(a)-1)] < v:
#         return v * min(n, len(a)), a[n:]
#     count = 0
#     for i in range(min(n, len(a))):
#         if a[i] < v:
#             count += 1
#         else:
#             break
#     return v * count, a[count:]


sum__ = 0
now = 0
for val, num in BC_:
    if now >= len(As) or As[now] >= val:
        break

    if As[min(num - 1 + now, len(As) - 1)] < val:
        sum_ = val * min(num, len(As) - now)
        now += min(num, len(As) - now)
    else:
        count = 0
        for i in range(min(num, len(As)-now)):
            if As[i + now] < val:
                count += 1
            else:
                break
        sum_ = val * count
        now += count
    sum__ += sum_

print(sum__ + sum(As[now:]))
### BUGGY CODE ###

import itertools

N = int(input())
nums = []
for _ in range(N):
    num = input().split(".")
    if len(num) == 2:
        nums.append([int(num[0]), int(num[1]), len(num[1])])
    else:
        nums.append([int(num[0]),0,0])
ans = 0
for i,j in itertools.combinations(range(N),2):
    l = nums[i][1]*nums[j][1] + nums[i][0]*nums[j][1]*(10**nums[i][2]) + nums[i][1]*nums[j][0]*(10**nums[j][2])
    if l%(10**(nums[i][2]+nums[j][2])) == 0:
        ans += 1
print(ans)    

### FIXED CODE ###

from collections import defaultdict
from math import gcd
nums = defaultdict(int)
for _ in range(int(input())):
  nums[gcd(round(float(input())*(10**9)),10**18)] += 1
nums = tuple(nums.items())
ans = 0
for i, (a,b) in enumerate(nums):
  if a*a%(10**18) == 0:
    ans += b*(b-1)//2
  for (c,d) in nums[i+1:]:
    if a*c%(10**18) == 0:
      ans += b*d
print(ans)
### BUGGY CODE ###

def main():
  from sys import exit
  n = int(input())
  a = [list(map(int, input().split())) for _ in range(n)]
  ilist = [0] * n
  days = 1
  finished = 0
  while True:
    booked = [False] * n
    books = 0
    for i in range(n):
      if booked[i]:
        continue
      ii = ilist[i]
      if ii == n - 1:
        continue
      j = a[i][ii] - 1
      if booked[j]:
        continue
      if a[j][ilist[j]] - 1 != i:
        continue
      books += 1
      booked[i] = True
      booked[j] = True
      ilist[i] += 1
      if ilist[i] == n -1:
        finished += 1
      ilist[j] += 1
      if ilist[j] == n -1:
        finished += 1
    if books == 0:
      print(-1)
      exit()
    if finished == n:
      break
    days += 1
  print(days)
main()


### FIXED CODE ###

from sys import exit, setrecursionlimit
setrecursionlimit(1000000)

def dfs(v, dp, to):
  t = dp[v]
  if t >= 0:
    return t
  dp[v] = 0
  t = 0
  for u in to[v]:
    res = dfs(u, dp, to)
    if res == 0:
      print('-1')
      exit()
    if res > t:
      t = res
  t += 1
  dp[v] = t
  return t

def toId(i, j, id_db):
  if i < j:
    return id_db[i][j]
  else:
    return id_db[j][i]

def main():
  N = int(input())
  a = [[int(e) - 1 for e in input().split()] for _ in range(N)]

  id_db = [[0] * N for _ in range(N)]

  dp = [-1] * (N * (N - 1) // 2)
  to = [[] for _ in range(N * (N - 1) // 2)]

  v = 0
  for i in range(N):
    for j in range(i + 1, N):
      id_db[i][j] = v
      v += 1

  for i in range(N):
    for j in range(N - 1):
      a[i][j] = toId(i, a[i][j], id_db)
    for j in range(N - 2):
      to[a[i][j + 1]].append(a[i][j])

  print(max(dfs(i, dp, to) for i in range(N * (N - 1) // 2)))

main()
### BUGGY CODE ###

# ABC 137, c
from collections import Counter
import math
n = int(input())
S = []
for i in range(n):
    s = ''.join(sorted(input()))
    S.append(s)
count = 0
for i in range(n):
    for j in range(i+1, n):
        if S[i] == S[j]:
            count += 1
print(count)










### FIXED CODE ###

# ABC 137, c
n = int(input())
S = []
D = {}
count = 0
for i in range(n):
    s = ''.join(sorted(input()))
    if s in D:
        count += D[s]
        D[s] += 1
    else:
        D[s] =1
print(count)
### BUGGY CODE ###

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

now = 1
pre = 0
for i in range(0,n[1]):
    now *= a[i]

for i in range(n[1],n[0]):
    pre = now
    if a[i-n[1]] == 0:
        now = 1
    else:
        now /= a[i-n[1]]
    now *= a[i]
    if now > pre:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

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

for i in range(n[1],n[0]):
    if a[i-n[1]] < a[i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, M, K = map(int, readline().split())
MOD = 998244353
# Combination under a prime modulo: nCk % p
def combmod(n, k, p):
    if k > n:
        return 0
    if k > n - k:
        k = n - k
    num, den = 1, 1
    for i in range(k):
        num = num * (n - i) % p
        den = den * (i + 1) % p
    # By Fermat's little theorem,
    # a^(p-1) ≡ 1 mod p
    # i.e. a^(p-2) ≡ a^(-1) mod p
    inv_dev = pow(den, p - 2, p)
    return num * inv_dev % p


def solve():
    ans = 0
    for i in range(K + 1):
        ans += combmod(N - 1, i, MOD) * M * pow(M - 1, N - 1 - i, MOD)
        ans %= MOD
    return ans


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


### FIXED CODE ###

#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, M, K = map(int, readline().split())
MOD = 998244353

def solve():
    m1pows = [1 for i in range(K + 1)]
    m1pows[0] = M * pow(M - 1, N - 1 - K, MOD) % MOD
    for i in range(1, K + 1):
        m1pows[i] = m1pows[i - 1] * (M - 1) % MOD
    cs = 1
    ans = 0
    for i in range(K + 1):
        ans += cs * m1pows[K - i]
        ans %= MOD
        cs *= (N - 1 - i) * pow(i + 1, MOD - 2, MOD)
        cs %= MOD
    return ans


if __name__ == "__main__":
    print(solve())
### BUGGY CODE ###

n = int(input())
ai = list(map(int,input().split()))
pl = []
mi = []
for i in range(n):
    pl.append(i+ai[i])
    mi.append(i-ai[i])
cnt = 0 
for i in range(n):
    cnt += mi.count(pl[i])
print(cnt)

### FIXED CODE ###

from collections import Counter
n = int(input())
ai = list(map(int,input().split()))
pl = []
mi = []
for i in range(n):
    pl.append(i+ai[i])
    mi.append(i-ai[i])
x = Counter(pl)
y = Counter(mi)
cnt = 0
for i in x.keys():
    cnt += x[i]*y[i]
print(cnt)
### BUGGY CODE ###

def main():
    n = int(input())
    r = []
    ans = 0
    for i in range(n):
        r.append(int(input()))

    ans = min(r) - max(r)
    for i in reversed(range(1, n)):
        tmpr = r[:i]
        tmp = r[i] - min(tmpr)
        if tmp > ans:
            ans = tmp
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    ans = 0
    minr = int(input())
    ans = -1 * 10**9
    for i in range(n-1):
        r = int(input())
        ans = max(ans, r-minr)
        minr = min(minr, r)

    print(ans)


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

N, M = map(int, input().split())
*a, = map(int, input().split())
BC = []
for _ in range(M):
    b, c = map(int, input().split())
    BC.append((b, c))
a.sort()
BC = sorted(BC, key=lambda x: x[1], reverse=True)
ans = 0
for b, c in BC:
    for _ in range(b):
        if a[0] < c:
            ans += c
            a = a[1:]
        else:
            break
ans += sum(a)
print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
a = [(1, int(i)) for i in input().split()]
for _ in range(m):
    b, c = map(int, input().split())
    a.append((b, c))
a = sorted(a, key=lambda x: x[1])
ans = 0
t = 0
while t < n:
    b, c = a.pop()
    p = min(b, n-t)
    ans += p * c
    t += p
print(ans)
### BUGGY CODE ###

k = int(input())
import math
from functools import reduce

l = []
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def gcd_list(numbers):
    return reduce(math.gcd, numbers)

for i in range(1, k+1):
    for j in range(1, k+1):
        for m in range(1, k+1):
            n = gcd(i, j, m)
            l.append(n)
print(sum(l))

### FIXED CODE ###

k = int(input())
import math
from functools import reduce

l = []
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def gcd_list(numbers):
    return reduce(math.gcd, numbers)

for i in range(1, k+1):
    for j in range(1, k+1):
        for m in range(1, k+1):
            n = gcd(i, j, m)
            l.append(n)
print(sum(l))
### BUGGY CODE ###

[l,r] = [int(i) for i in input().split()]

ans = 2018


for i in range(l,r):
	for j in range(i+1,r+1):
		rem = i*j%2019
		if rem < ans:
			ans = rem
			if ans == 0:
				break
print(ans)	

### FIXED CODE ###

L, R = list(map(int, input().split(' ')))
#print(L, R)
 
min = 2019
for i in range(L, R):
    for j in range(i + 1, R + 1):
        mod_ij = (i * j) % 2019
        if min > mod_ij:
            min = mod_ij
            if min == 0:
                break
    if min == 0:
        break
print(min)
### BUGGY CODE ###

import fractions
K = int(input())
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        g = fractions.gcd(i,j)
        for k in range(1,K+1):
            ans += fractions.gcd(g,k)
print(ans)

### FIXED CODE ###

import fractions
K = int(input())
ans = 0
dp = []
for i in range(0,K+1):
    dpp = []
    for j in range(0,K+1):
        dpp.append(0)
    dp.append(dpp)
def dpgcd(a,b):
    if dp[a][b] != 0:
        return dp[a][b]
    else:
        gg = fractions.gcd(a,b)
        dp[a][b] = gg
        dp[b][a] = gg
        return gg
for i in range(0,K):
    for j in range(0,K):
        g = dpgcd(i+1,j+1)
        for k in range(0,K):
            ans += dpgcd(g,k+1)
print(ans)