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

from fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7

def main():
    n, c = map(int, input().split())
    stk = [list(map(int, input().split())) for i in range(n)]
    stk = sorted(stk,key=lambda x:x[0])

    ans = 1
    l = []
    heapify(l)
    heappush(l,[stk[0][1],stk[0][2]])
    for i in range(1, n):
        ll = []
        size = len(l)
        for j in range(size):
            v = heappop(l)
            if stk[i][2] == v[1]:
                if stk[i][0] < v[0]:
                    ll.append(v)
            else:
                if stk[i][0] - 0.5 < v[0] :
                    ll.append(v)
        for j in range(len(ll)):
            heappush(l, ll[j])
        
        heappush(l, stk[i][1:])
        ans = max(ans , len(l))
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7

input = sys.stdin.readline
def main():
    n, c = map(int, input().split())
    stk = [tuple(map(int, input().split())) for i in range(n)]
    stk = sorted(stk, key=lambda x: x[0])

    ans = 1
    l = []
    # heapify(l)
    # heappush(l, (stk[0][1], stk[0][2]))
    l = [(stk[0][1], stk[0][2])]
    for i in range(1, n):
        ll = []
        #heapify(ll)
        for j in range(len(l)):
            # v = heappop(l)
            v = l[j]
            if stk[i][2] == v[1]:
                if stk[i][0] < v[0]:
                    # heappush(ll, v)
                    ll.append(v)
            else:
                if stk[i][0] - 0.5 < v[0]:
                    # heappush(ll, v)
                    ll.append(v)
        # heappush(ll, stk[i][1:])
        ll.append(stk[i][1:])
        l = ll
        ans = max(ans, len(l))
    print(ans)


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

# -*- coding: utf-8 -*-

N = int(input().strip())
A_list = list(map(int, input().rstrip().split()))
#-----

# A_index[i] = ( value of A , index of A)
A_index = []

for i in range(len(A_list)):
    A_index.append( (A_list[i], i) )

A_index.sort(reverse=True)


# dp[left][right] = score
dp = [ [0]*(N+1) for _ in range(N+1) ]


for L in range(N):
    for R in range(N-L):
        i = L + R
        append_L = dp[L][R] + A_index[i][0] * abs(L - A_index[i][1])
        append_R = dp[L][R] + A_index[i][0] * abs((N-1-R) - A_index[i][1])
        
        dp[L+1][R] = max(dp[L+1][R], append_L)
        dp[L][R+1] = max(dp[L][R+1], append_R)


ans = max( [ dp[i][N-i] for i in range(N+1)] )
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

N = int(input().strip())
A_list = list(map(int, input().rstrip().split()))
#-----

# A_index[i] = ( value of A , index of A)
A_index = [ (A_list[i], i) for i in range(len(A_list)) ]
A_index.sort(reverse=True)


# dp[left][right] = score
dp = [ [0]*(N+1) for _ in range(N+1) ]


for L in range(N):
    for R in range(N-L):
        i = L + R
        append_L = dp[L][R] + A_index[i][0] * abs(L - A_index[i][1])
        append_R = dp[L][R] + A_index[i][0] * abs((N-1-R) - A_index[i][1])
        
        dp[L+1][R] = max(dp[L+1][R], append_L)
        dp[L][R+1] = max(dp[L][R+1], append_R)


ans = max( [ dp[i][N-i] for i in range(N+1)] )
print(ans)
### BUGGY CODE ###

MOD = 10 ** 9 + 7
s = input()
n = len(s)
dp = [[0 for j in range(13)] for i in range(n + 1)]
dp[0][0] = 1
for i, si in enumerate(s):
    if si == '?':
        k_list = range(10)
    else:
        k_list = [int(si)]
    for j in range(13):
        xij = dp[i][j]
        for k in k_list:
            dp[i + 1][(j * 10 + k) % 13] += xij
    for j in range(13):
        dp[i + 1][j] %= MOD
print(dp[-1][5])


