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

n = int(input())

v = list(map(int,input().split()))

v1 = []

v2 = []

q = 0

for i in v:
    if q == 0:
        v1.append(i)
        q = 1
    else:
        v2.append(i)
        q = 0
        
maxv1 = 0

maxv2 = 0

for i in set(v1):
    a = v1.count(i)
    if a>maxv1:
        maxv1 = a
        
for i in set(v2):
    b = v2.count(i)
    if b>maxv2:
        maxv2 = b
        
if v1 == v2:
    print(n//2)
else:
    print(n-maxv1-maxv2)

### FIXED CODE ###

import collections

n = int(input())

v = list(map(int,input().split()))

v1 = v[::2]

v2 = v[1::2]
        
if len(set(v))==1:
    print(n//2)
else:
    maxv1 = collections.Counter(v1).most_common()

    maxv2 = collections.Counter(v2).most_common()


    if maxv1[0][0] == maxv2[0][0]:    
        ans1 = (len(v1) - maxv1[0][1]) + (len(v2) - maxv2[1][1])
        ans2 = (len(v1) - maxv1[1][1]) + (len(v2) - maxv2[0][1])
        print(min(ans1, ans2))
    else:
        ans = (len(v1) - maxv1[0][1]) + (len(v2) - maxv2[0][1])
        print(ans)
### BUGGY CODE ###

import collections
q=collections.deque()
h,w=map(int,input().split())
arr=[[] for _ in range(h+2)]
for i in range(w+2):
  arr[0].append(True)
for i in range(h):
  arr[i+1].append(True)
  for j in input():
    if j=='#':
      arr[i+1].append(True)
    else:
      arr[i+1].append(False)
  arr[i+1].append(True)
for i in range(w+2):
  arr[h+1].append(True)
dx=[-1,0,1,0]
dy=[0,-1,0,1]
l=0
for i in range(1,h+1):
  for j in range(1,w+1):
    if arr[i][j]:
      q.append([i,j,0])
      l+=1
while 1:
  y,x,cnt=q.popleft()
  l-=1
  for i in range(4):
    if not arr[y+dy[i]][x+dx[i]]:
      q.append([y+dy[i],x+dx[i],cnt+1])
      l+=1
      arr[y+dy[i]][x+dx[i]]=True
  if l==0:
    print(cnt)
    break

### FIXED CODE ###

import collections
q=collections.deque()
h,w=map(int,input().split())
arr=[[] for _ in range(h+2)]
for i in range(w+2):
  arr[0].append('#')
for i in range(h):
  arr[i+1].append('#')
  for j in input():
    arr[i+1].append(j)
  arr[i+1].append('#')
for i in range(w+2):
  arr[h+1].append('#')
dx=[-1,0,1,0]
dy=[0,-1,0,1]
for i in range(1,h+1):
  for j in range(1,w+1):
    if arr[i][j]=='#':
      q.append([i,j,0])
while 1:
  y,x,cnt=q.popleft()
  for i in range(4):
    if arr[y+dy[i]][x+dx[i]]=='.':
      q.append([y+dy[i],x+dx[i],cnt+1])
      arr[y+dy[i]][x+dx[i]]='#'
  if len(q)==0:
    print(cnt)
    break
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=deque()
Q.append((x1-1,y1-1,0))
MAP[x1-1][y1-1]=0

while Q:
    x,y,c=Q.pop()
    if MAP[x][y]<c:
        continue

    for i in range(1,K+1):
        if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
            MAP[x+i][y]=MAP[x][y]+1
            Q.appendleft((x+i,y,MAP[x][y]+1))
        else:
            break

    for i in range(1,K+1):
        if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
            MAP[x-i][y]=MAP[x][y]+1
            Q.appendleft((x-i,y,MAP[x][y]+1))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
            MAP[x][y+i]=MAP[x][y]+1
            Q.appendleft((x,y+i,MAP[x][y]+1))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
            MAP[x][y-i]=MAP[x][y]+1
            Q.appendleft((x,y-i,MAP[x][y]+1))
        else:
            break
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])


### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=deque()
Q.append((x1-1,y1-1))
MAP[x1-1][y1-1]=0

