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

from collections import deque
n,m,s,t = map(int,input().split())
edgem = [[]for i in range(n)]
edges = [[]for i in range(n)]
for i in range(m):
    u,v,a,b = map(int,input().split())
    edgem[u-1].append([v-1,a])
    edgem[v-1].append([u-1,a])
    edges[u-1].append([v-1,b])
    edges[v-1].append([u-1,b])

costm = [float('inf')]*n
costs = [float('inf')]*n
costm[s-1],costs[t-1] = 0,0

queue = deque([s-1])
while queue.__len__() > 0:
    p = queue.popleft()
    for a,b in edgem[p]:
        if costm[a] > costm[p] + b:
            costm[a] = costm[p] + b
            queue.append(a)
queue = deque([t-1])
while queue.__len__() > 0:
    p = queue.popleft()
    for a,b in edges[p]:
        if costs[a] > costs[p] + b:
            costs[a] = costs[p] + b
            queue.append(a)
ans = [float('inf')]*n
for i in range(n):
    ans[i] = costm[i] + costs[i]
for i in range(n-1,0,-1):
    ans[i-1] = min(ans[i-1],ans[i])
money = 10**15
for i in ans:
    print(money-i)

### FIXED CODE ###

from collections import deque
n,m,s,t = map(int,input().split())
edgem = [[]for i in range(n)]
edges = [[]for i in range(n)]
for i in range(m):
    u,v,a,b = map(int,input().split())
    edgem[u-1].append([v-1,a])
    edgem[v-1].append([u-1,a])
    edges[u-1].append([v-1,b])
    edges[v-1].append([u-1,b])

costm = [float('inf')]*n
costs = [float('inf')]*n
costm[s-1],costs[t-1] = 0,0

queue = deque([s-1])
while queue.__len__() > 0:
    p = queue.popleft()
    for a,b in edgem[p]:
        if costm[a] > costm[p] + b:
            costm[a] = costm[p] + b
            queue.append(a)
queue = deque([t-1])
while queue.__len__() > 0:
    p = queue.popleft()
    for a,b in edges[p]:
        if costs[a] > costs[p] + b:
            costs[a] = costs[p] + b
            queue.append(a)
ans = [float('inf')]*n
for i in range(n):
    ans[i] = costm[i] + costs[i]
for i in range(n-1,0,-1):
    ans[i-1] = min(ans[i-1],ans[i])
money = 10**15
for i in ans:
    print(money-i)
### BUGGY CODE ###

import collections

n = int(input())
a = list(map(int, input().split(' ')))
c = collections.Counter(a)
dict_1 = {}
dict_2 = {}
for key, value in c.items():
    dict_1[key] = value * (value-1) // 2
    if value - 1 == 0:
        dict_2[key] = 0
    else:
        dict_2[key] = (value-1) * (value-2) // 2
    
for k in range(n):
    ans = 0
    for key, val in dict_1.items():
        if key == a[k]:
            ans += dict_2[key]
        else:
            ans += dict_1[key]
    print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split(' ')))
dic = {}
com = {}
ans = 0
for v in a:
    try:
        t = dic[v]
        ans += t
        com[v] += t
        dic[v] += 1
    except:
        dic[v] = 1
        com[v] = 0

for k in range(n):
    print(ans - (dic[a[k]]-1))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
s = 0
for i in range(1,n):
    for j in range(i):
        pro = a[i] * a[j]
        s = s + pro

mod = s % (10**9 + 7)

print(mod)



### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
s = sum(a) ** 2
b = []
for i in range (n):
    b.append(a[i]**2)
s = (s - sum(b)) // 2
mod = s % (10**9 + 7)
print(mod)
### BUGGY CODE ###

from fractions import Fraction as F
from fractions import gcd

MOD = 10 ** 9 + 7

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

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

# B_1 = 1と仮定
b = [F(1, 1)]
for i in range(1, n):
    b.append(F(a[0], a[i]))