### FIXED CODE ###

MOD = 10 ** 9 + 7
s = input()
n = len(s)
dp = [[0 for j in range(13)] for i in range(n + 1)]
dp[0][0] = 1
dpi = dp[0]
for i, si in enumerate(s):
    dpi1 = dp[i + 1]
    if si == '?':
        k_list = range(10)
    else:
        k_list = [int(si)]
    for j in range(13):
        xij = dpi[j]
        for k in k_list:
            dpi1[(j * 10 + k) % 13] += xij
    for j in range(13):
        dpi1[j] %= MOD
    dpi = dpi1
print(dp[-1][5])
### BUGGY CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
ans = 0
for i in range(n-k+1):
    x = 0
    for j in p[i:i+k]:
        z = 0
        for a in range(1,j+1):
            z+=a*(1/j)
        x+=z
    ans = max(x,ans)
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
p = [0]
a = list(map(int,input().split()))
a = [(1+i)/2 for i in a]
p.extend(a)
s = [0]*(n+1)
for i in range(n):
    s[i+1]=s[i]+p[i+1]
ans = 0
for i in range(n-k+1):
    ans = max(ans,s[i+k]-s[i])
print(ans)
### BUGGY CODE ###

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

m = 0
s = sorted(a)

d = [0]*(s[-1]+3)

for i in range(0,s[-1]+1):
    d[i+1] += s.count(i)
    d[i] += s.count(i)
    d[i+2] += s.count(i)

print(max(d))


### FIXED CODE ###

cnt=[0]*100002
input()
for x in map(int,input().split()):
    cnt[x]+=1
    cnt[x+1]+=1
    cnt[x+2]+=1
print(max(cnt))
### BUGGY CODE ###

n = int(input())

ans = 0
list = []

for _ in range(n):
    a = input()
    if a not in list:
        list.append(a)
        ans +=1

print(ans)

### FIXED CODE ###

n = int(input())

import sys
S = set(sys.stdin.readlines())



print(len(S))
### BUGGY CODE ###

N = int(input())
A = sorted(map(int, input().split()), reverse=False)
m = max(A)+1
dp = [0] * m
for i in range(N):
    if dp[A[i]] == 0:
        dp[A[i]] = 1
        t = A[i] * 2
        while t < m:
            dp[t] = 2
            t += A[i]
ans = 0
for a in A:
    if A.count(a) == 1 and dp[a] == 1:
        ans += 1
print(ans)



### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
p = [True] * (10 ** 6 + 1)
s = list(set(a))
for x in s:
    t = x * 2
    while t <= 10 ** 6:
        p[t] = False
        t += x
ans = 0
for x in a:
    if c[x] == 1 and p[x] == True:
        ans += 1
print(ans)
### BUGGY CODE ###

n,w = (int(i) for i in input().split())
allItems = [[int(i) for i in input().split()] for j in range(n)]
##weight,value
allItems.sort(key = lambda x:x[0])
allItems.sort(key = lambda x:-x[1])
##print(allItems)
##print()
def getMaxSum(items,emptyWt):
    if emptyWt==0:
        return 0
    if emptyWt==1:
        for i in items:
            if i[0]==1:
                return i[1]
        return 0
    prevWt = {}
    maxRes = -1
    for i in range(len(items)):
        wt,val = items[i]
        if (wt in prevWt) or wt>emptyWt:
            continue
        prevWt[wt]=0
        res = val+getMaxSum(items[:i]+items[i+1:],emptyWt-wt)
        if res>maxRes:
            maxRes = res
    return maxRes
        
prevWt = {}
maxRes = -1
for i in range(n):
    wt,val = allItems[i]
    if wt in prevWt:
        continue
    prevWt[wt]=0
    res = val+getMaxSum(allItems[:i]+allItems[i+1:],w-wt)
    if res>maxRes:
        maxRes = res
print(maxRes)


### FIXED CODE ###

import numpy as np