while Q:
    x,y=Q.pop()

    for i in range(1,K+1):
        if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
            if MAP[x+i][y]==1<<30:
                MAP[x+i][y]=MAP[x][y]+1
                Q.appendleft((x+i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
            if MAP[x-i][y]==1<<30:
                MAP[x-i][y]=MAP[x][y]+1
                Q.appendleft((x-i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
            if MAP[x][y+i]==1<<30:
                MAP[x][y+i]=MAP[x][y]+1
                Q.appendleft((x,y+i))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
            if MAP[x][y-i]==1<<30:
                MAP[x][y-i]=MAP[x][y]+1
                Q.appendleft((x,y-i))
        else:
            break
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])
### BUGGY CODE ###

import math
import heapq
def dijkstra(s,c,n):
    d=[10**10]*n
    d[s]=0
    pq=[]
    heapq.heappush(pq,[0,s])
    while len(pq)!=0:
        t,u=heapq.heappop(pq)
        if d[u]<t:
            continue
        for v in xrange(n):
            if u==v:continue
            if d[u]+c[u][v]<d[v]:
                d[v]=d[u]+c[u][v]
                heapq.heappush(pq,[d[v],v])
    return d

def main():
    xs,ys,xt,yt=map(int,raw_input().split())
    n=int(raw_input())
    c=[[xs,ys,0]]+[map(int,raw_input().split()) for _ in xrange(n)]+[[xt,yt,0]]
    dist=[[10**10]*(n+2) for _ in xrange(n+2)]
    for i in xrange(n+2):
        for j in xrange(n+2):
            if i==j:continue
            dist[i][j]=min(dist[i][j], max(math.sqrt(abs(c[i][0]-c[j][0])**2+abs(c[i][1]-c[j][1])**2)-c[i][2]-c[j][2],0))
            dist[j][i]=dist[i][j]
    ans=dijkstra(0,dist,n+2)
    print(ans[n+1])
main()

### FIXED CODE ###

import math
import heapq
def dijkstra(s,m,n):
    visited=[0]*n
    d=[float("inf")]*n
    d[s]=0
    while True:
        mincost=float("inf")
        for i in xrange(n):
            if visited[i]!=2 and d[i]<mincost:
                mincost=d[i]
                u=i
        if mincost==float("inf"):
            break
        visited[u]=2
        for v in xrange(n):
            if visited[v]!=2:
                if d[u]+m[u][v]<d[v]:
                    d[v]=d[u]+m[u][v]
                    visited[v]=1
    return d

def main():
    xs,ys,xt,yt=map(int,raw_input().split())
    n=int(raw_input())
    c=[[xs,ys,0]]+[map(int,raw_input().split()) for _ in xrange(n)]+[[xt,yt,0]]
    dist=[[float("inf")]*(n+2) for _ in xrange(n+2)]
    for i in xrange(n+2):
        for j in xrange(n+2):
            if i==j:continue
            dist[i][j]=min(dist[i][j],dist[j][i],max(math.sqrt(abs(c[i][0]-c[j][0])**2+abs(c[i][1]-c[j][1])**2)-c[i][2]-c[j][2],0))
            dist[j][i]=dist[i][j]
    ans=dijkstra(0,dist,n+2)
    print(ans[n+1])
main()
### BUGGY CODE ###

import itertools
n=int(input())
a=list(map(int,input().split()))
b=0
for v in itertools.combinations(a,2):
  b+=v[0]*v[1]
  if b>=10**9:
    b=b%(10**9+7)
print(b)  


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=sum(a)
c=0
for v in range(n-1):
  b-=a[v]
  c+=a[v]*b
print(c%(10**9+7))
### BUGGY CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]*n
dp[1] = abs(h[1] - h[0])

for i in range(2,n):
    dp[i] = min(dp[j] + abs(h[i] - h[j]) for j in range(max(0,i-k),i))

print(dp[-1])
                  



### FIXED CODE ###

def main():
    n,k = map(int,input().split())
    h = list(map(int,input().split()))
    dp = [0]*n
    dp[1] = abs(h[1] - h[0])
    for i in range(2,n):
        dp[i] = min(abs(h[i] - h[j]) + dp[j] for j in range(max(0,i-k),i))
    print(dp[-1])

main()
### BUGGY CODE ###

import numpy as np
s = list(map(int, input().split()))
l = s[0]

while True:
    tmp = s[0]
    s[0] = s[1]
    s[1] = tmp - s[1]
    s = np.sort(s)[::-1]
    
    if s[0] == s[1]:
        l += s[0]
        break
    else:
        l = l + s[1] * 2

print(l)

### FIXED CODE ###

# %%time
import numpy as np
n, x = list(map(int, input().split()))
s = 0
a = [n-x, x]
s += n
# print(a,s)
while True:
#     if a[0] == a[1]:
#         s += a[0]
#         break
#     else:
    mi = np.min(a)
    ar = np.argmax(a)
    num = a[ar]//mi
    a[ar] -= mi * num
    s += 2 * mi * num
#     print(a, s)
    if np.min(a) == 0:
        s -= mi
        break
            
print(s)
### BUGGY CODE ###

n=int(input())
s=list(input())
rlist=[]
glist=[]
blist=[]
ans=0
if len(s)<=3:
    print(0)
    exit()
for i in range(n):
    if s[i]=="R":
        rlist.append(i)
    elif s[i]=="G":
        glist.append(i)
    else:
        blist.append(i)
if len(rlist)==0 or len(glist)==0 or len(blist)==0:
    print(0)
    exit()
ans+=len(rlist)*len(glist)*len(blist)
for i in glist:
    for j in blist:
        if i>j :
            if 2*i-j in rlist:
                ans-=1
            if 2*j-i in rlist:
                ans-=1
            if (i+j)/2 in rlist:
                ans-=1
        else:
            if 2*i-j in rlist:
                ans-=1
            if 2*j-i in rlist:
                ans-=1
            if (i+j)/2 in rlist:
                ans-=1

print(ans)

### FIXED CODE ###

def binary_search(list,target):

	result = -1
	left = 0
	right = len(list) - 1

	while left <= right:
		center = int((left + right)/2)
		if list[center] == target:
			result = center
			break
		elif list[center] < target:
			left = center + 1
		elif list[center] > target:
			right = center - 1

	if result == -1:
		return result
	else:
		return result


if __name__=="__main__":
    n=int(input())
    s=list(input())
    rlist=[]
    glist=[]
    blist=[]
    ans=0
    if len(s)<=3:
        print(0)
        exit()
    for i in range(n):
        if s[i]=="R":
            rlist.append(i)
        elif s[i]=="G":
            glist.append(i)
        else:
            blist.append(i)
    if len(rlist)==0 or len(glist)==0 or len(blist)==0:
        print(0)
        exit()
    ans+=len(rlist)*len(glist)*len(blist)
    for i in range(n-2):
        for j in range(i+1,n-1):
            k=2*j-i
            if s[i]==s[j]:
                continue
            elif k>len(s)-1:
                continue
            else:
                if s[k]!=s[i] and s[k]!=s[j]:
                    ans-=1

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

import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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


def dfs(r, c, cnt, iswhite=True):
    # if r == H - 1 and c == W - 1:
        # return cnt

    now = '.' if iswhite == True else '#'

    ans = 200

    if MEIJI[r][c] != now:
        if iswhite == True:
            cnt += 1

        iswhite = not (iswhite)

    if r == H-1 and c == W - 1:
        return cnt
    if r < H-1:
        ans = min(dfs(r + 1, c, cnt, iswhite), ans)
    if c < W-1:
        ans = min(dfs(r, c + 1, cnt, iswhite), ans)

    return ans


ans = dfs(0, 0, 0, True)
print(ans)


### FIXED CODE ###

import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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


@lru_cache(maxsize=None)
def dfs(r, c, cnt, iswhite=True):
    # if r == H - 1 and c == W - 1:
        # return cnt

    now = '.' if iswhite == True else '#'

    ans = 200

    if MEIJI[r][c] != now:
        if iswhite == True:
            cnt += 1

        iswhite = not (iswhite)

    if r == H-1 and c == W - 1:
        return cnt
    if r < H-1:
        ans = min(dfs(r + 1, c, cnt, iswhite), ans)
    if c < W-1:
        ans = min(dfs(r, c + 1, cnt, iswhite), ans)

    return ans


ans = dfs(0, 0, 0, True)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 5)
MOD = 10 ** 9 + 7
N, K = map(int, input().split())
V = {i: [] for i in range(1,N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)

def dfs(u, p, c):
    l = len([i for i in V[u] if i != p])
    n = K - 2
    if p == 0:
        n += 1
    if l == 0:
        return c
    for v in V[u]:
        if v == p:
            continue
        c *= dfs(v, u, n)
        n -= 1
        c %= MOD
    return c

print(dfs(1, 0, K))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 5)
MOD = 10 ** 9 + 7
N, K = map(int, input().split())
V = {i: [] for i in range(1,N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)

def dfs(u, p, c):
    l = len([i for i in V[u] if i != p])
    n = K - 2
    if p == 0:
        n += 1
    if l == 0:
        return c
    for v in V[u]:
        if v == p:
            continue
        c *= dfs(v, u, n)
        n -= 1
        c %= MOD
    return c

print(dfs(1, 0, K))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys 
import itertools
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H, W, M = map(int,readline().split())
h_cnt = [0]*(H+1)
w_cnt = [0]*(W+1)
data = [[False]*(W+1) for i in range(H+1)]
 
for i in range(M):
    h,w = map(int,readline().split())
    data[h][w] = True
    h_cnt[h] += 1 
    w_cnt[w] += 1
    
maxh = max(h_cnt)
maxw = max(w_cnt)
maxhInd = []
maxwInd = []
maxhInd = [i for i,a in enumerate(h_cnt) if a == maxh]
maxwInd = [i for i,a in enumerate(w_cnt) if a == maxw]
maxhCnt = len(maxhInd)
maxwCnt = len(maxwInd)

ans = maxh+maxw

if maxhCnt * maxwCnt > M:
    print(ans)
else:
    t = list(itertools.product(maxhInd, maxwInd))
    for h,w in t:
        if data[h][w] == False:
            print(ans)
            sys.exit()
    print(ans-1)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys 
import itertools
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H, W, M = map(int,readline().split())
h_cnt = [0]*(H+1)
w_cnt = [0]*(W+1)
bomb = []
 
for i in range(M):
    h,w = map(int,readline().split())
    bomb.append((h,w))
    h_cnt[h] += 1 
    w_cnt[w] += 1
    
maxh = max(h_cnt)
maxw = max(w_cnt)
maxhCnt = h_cnt.count(maxh)
maxwCnt = w_cnt.count(maxw)

total = maxhCnt*maxwCnt
ans = maxh+maxw
cnt = 0
for h,w in bomb:
    if h_cnt[h] == maxh and w_cnt[w] == maxw:
       cnt += 1

print(ans-1 if cnt == total else ans)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
a = list(map(int,readline().split()))
a.sort()
if a[0] == a[-1]:
  if n > 1:
    print(0)
  else:
    print(1)
  exit()

if a[0] == 1:
  if a[0] == a[1]:
    print(0)
  else:
    print(1)
  exit()
  
def divisorize(fct):
    b, e = fct.pop()
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]

def factorize(n):
    fct = []
    b, e = 2, 0
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
 
 
def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a
    
s = set()
if a[0] < a[1]:
  ans = 1
else:
  ans = 0
s.add(a[0])
for nm,i in enumerate(a[1:]):
  c = set()
  fct = factorize(i)
  for div in divisorize(fct):
      c.add(num(div))
  if c&s == set() and ((nm < n-2 and a[nm+2] != i) or nm == n-2):
    ans += 1
  s.add(i)

print(ans)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
a = list(map(int,readline().split()))
a.sort()
if a[0] == a[-1]:
  if n > 1:
    print(0)
  else:
    print(1)
  exit()

if a[0] == 1:
  if a[0] == a[1]:
    print(0)
  else:
    print(1)
  exit()
  
def divisorize(fct):
    b, e = fct.pop()
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]