al_lcm = 1
for i in b:
    al_lcm = lcm(al_lcm, i.denominator)

res = 0
for i in b:
    res += i.numerator * pow(i.denominator, MOD - 2, MOD) % MOD * al_lcm % MOD

# lcmめっちゃ大きくなってそう

print(res % MOD)


### FIXED CODE ###

mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
def gcd(a,b):
  while b:a,b=b,a%b
  return a
def lcm(a,b):return a*b//gcd(a,b)
l=a[0]
for i in range(1,n):
  l=lcm(l,a[i])
ans=0
l%=mod
for i in range(n):
  ans+=l*pow(a[i],mod-2,mod)
  ans%=mod
print(ans)
### BUGGY CODE ###

class Fenwick:
    def __init__(self, size):
        self.arr = [0]*size
    
    def update(self, i, val):
        while i < len(self.arr): self.arr[i] += val; i |= i+1
    
    def getsum(self, i):
        res = 0
        while i >= 0: res+= self.arr[i]; i = (i&(i+1))-1
        return res

def paramin(F, l, r):
    while l <= r:
        mid = (l+r)//2
        if F(mid): ans, r = mid, mid-1
        else: l = mid+1
    return ans

from itertools import accumulate
def medleq(x):
    M = [(y<=x)*2-1 for y in L]
    MA = list(accumulate(M))
    cnt = sum(y>0 for y in MA)
    F = Fenwick(2*n+3)
    for y in MA:
        c = y+n+1
        cnt+= F.getsum(c-1)
        F.update(c, 1)
    return cnt >= target

n = int(input())
L = list(map(int,input().split()))
tot = n + n*(n-1)//2
target = tot//2 + 1
print(paramin(medleq, min(L), max(L)))

### FIXED CODE ###

class Fenwick:
    def __init__(self, size):
        self.arr = [0]*size
    
    def update(self, i, val):
        while i < len(self.arr): self.arr[i] += val; i |= i+1
    
    def getsum(self, i):
        res = 0
        while i >= 0: res+= self.arr[i]; i = (i&(i+1))-1
        return res

def paramin(F, l, r):
    while l <= r:
        mid = (l+r)//2
        if F(mid): ans, r = mid, mid-1
        else: l = mid+1
    return ans

from itertools import accumulate
def medleq(x):
    M = [(y<=x)*2-1 for y in L]
    MA = list(accumulate(M))
    cnt = sum(y>0 for y in MA)
    F = Fenwick(2*n+3)
    for y in MA:
        c = y+n+1
        cnt+= F.getsum(c-1)
        F.update(c, 1)
    return cnt >= target

n = int(input())
L = list(map(int,input().split()))
tot = n + n*(n-1)//2
target = tot//2 + 1
print(paramin(medleq, min(L), max(L)))
### BUGGY CODE ###

n=int(input())
a=1
b=1
for i in range(n):
    ti,ai=map(int,input().split())
    m=1
    while a>m*ti or b>m*ai:
        m=m+1
#        print(m,a,m*ti,b,m*ai)
#    print(m,a,m*ti,b,m*ai)
    a=m*ti
    b=m*ai
#    print(a,b,m)
print(a+b)    

### FIXED CODE ###

icase=0
if icase==0:
    n=int(input())
    t=[0]*n
    a=[0]*n

    for i in range(n):
        t[i],a[i]=map(int,input().split())
elif icase==1:
    n=5
    t=[3,48,31,231,3]
    a=[10,17,199,23,2]
    ans=6930