n,W = (int(i) for i in input().split())
weights = []
values = []
for j in range(n):
    wt, val = [int(i) for i in input().split()]
    weights.append(wt)
    values.append(val)

dp  = np.zeros(W+1)

for i in range(1,n+1):
    w = weights[i-1]
    v = values[i-1]
    dp[w:] = np.maximum(dp[w:],v+dp[:-w])

print(int(dp[-1]))
### BUGGY CODE ###

n = int(input())
ans = 1

for i in range(1, n+1):
  ans *= i
  
print(ans % 1000000007)


### FIXED CODE ###

n = int(input())
ans = 1
 
for i in range(1, n+1):
  ans = (ans * i) % 1000000007
  
print(ans)
### BUGGY CODE ###

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

j = n
k = n
t = n * a



dp = [[[0 for t in range(t + 1)] for k in range(k + 1)] for j in range(j + 1)]

dp[1][0][0] = 1
dp[0][0][0] = 1

# for d in dp:
#     print(d)
# print(dp[1][1][15])


for ki in range(0, k + 1):
    for ji in range(0, j + 1):
        for ti in range(0, t + 1):
            # print('now', ji, ki, ti)
            if ji == 0 and ki == 0 and ti == 0:
                # print('branch 1')
                dp[ji][ki][ti] = 1
            elif ji >= 1 and ti < xlist[ji - 1]:
                dp[ji][ki][ti] = dp[ji - 1][ki][ti]
                # print('branch 2')
            elif ji >= 1 and ki >= 1 and ti >= xlist[ji - 1]:
                # print('branch 3', ji - 1)
                dp[ji][ki][ti] = dp[ji - 1][ki][ti] + dp[ji - 1][ki - 1][ti - xlist[ji - 1]]
            else:
                # print('branch 4')
                dp[ji][ki][ti] = 0
            # print(dp[ji][ki][ti])

count = 0
for i in range(1, k + 1):
    count += dp[j][i][i*a]

print(count)

### FIXED CODE ###

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

j = n
k = n
t = n * a
maxv = max(a, max(xlist))


dp = [[[0 for t in range(n*maxv + 1)] for k in range(k + 1)] for j in range(j + 1)]

dp[1][0][0] = 1
dp[0][0][0] = 1

# for d in dp:
#     print(d)
# print(dp[1][1][15])

for ji in range(0, j + 1):
    for ki in range(0, ji + 1):
        for ti in range(0, ki * maxv + 1):
            # print('now', ji, ki, ti)
            if ji == 0 and ki == 0 and ti == 0:
                # print('branch 1')
                dp[ji][ki][ti] = 1
            elif ji >= 1 and ti < xlist[ji - 1]:
                dp[ji][ki][ti] = dp[ji - 1][ki][ti]
                # print('branch 2')
            elif ji >= 1 and ki >= 1 and ti >= xlist[ji - 1]:
                # print('branch 3', ji - 1)
                dp[ji][ki][ti] = dp[ji - 1][ki][ti] + dp[ji - 1][ki - 1][ti - xlist[ji - 1]]
            # print(dp[ji][ki][ti])

count = 0
for i in range(1, k + 1):
    count += dp[j][i][i*a]

print(count)
### BUGGY CODE ###

n,k,l=map(int,input().split())
el=[set() for _ in range(n+1)]
et=[set() for _ in range(n+1)]
ela=[set() for _ in range(n+1)]
eta=[set() for _ in range(n+1)]
eml=[0]*(n+1)
emt=[0]*(n+1)
ans=[0]*(n+1)
for _ in range(k):
  p,q=map(int,input().split())
  el[p].add(q)
  el[q].add(p)
j=0
for i in range(n+1):
  if eml[i]:continue
  eml[i]=j
  ela[j].add(i)
  q=[i]
  while q:
    now=q.pop()
    eml[now]=j
    for to in el[now]:
      if eml[to]:continue
      ela[j].add(to)
      q+=[to]
  j+=1