def factorize(n):
    fct = []
    b, e = 2, 0
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
 
 
def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a
    
s = set()
if a[0] < a[1]:
  ans = 1
else:
  ans = 0
s.add(a[0])
for nm,i in enumerate(a[1:]):
  c = set()
  fct = factorize(i)
  for div in divisorize(fct):
      c.add(num(div))
  if c&s == set() and ((nm < n-2 and a[nm+2] != i) or nm == n-2):
    ans += 1
  s.add(i)

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

n = int(input())
A = [int(item) for item in input().split()]
B = [int(item) for item in input().split()]
 
dp = [0] * (n+1)
for i, x in enumerate(dp):
    for a, b in zip(A, B):
        if i - a >= 0:
            dp[i] = max(dp[i], dp[i-a] + b - a)
n += dp[n]
dp = [0] * (n+1)
for i, x in enumerate(dp):
    for b, a in zip(B, A):
        if i - b >= 0:
            dp[i] = max(dp[i], dp[i-b] + a - b)
print(n + dp[n])

### FIXED CODE ###

n = int(input())
A = [int(item) for item in input().split()]
B = [int(item) for item in input().split()]
 
dp = [0] * (n+1)
AB = [] 
for a, b in zip(A, B):
    if b > a:
        AB.append((a, b))