ti=t[0]
ai=a[0]
dt=1
for i in range(n-1):
    if ti/t[i+1]>ai/a[i+1]:
        ii=max((ti-dt)//t[i+1]+1,1)
        ti=ii*t[i+1]
        ai=ii*a[i+1]
    else:
        ii=max((ai-dt)//a[i+1]+1,1)
        ti=ii*t[i+1]
        ai=ii*a[i+1]

print(ai+ti)
### BUGGY CODE ###

#!/usr/bin/env python3
n = int(input())

arg = list(map(int, input().split()))
ans = 1

if 0 in arg:
    ans = 0
else:
    for m in arg:
        ans *= m

        if ans > 1000000000000000000:
            ans = -1

print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
n = int(input())

arg = list(map(int, input().split()))
ans = 1

if 0 in arg:
    ans = 0
else:
    for m in arg:
        ans *= m

        if ans > 1000000000000000000:
            ans = -1
            break

print(ans)
### BUGGY CODE ###

b = input()
l = list(map(int, input().split()))
plus = 0
for i in range (len(l)-1):
	if l.count(l[i])>1:
		plus += 1
        
if plus > 0:
  	print('NO')
else:
	print('YES')

### FIXED CODE ###

b = input()
l = list(map(int, input().split()))
ldistinct = set(l)

if len(ldistinct) < len(l):
	print('NO')
else:
	print('YES')
### BUGGY CODE ###

import itertools


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

C = list(itertools.permutations(V, N))
ans = 0
for c in C:
    a = c[0]
    for i in range(1, N):
        a = (a + c[i]) / 2
    ans = max(ans, a)
print(ans)

### FIXED CODE ###

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

C = sorted(V)

ans = 0
a = C[0]
for i in range(1, N):
    a = (a + C[i]) / 2
ans = max(ans, a)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000000)
N, Q = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(N-1):
  a, b = map(lambda x:int(x)-1, input().split())
  graph[a] += [b]
  graph[b] += [a]


cnt = [0] * N
for _ in range(Q):
  p, x = map(int, input().split())
  p -= 1 
  cnt[p] += x

def dfs(u, pre, c):
  for v in graph[u]:
    if v != pre:
      cnt[v] += cnt[u]
      dfs(v, u, cnt[v])

dfs(0, -1, cnt[0])
print(*cnt)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.buffer.readline
def dfs(G,v,p):
    for nv in G[v]:
        if(nv==p):
            continue
        point[nv]+=point[v]
        dfs(G,nv,v)

N,Q=map(int,input().split())
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
point=[0]*N
for i in range(Q):
    p,x=map(int,input().split())
    point[p-1]+=x
dfs(G,0,-1)
print(*point)
### BUGGY CODE ###

import sys
n, k = map(int, sys.stdin.readline().strip('\n').split())
h = list(map(int, sys.stdin.readline().strip('\n').split()))
dp = [float('inf') for _ in range(n)]
dp[0] = 0
for i in range(1, n):
  for j in range(k+1):
    if i-j>=0: dp[i] = min(dp[i], dp[i-j] + abs(h[i-j]-h[i]))
print(dp[n-1])

### FIXED CODE ###

import sys
n, k = map(int, sys.stdin.readline().strip('\n').split())
h = list(map(int, sys.stdin.readline().strip('\n').split()))
dp = [float('inf') for _ in range(n)]
dp[0] = 0
for i in range(1, n):
  for j in range(k+1):
    if i-j>=0: dp[i] = min(dp[i], dp[i-j] + abs(h[i-j]-h[i]))
print(dp[n-1])
### BUGGY CODE ###

#!/usr/bin/env python3

MOD = 1000000007
n, *a = map(int, open(0).read().split())

ans = 0
w = 1
for i in range(61):
    zero = one = 0
    for j in range(n):
        if a[j]&1: one += 1
        else: zero += 1
        a[j] >>= 1;
    ans = (ans + w * zero * one)% MOD
    w = w * 2 % MOD
print(ans)


### FIXED CODE ###

MOD = 1000000007
n, *a = map(int, open(0).read().split())

ans = 0
w = 1
for i in range(61):
    zero = one = 0
    for j in range(n):
        if a[j]&1: one += 1
        else: zero += 1
        a[j] >>= 1;
    ans += w * zero * one
    ans %= MOD
    w = w * 2 % MOD
print(ans)
### BUGGY CODE ###

N = int(input())
lowid= 0
highid = N-1
print(0,flush=True)
lowsex = input()
if lowsex=='Vacant':
    exit()
print(N-1,flush=True)
highsex = input()
if highsex=='Vacant':
    exit()
while highid-lowid>1:
    midid = (lowid+highid)//2
    print(midid,flush=True)
    midsex = input()
    if midsex=='Vacant':
        exit()
    if (midid-lowid)%2==1 and midsex==lowsex:
        highid = midid
        highsex = midsex
    elif (midid-lowid)%2==0 and midsex!=lowsex:
        highid = midid
        highsex = midsex
    else:
        lowid = midid
        lowsex = midsex

### FIXED CODE ###

N = int(input())
lowid= 0
highid = N-1
print(0)
lowsex = input()
if lowsex=='Vacant':
    exit()
print(N-1)
highsex = input()
if highsex=='Vacant':
    exit()
while highid-lowid>1:
    midid = (lowid+highid)//2
    print(midid)
    midsex = input()
    if midsex=='Vacant':
        exit()
    if (midid-lowid)%2==1 and midsex==lowsex:
        highid = midid
        highsex = midsex
    elif (midid-lowid)%2==0 and midsex!=lowsex:
        highid = midid
        highsex = midsex
    else:
        lowid = midid
        lowsex = midsex
### BUGGY CODE ###

from collections import deque
from math import ceil

H, W, K = map(int, input().split())
A = [input() for _ in range(H)]

# 2回目以降の移動において、すべての部屋は開いていると考えてよい
si, sj = next(
    (i, j)
    for i in range(H)
    for j in range(W)
    if A[i][j] == 'S'
)
q = deque()
q.append((si, sj, 0))
T = {(si, sj)}
while q:
    i, j, d = q.popleft()
    if d < K:
        for x, y in (
                (u, v)
                for u, v in ((i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1))
                if 0 <= u < H and 0 <= v < W and
                A[u][v] == '.' and (u, v) not in T
        ):
            q.append((x, y, d + 1))
            T.add((x, y))
ans = 1 + ceil(
    min(
        min(i, j, H - 1 - i, W - 1 - j)
        for i, j in T
    ) / K
)

print(ans)


### FIXED CODE ###

from collections import deque
from math import ceil

H, W, K = map(int, input().split())
A = [input() for _ in range(H)]

# 2回目以降の移動において、すべての部屋は開いていると考えてよい
si, sj = next(
    (i, j)
    for i in range(H)
    for j in range(W)
    if A[i][j] == 'S'
)
q = deque()
q.append((si, sj, 0))
T = {(si, sj)}
while q:
    i, j, d = q.popleft()
    if d < K:
        for x, y in (
                (u, v)
                for u, v in ((i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1))
                if 0 <= u < H and 0 <= v < W and
                A[u][v] == '.' and (u, v) not in T
        ):
            q.append((x, y, d + 1))
            T.add((x, y))
ans = 1 + ceil(
    min(
        min(i, j, H - 1 - i, W - 1 - j)
        for i, j in T
    ) / K
)

print(ans)
### BUGGY CODE ###

from collections import defaultdict

N = int(input())
S = input()
left = S[:N]
right = S[:N-1:-1]

# leftの(blue, red)のパターンを全列挙
br_pattern = defaultdict(int)

for bit in range(1<<N):
    blue = ""
    red = ""
    for isb in range(N):
        if bit & (1<<isb):
            blue = blue + left[isb]
        else:
            red = red + left[isb]
            
    br_pattern[(blue, red)] += 1

# rightの(red, blue)のパターンをひとつずつ調べ、br_patternに一致する数だけansに足す
ans = 0
for bit in range(1<<N):
    red = ""
    blue = ""
    for isr in range(N):
        if bit & (1<<isr):
            red = red + right[isr]
        else:
            blue = blue + right[isr]
            
    ans += br_pattern[(red, blue)]
        
print(ans)

### FIXED CODE ###

from collections import defaultdict

N = int(input())
S = input()
left = S[:N]
right = S[:N-1:-1]

# leftの(blue, red)のパターンを全列挙
br_pattern = defaultdict(int)

for bit in range(1<<N):
    blue = ""
    red = ""
    for isb in range(N):
        if bit & (1<<isb):
            blue = blue + left[isb]
        else:
            red = red + left[isb]
            
    br_pattern[(blue, red)] += 1

# rightの(red, blue)のパターンをひとつずつ調べ、br_patternに一致する数だけansに足す
ans = 0
for bit in range(1<<N):
    red = ""
    blue = ""
    for isr in range(N):
        if bit & (1<<isr):
            red = red + right[isr]
        else:
            blue = blue + right[isr]
            
    ans += br_pattern[(red, blue)]
        
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
q = []

for x in p:
  q.append((x+1)/2)
  
max_reg = 0
for i in range(n - k + 1):
  max_reg = max(max_reg, sum(q[i:i+k]))
  
print(max_reg)

### FIXED CODE ###

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

sum_reg = (sum(p[0:k])+k)/2
max_reg = sum_reg
for i in range(k, n):
  sum_reg = sum_reg + (p[i]-p[i-k])/2
  max_reg = max(max_reg, sum_reg)
  
print(max_reg)
### BUGGY CODE ###

N, X, Y = [int(_) for _ in input().split()]

INF = 10 ** 9
dp = [[INF] * N for _ in range(N)]

for i in range(N - 1):
    dp[i][i + 1] = 1
    dp[i+1][i] = 1

dp[X - 1][Y - 1] = 1
dp[Y - 1][X - 1] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            # k経由でiからjへ
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

cnt = [0] * N
for i in range(N):
    for j in range(i+1, N):
        v = dp[i][j]
        cnt[v]+=1
for i in range(1,N):
    print(cnt[i])


### FIXED CODE ###

N, X, Y = [int(_) for _ in input().split()]

INF = 10 ** 9
dp = [[INF] * N for _ in range(N)]

for i in range(N - 1):
    for j in range(i + 1, N):
        dp[i][j] = j - i
        dp[j][i] = j - i

dp[X - 1][Y - 1] = 1
dp[Y - 1][X - 1] = 1

for k in [X - 1, Y - 1]:
    for i in range(N):
        for j in range(N):
            # k経由でiからjへ
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

cnt = [0] * N
for i in range(N):
    for j in range(i + 1, N):
        v = dp[i][j]
        cnt[v] += 1
for i in range(1, N):
    print(cnt[i])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(220000)

n,q = map(int,input().split())
l =  [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    l[a].append(b)
    l[b].append(a)

value = [0 for _ in range(n)]
for _ in range(q):
    p,q = map(int,input().split())
    value[p-1] += q

bit = [0 for _ in range(n)]
def dfs(k):
    bit[k] = 1
    for i in l[k]:
        if bit[i]==0:
            value[i] += value[k]
            dfs(i)

dfs(0)
print(*value)


### FIXED CODE ###

from collections import deque
n,q = map(int,input().split())
l =  [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    l[a].append(b)
    l[b].append(a)

value = [0 for _ in range(n)]
for _ in range(q):
    p,q = map(int,input().split())
    value[p-1] += q

bit = [0 for _ in range(n)]
"""
def dfs(k):
    bit[k] = 1
    for i in l[k]:
        if bit[i]==0:
            value[i] += value[k]
            dfs(i)
"""
d = deque([0])
while d:
    a = d.popleft()
    bit[a] = 1
    for i in l[a]:
        if bit[i]==0:
            d.append(i)
            value[i] += value[a]
        

print(*value)
### BUGGY CODE ###

N, M = map(int, input().split())
priceList = [int(i) for i in input().split()]

priceList.sort(reverse=True)
if N == 1:
    while M > 0:
        priceList[0] = priceList[0] // 2
        M -= 1
else:
    while M > 0:
        while priceList[0] >= priceList[1] and M > 0:
            priceList[0] = priceList[0] // 2
            M -= 1

        priceList.sort(reverse=True)

sum = 0
for i in range(N):
    sum += priceList[i]

print(sum)

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
priceList = [(-1)*int(i) for i in input().split()]
heapq.heapify(priceList)

while M > 0:
    maxPrice = -heapq.heappop(priceList)
    maxPrice = maxPrice // 2
    M -= 1
    heapq.heappush(priceList, -maxPrice)

sum = 0
for i in range(N):
    sum += priceList[i]

print(-sum)
### BUGGY CODE ###

import sys
import math

lines = sys.stdin.readlines()
N = int(lines[0])
X = []

for i in range(N):
  Si = str(lines[i+1].split('\n')[0])
  X = X + [Si]

X.sort()

z = 1
for i in range(N-1):
  if X[i] != X[i+1]:
    z +=1
print(z)


### FIXED CODE ###

import sys
import math

lines = sys.stdin.readlines()
N = int(lines[0])
X = []

for i in range(N):
  Si = str(lines[i+1].split('\n')[0])
  X.append(Si)

X.sort()

z = 1
for i in range(N-1):
  if X[i] != X[i+1]:
    z +=1
print(z)
### BUGGY CODE ###

n,m = map(int,input().split())
cards = list(map(int,input().split()))
cards.sort()
actions = []
#print()
#print(cards)
for i in range(m):
    l,r  = map(int,input().split())
    actions.append([r,l])
actions.sort(reverse=True)
start = 0
for i in range(m):
    minnum = min(cards)
    if actions[i][0] <= minnum:
        break
    else:
        for j in range(actions[i][1]):
            #print(cards[j])
            if cards[start+j] <= actions[i][0]:
                cards[start+j] = actions[i][0]
            else:
                break
    start += actions[i][1]
    #print(cards)
print(sum(cards))

### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect
n,m = map(int,input().split())
A = list(map(int,input().split()))
A.sort()

minA = A[0]
Query = []
for _ in range(m):
    b,c = map(int,input().split())
    if c > minA:
        Query.append([b,c])
Query = sorted(Query, key=lambda x:(x[1], x[0]), reverse=True)

ans = 0
index = 0
for b,c in Query:
    if index >= n:
        break
    #print("----")
    cnt = 0
    Flag = True
    while Flag:
        #print(A,b,c,index)
        if A[index] < c:
            A[index] = c
            cnt += 1
            index += 1
            if (cnt >= b) or (index >= n):
                Flag = False
        else:
            Flag = False
    '''
    #A.sort()
    if A[0] >= c:
        break
    else:
        index = min(bisect.bisect_left(A,c),b)
        if index > len(A):
            ans += c * len(A)
            break
        else:
            ans += c * index
            A = A[index:]
    print(A)
    '''
print(sum(A))
### BUGGY CODE ###

MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        ans += a[i] ^ a[j]
        ans %= MOD
print(ans)


### FIXED CODE ###


MOD = 10 ** 9 + 7
MAX = 60

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

cnt = [0 for i in range(MAX)]
for i in range(n):
    bit = bin(a[i])[2:].zfill(MAX)
    for j in range(MAX):
        cnt[j] += int(bit[j])

ans = 0
for i in range(MAX):
    ans += cnt[MAX - i - 1] * (n - cnt[MAX - i - 1]) * 2 ** i
    ans %= MOD
print(ans)
### BUGGY CODE ###


def gcd(a,b):
    x = max([a,b])
    y = min([a,b])
    while y:
        x, y = y, x % y
    return x

# x * y = lcm(x, y) // gcd(x, y)より
def lcm(x, y):
    return x * y // gcd(x, y)

def main():
    N = int(input())
    A = tuple(map(int, input().split()))
    MOD = 10**9+7


    tmp = A[0]
    for a in A[1:]:
        tmp = lcm(tmp, a)

    B = [0] * N
    for i in range(N):
        B[i] = tmp // A[i]

    ans = 0
    for b in B:
        ans += b
        ans %= MOD
        

    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from fractions import gcd


def main():
        
    N = int(input())
    A = list(map(int, input().split())) 
    MOD = 10**9 + 7


    l = 1

    for a in A:
        l = l * a // gcd(l, a)


    ans = 0
    for a in A:
        ans += (l // a)
    ans %= MOD

    print(ans)


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

N = int(input())
As = list(map(int, input().split(" ")))

rule = 1000000007
s = 0
for i in range(len(As)):
    s += As[i] * sum(As[i+1:])
    if s >= rule:
        s = s % rule
print(s)

### FIXED CODE ###

N = int(input())
As = list(map(int, input().split(" ")))

rule = 1000000007
s = 0
list_sum = sum(As[1:])
if list_sum >= rule:
    list_sum = list_sum % rule

for i in range(len(As) - 1):
    s += As[i] * list_sum
    if s >= rule:
        s = s % rule
    list_sum -= As[i+1]
    if list_sum < 0:
        list_sum += rule
print(s)
### BUGGY CODE ###

import unittest


class TestFunc(unittest.TestCase):
    def test_1(self):
        self.assertEqual(fun(5,8,[50,30,40,10,20]),2)
        self.assertEqual(fun(3,2,[100,50,200]),1)
        self.assertEqual(fun(10,100,[7,10,4,5,9,3,6,8,2,1]),2)
        self.assertEqual(fun(5,2,[1,2,3,2,4]),1)




def fun(n,t,a):
    aa = []
    b = None
    s = None
    for i in range(n):
        m = -1
        for j in range(i+1,n):
            if a[j]>a[i] and a[j]-a[i]>m:
                m = a[j]-a[i]
        if m>0:
            aa.append(m)

    c = aa[0]
    ans = 1
    for i in range(1,len(aa)):
        if c<aa[i]:
            c = aa[i]
            ans = 1
        elif c==aa[i]:
            ans += 1

    return ans


if __name__=='__main__':
    #unittest.main()                                                                                                                                                              

    n,t = [int(x) for x in raw_input().split(" ")]
    a = [int(x) for x in raw_input().split(" ")]
    print(fun(n,t,a))


### FIXED CODE ###

import unittest

class TestFunc(unittest.TestCase):
    def test_1(self):
        self.assertEqual(fun(5,8,[50,30,40,10,20]),2)
	self.assertEqual(fun(3,2,[100,50,200]),1)
        self.assertEqual(fun(10,100,[7,10,4,5,9,3,6,8,2,1]),2)
        self.assertEqual(fun(5,2,[1,2,3,2,4]),1)

def fun(n,t,a):
    aa = []
    b = None
    s = None
    for i in range(n):
	if b!=None:
            if s==None:
		if b<a[i]:
                    s = a[i]
                else:
                    b = a[i]
            elif s<=a[i]:
                s = a[i]
            elif s>b:
                aa.append(s-b)
		if b>a[i]:
                    b = a[i]
		s = None
	else:
            b = a[i]

    if b!=None and s!= None and s-b>0:
	aa.append(s-b)

    c = aa[0]
    ans = 1
    for i in range(1,len(aa)):
	if c<aa[i]:
            c = aa[i]
            ans = 1
	elif c==aa[i]:
            ans += 1

    return ans


if __name__=='__main__':
    #unittest.main()                                                                                                                                                              

    n,t = [int(x) for x in raw_input().split(" ")]
    a = [int(x) for x in raw_input().split(" ")]
    print(fun(n,t,a))