for _ in range(l):
  p,q=map(int,input().split())
  et[p].add(q)
  et[q].add(p)
j=0
for i in range(n+1):
  if emt[i]:continue
  emt[i]=j
  eta[j].add(i)
  q=[i]
  while q:
    now=q.pop()
    emt[now]=j
    for to in et[now]:
      if emt[to]:continue
      eta[j].add(to)
      q+=[to]
  j+=1
for i in range(n+1):
  ans[i]=len(eta[emt[i]]&ela[eml[i]])
print(*ans[1:])

### FIXED CODE ###

from collections import Counter
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)
  def find(self, x):
    if(self.root[x] < 0):
      return x
    else:
      self.root[x] = self.find(self.root[x])
      return self.root[x]
  def unite(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if(x == y):
      return 
    elif(self.rnk[x] > self.rnk[y]):
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if(self.rnk[x] == self.rnk[y]):
        self.rnk[y] += 1
  def same(self, x, y):
    return self.find(x) == self.find(y)
n,k,l=map(int,input().split())
e=[[i]for i in range(n+1)]
ur=UnionFind(n)
ut=UnionFind(n)
for i in range(k):
  a,b=map(int,input().split())
  ur.unite(a,b)
for _ in range(l):
  a,b=map(int,input().split())
  ut.unite(a,b)
pair=[(ur.find(i),ut.find(i)) for i in range(1,n+1)]
c=Counter(pair)
ans=[c[i] for i in pair]
print(*ans)
### BUGGY CODE ###

l = list(input())
amari = [0]*len(l)
mod = 2019
count = [0]*2020
import math
for i in range(len(l)):
    n = int("".join(l[i:])) % mod
    count[n] += 1
ans = 0
for i in range(1,2020):
    if count[i] == 0 or count[i] == 1:
        continue
    ans += count[i] * (count[i]-1)//2
ans += count[0]
print(ans)

### FIXED CODE ###

S = input()
N = len(S)
P = 2019
num = [0] * P
num[0] = 1
now, ans = 0, 0
_10 = 1
for i in range(N-1, -1, -1):
    now = (now + int(S[i]) * _10) % P
    _10 *= 10
    _10 %= P
    ans += num[now]
    num[now] += 1
print(ans)
### BUGGY CODE ###

import heapq


class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        route_count = [0 for _ in range(num_of_city)]
        route_count[self.start_point] = 1
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
                if dist[dest] == dist[src] + cost:
                    route_count[dest] += route_count[src]

        if self.goal_point is not None:
            return self._get_path(self.goal_point, prev)
        else:
            return dist, route_count

    def _get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))


H, W = map(int, input().split())
graph = [dict() for _ in range(H * W)]
s_list = []
for i in range(H):
    s = list(input())
    s_list.append(s)

for i in range(H):
    for j in range(W):
        if s_list[i][j] == "#":
            continue
        if i + 1 < H and s_list[i + 1][j] == ".":
            graph[i * W + j][(i + 1) * W + j] = 1

        if j + 1 < W and s_list[i][j + 1] == ".":
            graph[i * W + j][i * W + j + 1] = 1

dijkstra = Dijkstra(graph, 0)
_, dijkstra_result = dijkstra.execute()

print(dijkstra_result[-1] % (10**9 + 7))


### FIXED CODE ###

H, W = map(int, input().split())
s_list = []
for i in range(H):
    s = list(input())
    s_list.append(s)

dp = [[0 for _ in range(W)] for _ in range(H)]
dp[0][0] = 1
mod = 10 ** 9 + 7
for i in range(H):
    for j in range(W):
        if s_list[i][j] == "#":
            continue
        if i + 1 < H and s_list[i + 1][j] == ".":
            dp[i + 1][j] += dp[i][j] % mod
        if j + 1 < W and s_list[i][j + 1] == ".":
            dp[i][j + 1] += dp[i][j] % mod
print(dp[H - 1][W - 1] % mod)
### BUGGY CODE ###

from collections import Counter