for i in range(n+1):
    for a, b in AB:
        if i - a >= 0:
            y = dp[i-a] + b - a
            if y > dp[i]:
                dp[i] = y
n += dp[n]
dp = [0] * (n+1)
BA = []
for b, a in zip(B, A):
    if a > b:
        BA.append((b, a))
for i in range(n+1):
    for b, a in BA:
        if i - b >= 0:
            y = dp[i-b] + a - b
            if y > dp[i]:
                dp[i] = y 
print(n + dp[n])
### BUGGY CODE ###

from math import ceil
from bisect import bisect_right
N, D, A = map(int, input().split())
Monsters = [list(map(int, input().split())) for i in range(N)]
Monsters = sorted([[x, ceil(h / A)] for x, h in Monsters])


class BIT2:
    """ 区間加算BIT(区間加算・区間合計取得) """

    def __init__(self, N):
        self.N = N
        self.data0 = [0] * N
        self.data1 = [0] * N

    def _add(self, data, k, x):
        while k < self.N:
            data[k] += x
            k += k & -k

    def _get(self, data, k):
        s = 0
        while k:
            s += data[k]
            k -= k & -k
        return s

    def add(self, l, r, x):
        """ 区間[l,r)に値xを追加 """

        self._add(self.data0, l, -x*(l-1))
        self._add(self.data0, r, x*(r-1))
        self._add(self.data1, l, x)
        self._add(self.data1, r, -x)

    def query(self, l, r):
        """ 区間[l,r)の和を取得 """

        return self._get(self.data1, r-1) * (r-1) + self._get(self.data0, r-1) \
             - self._get(self.data1, l-1) * (l-1) - self._get(self.data0, l-1)