n = int(input())
a = list(map(int, input().split()))
q = int(input())
l = [list(map(int, input().split())) for _ in range(q)]

for i in range(q):
    (b, c) = l[i] 
    dic = Counter(a)
    for i in range(dic[b]):
        a.remove(b)
        a.append(c)
    print(sum(a))

### FIXED CODE ###

from collections import Counter

n = int(input())
a = list(map(int, input().split()))
q = int(input())
l = [list(map(int, input().split())) for _ in range(q)]
dic = Counter(a)
S = sum(a)
for i in range(q):
    (b, c) = l[i] 
    num = dic[b]
    S -= b*num
    dic[b] = 0
    if dic[c] == 0:
        dic[c] = num
    else:
        dic[c] += num
    S += c*num
    print(S)
### BUGGY CODE ###

import bisect

a, b, q = map(int, input().split())

s = [- 10 ** 19]
for i in range(a):
    s.append(int(input()))
s.append(10 ** 19)

t = [- 10 ** 19]
for i in range(b):
    t.append(int(input()))
t.append(10 ** 19)

for i in range(q):
    x = int(input())
    ps = bisect.bisect_right(s, x)
    pt = bisect.bisect_right(t, x)
    ret = 10 ** 19
    for loc1 in (s[ps], s[ps-1]):
        for loc2 in (t[pt], t[pt-1]):
            val = min(abs(x-loc1) + abs(loc1-loc2),
                      abs(x-loc2) + abs(loc1-loc2))
            ret = min(ret, val)
    print(ret)


### FIXED CODE ###

import bisect

a, b, q = map(int, input().split())

s = [- 10 ** 19]
for i in range(a):
    s.append(int(input()))
s.append(10 ** 19)

t = [- 10 ** 19]
for i in range(b):
    t.append(int(input()))
t.append(10 ** 19)

for i in range(q):
    x = int(input())
    ps = bisect.bisect_right(s, x)
    pt = bisect.bisect_right(t, x)
    ret = 10 ** 19
    for loc1 in (s[ps], s[ps-1]):
        for loc2 in (t[pt], t[pt-1]):
            val = min(abs(x-loc1) + abs(loc1-loc2),
                      abs(x-loc2) + abs(loc1-loc2))
            ret = min(ret, val)
    print(ret)
### BUGGY CODE ###

N, M = map(int, input().split())  # N枚のカード, 操作内容がMセット
A = list(map(int, input().split()))


for i in range(M):
    B, C = map(int, input().split())
    A.extend([C]*B)

A.sort(reverse=True)
print(sum(A[:N]))


### FIXED CODE ###

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

# 二次元配列を作る
BC = []
for i in range(M):
    b, c = list(map(int, input().split()))
    BC.append([b, c])

BC = sorted(BC, reverse=True, key=lambda x: x[1])  # Cの値で降順にソートされる

cnt = 0
com = []

for b, c in BC:
    cnt += b
    if cnt > N:  # 操作を加える回数がNを超えることはない
        add = N-cnt+b  # comの要素数の調整
        com.extend([c]*add)
        break
    else:
        com.extend([c]*b)

A.extend(com)

A.sort(reverse=True)
print(sum(A[:N]))
### BUGGY CODE ###

s = input()

n = len(s) + 1
ans = 0
# for i in range(n - 1):
i = 0
while i < n - 1:
    uCount = 0 # '<'
    dCount = 0 # '>'
    while s[i] == '<' and i < n - 1:
        uCount += 1
        if i == n - 2:
            break
        i += 1
    while s[i] == '>' and i < n - 1:
        dCount += 1
        if i == n - 2:
            i += 1
            break
        i += 1
    if uCount > dCount:
        ans += sum(range(0, uCount + 1))
        ans += sum(range(0, dCount))
    elif uCount <= dCount:
        ans += sum(range(0, dCount + 1))
        ans += sum(range(0, uCount))
    # if i == n - 2 and s[i] == '<':
    #     ans += 1
    #     i += 1
    # elif i == n - 2 and s[i] == '>':
    #     i += 1
print(ans)


### FIXED CODE ###

s = input()

n = len(s) + 1
a = [0] * n
for i in range(n - 1):
    if s[i] == '<':
        a[i + 1] = a[i] + 1

for i in range(n - 2, - 1, -1):
    if s[i] == '>':
        if a[i] <= a[i + 1] + 1:
            a[i] = a[i + 1] + 1

print(sum(a))
### BUGGY CODE ###

N,K = map(int, input().split())
H = list(map(int, input().split()))
 
H.sort(reverse=True)
 
K = min(K, len(H))
for k in range(K):
    H.pop(0)
 
print(sum(H))

### FIXED CODE ###

N,K = map(int, input().split())
H = list(map(int, input().split()))

H.sort(reverse=True)

K = min(K, len(H))
HH = H[K:]

print(sum(HH))
### BUGGY CODE ###

H,W,D=map(int,input().split())
dic=dict()
for i in range(H):
    A = list(map(int,input().split()))
    for j in range(W):
        dic[A[j]]=(i,j)

Q=int(input())

for _ in range(Q):
    ans=0
    L,R=map(int,input().split())
    i,j=dic[L]
    for k in range((R-L)//D):
        x,y=dic[L+D*(k+1)]
        ans+=abs(x-i)+abs(y-j)
        i,j=(x,y)
    print(ans)


### FIXED CODE ###

H,W,D=map(int,input().split())
dic=dict()
for i in range(H):
    A = list(map(int,input().split()))
    for j in range(W):
        dic[A[j]]=(i,j)

Q=int(input())

d=[0 for i in range(H*W+1)]

for i in range(D+1,H*W+1):
    p,q = dic[i-D]
    x,y = dic[i]
    d[i]=d[i-D]+abs(p-x)+abs(q-y)


for _ in range(Q):
    ans=0
    L,R=map(int,input().split())
    print(d[R]-d[L])
### BUGGY CODE ###

def bfs(graph, start, weight, ):
	queue = [start]
	while queue:
		label = queue.pop(0)
		cnt[label-1] += weight
		queue += graph.get(label,[])

n, q = list(map(int, input().split()))
a = [list(map(int, input().split())) for i in range(n-1)]
b = [list(map(int, input().split())) for i in range(q)]

cnt = [0 for i in range(n)]
dic = {}
for i in range(n-1):
	if a[i][0] not in set(dic.keys()):
		dic[a[i][0]] = [a[i][1]]
	else:
		dic[a[i][0]].append(a[i][1])

for i in range(q):
	bfs(dic, b[i][0], b[i][1])
print(*cnt)

### FIXED CODE ###

N, Q = map(int, input().split())
edges = [[] for _ in range(N)]
count = [0]*N

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

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

not_yet = [1]*N
not_yet[0] = 0
stack = [0]

while stack:
    parent = stack.pop()
    # print(parent)
    
    for child in edges[parent]:
        if not_yet[child]:
            count[child] += count[parent]
            not_yet[child] = 0
            stack.append(child)

print(*count)
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))

ans = 0
P_sum = 0

for i in range(N - K + 1):
  for j in range(K):
    P_sum += P[i + j] + 1
  #print(ans, P_sum)
  ans = max(ans, P_sum)
  P_sum = 0

print(ans / 2)

### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))

ans = 0
P_sum = 0

for i in range(N):
  P[i] = (P[i] + 1) / 2

for j in range(K):
  P_sum += P[j]

ans = P_sum
for t in range(K, N):
  P_sum -= P[t - K]
  P_sum += P[t]
  ans = max(ans, P_sum)

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

# coding: utf-8
# Your code here!
import numpy as np

N,A,B=map(int,input().split())
l=[]

for _ in range(N):
    l.append(int(input()))


a=np.array(l)
count=0
while np.amax(a)>0:
    a=a-B
    a[np.argmax(a)]=a[np.argmax(a)]-A+B
    count+=1
   