RUQ = BIT2(2 * N)
for i, (x, h) in enumerate(Monsters, start=1):
    RUQ.add(i, i + 1, h)


i = 0
ans = 0
while i < N:
    cost = RUQ.query(i + 1, i + 2)
    if cost > 0:
        index = bisect_right(Monsters, [Monsters[i][0] + 2 * D, float('inf')])
        RUQ.add(i + 1, index + 1, -cost)
        ans += cost
    i += 1
    #
    # check = []
    # for j in range(1, N + 1):
    #     check.append(str(RUQ.query(j, j + 1)))
    # print(' '.join(check))

print(ans)

### FIXED CODE ###

from math import ceil
from collections import deque
N, D, A = map(int, input().split())
Monsters = sorted([list(map(int, input().split())) for i in range(N)])
Monsters = [[x, ceil(h / A)] for x, h in Monsters]


acc_damage = 0
que = deque([])

ans = 0
for x, h in Monsters:
    # 期限切れの蓄積ダメージを削除
    while que and x > que[0][0]:
        limit, damage = que.popleft()
        acc_damage -= damage

    need = max(0, h - acc_damage)
    ans += need
    acc_damage += need

    if need:
        que.append([x + 2 * D, need])

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

n,m=map(int,input().split())
e=[tuple(map(int,input().split())) for _ in range(m)]
d=[0]+[-float('inf')]*(n-1)
for _ in range(n-1):
    for a,b,c in e:
        d[b-1]=max(d[b-1],d[a-1]+c)