print(count)


### FIXED CODE ###

N,A,B=map(int,input().split())

H=[]
for _ in range(N):
    H.append(int(input()))

ok=10**9+1
ng=0

while ok-ng>1:
    mid=(ok+ng)//2
    dmg=B*mid
    tgt=0
    for item in H:
        tgt+=-(-max(item-dmg,0)//(A-B))
    if tgt<=mid:
        ok=mid
    else:
        ng=mid

print(ok)
### BUGGY CODE ###

from collections import*
INF=10**18
h,w=map(int,input().split())
sh,sw=map(int,input().split())
gh,gw=map(int,input().split())
s=[input() for _ in range(h)]
q=deque([(sh-1,sw-1)])
d=[[INF]*w for _ in range(h)]
d[sh-1][sw-1]=0
dx=[1,0,-1,0]
dy=[0,-1,0,1]
wx=[-2,-1,0,1,2]
wy=[-2,-1,0,1,2]
while q:
  x,y=q.popleft()
  if (x,y)==(gh-1,gw-1):
    print(d[gh-1][gw-1])
    break
  for i in range(4):
    nx=x+dx[i]
    ny=y+dy[i]
    if not(0<=nx<h and 0<=ny<w):continue
    if s[nx][ny]=='.' and d[nx][ny]>d[x][y]:
      d[nx][ny]=d[x][y]
      q.append((nx,ny))
  for i in wx:
    nx=x+i
    if not(0<=nx<h):continue
    for j in wy:
      ny=y+j
      if not(0<=ny<w):continue
      if s[nx][ny]=='.' and d[nx][ny]>d[x][y]:
        d[nx][ny]=d[x][y]+1
        q.append((nx,ny))
else:print(-1)

### FIXED CODE ###

from collections import*
INF=10**18
h,w=map(int,input().split())
sh,sw=map(int,input().split())
gh,gw=map(int,input().split())
s=[input() for _ in range(h)]
q=deque([(sh-1,sw-1,0)])
d=[[INF]*w for _ in range(h)]
dx=[1,0,-1,0]
dy=[0,-1,0,1]
wx=[-2,-1,0,1,2]
wy=[-2,-1,0,1,2]
while q:
  x,y,c=q.popleft()
  if d[x][y]!=INF:continue
  d[x][y]=c
  for i,j in zip(dx,dy):
    nx=x+i
    ny=y+j
    if not(0<=nx<h and 0<=ny<w):continue
    if s[nx][ny]=='.' and d[nx][ny]==INF:
      q.appendleft((nx,ny,c))
  for i in wx:
    nx=x+i
    if not(0<=nx<h):continue
    for j in wy:
      ny=y+j
      if not(0<=ny<w):continue
      if s[nx][ny]=='.' and d[nx][ny]==INF:
        q.append((nx,ny,c+1))
print(d[gh-1][gw-1]if d[gh-1][gw-1]!=INF else -1)
### BUGGY CODE ###

from sys import exit
N = int(input())
A = list(map(int,input().split()))
ans = 1
for i in A:
    ans *= i
if ans > 10 ** 18:
    print(-1)
else: print(ans)


### FIXED CODE ###

from sys import exit
N = int(input())
A = list(map(int,input().split()))
ans = 1
if 0 in A: print(0)
else:
    for i in A:
        ans *= i
        if ans > 10 ** 18:
            print(-1)
            exit()
    print(ans)
### BUGGY CODE ###

N = int(input())
P = [int(x) for x in input().split()]
count = 0
for i in range(len(P)):
  m = P[i]
  subm = min(P[:i+1])
  if m == subm:
    count += 1
print(count)

### FIXED CODE ###

N = int(input())
P = [int(x) for x in input().split()]
count = 0
minut = 3*10**5
for i in range(len(P)):
  m = P[i]
  if m < minut:
    minut = m
  if m == minut:
    count += 1
print(count)