r=d[n-1]
for _ in range(n-1):
    for a,b,c in e:
        d[b-1]=max(d[b-1],d[a-1]+c)
if d[n-1]==r:
    print(r)
else:
    print('inf')

### FIXED CODE ###

n,m=map(int,input().split())
e=[tuple(map(int,input().split())) for _ in range(m)]
d=[0]+[-float('inf')]*(n-1)
for _ in range(n-1):
    for a,b,c in e:
        d[b-1]=max(d[b-1],d[a-1]+c)
r=d[n-1]
for _ in range(n-1):
    for a,b,c in e:
        d[b-1]=max(d[b-1],d[a-1]+c)
if d[n-1]==r:
    print(r)
else:
    print('inf')
### BUGGY CODE ###

n = int(input())

ar = [0 for _ in range(n)]

ar = [int(s) for s in input().split()]

res = 1

for i in range(n):
    res = res*ar[i]

if(res > 10**18):
    print(-1)
else:
    print(res)


### FIXED CODE ###

from collections import deque
n = int(input())
d = deque()

ar = [0 for _ in range(n)]

ar = [int(s) for s in input().split()]

ar.sort()
res = 1
flag = 0

if(ar[0] == 0):
    res = 0
else:
    ar = [i for i in ar if i != 1]
    if(len(ar) < 50):
        for i in ar:
            res = res*i
            if(res > 10**18):
                print(-1)
                flag = 1
                break
    else:
        print(-1)
        flag = 1

if(flag == 0):
    print(res)
### BUGGY CODE ###

n, m = map(int, input().split())
items = list(map(int, input().split()))
for i in range(m):
    max_val_i = items.index(max(items))
    items[max_val_i] /= 2
print(sum(list(map(int, items))))

### FIXED CODE ###

import heapq as hq
n, m = map(int, input().split())
items = [-int(i) for i in input().split()]
hq.heapify(items)
for _ in range(m):
    max_val = hq.heappop(items)
    hq.heappush(items, -(-max_val // 2))
print(-sum(items))
### BUGGY CODE ###

import bisect

N,M=map(int,input().split())
A=list(map(int,input().split()))
BC=[list(map(int,input().split())) for i in range(M)]
BC.sort(key=lambda x: x[1], reverse=True)

for j in range(M):
    A.sort()
    if A[0]>=BC[j][1]:
        break
    else:
        b=BC[j][0]
        c=BC[j][1]
        R=bisect.bisect_left(A,c)
        if R>=b:
            for k in range(b):
                A[k]=c
        else:
            for k in range(R):
                A[k]=c
print(sum(A))

### FIXED CODE ###

import bisect

N,M=map(int,input().split())
A=list(map(int,input().split()))
BC=[list(map(int,input().split())) for i in range(M)]

A.sort()
BC.sort(key=lambda x: x[1],reverse=True) 
ans=0
for j in range(M):
    if A[0]>=BC[j][1]:
        break
    else:
        b=BC[j][0]
        c=BC[j][1]
        R=bisect.bisect_left(A,c)
        n=len(A)
        if R>b:
            if n<=b:
                A=[]
                ans+=n*c
                break
            else:
                del A[0:b]
                ans+=b*c
        else:
            del A[0:R]
            ans+=R*c
    if len(A)==0:
        break        
print(sum(A)+ans)
### BUGGY CODE ###

from decimal import Decimal

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

for i in range(n):
  a[i] = [(-1) * a[i], Decimal(str((-1) * a[i])), (-1) * a[i], Decimal(str((-1) * a[i])), 1]

import heapq
heapq.heapify(a)

for _ in range(k):
  i = heapq.heappop(a)
  i[4] += 1
  i[0] = i[2] // i[4]
  i[1] = i[3] / i[4]
  heapq.heappush(a, i)

print((-1) * heapq.heappop(a)[0])


### FIXED CODE ###

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

# binary search
left = 1
right = 10 ** 9

while left < right:
    center = (left + right) // 2

    total = 0
    for i in a:
        if i % center == 0:
            i -= 1
        total += i//center
    
    if total > k:
        left = center + 1
    else:
        right = center

print(left)