Harryxun/stf_run huggingface dataset:
import bisect
n=int(input())
h=[]
for i in range(n):
  a=int(input())
  if len(h)==0:
    h.append(-1*a)
  elif (-1)*a>=h[-1]:
    h.append(-1*a)
  else:
    index=bisect.bisect_right(h,-1*a)
    h[index]=-1*a
  print(h)
print(len(h))

### FIXED CODE ###

import bisect
n=int(input())
h=[]
for i in range(n):
  a=int(input())
  if len(h)==0:
    h.append(-1*a)
  elif (-1)*a>=h[-1]:
    h.append(-1*a)
  else:
    index=bisect.bisect_right(h,-1*a)
    h[index]=-1*a
print(len(h))
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, K = mi()
A = li()
flag = [0]*N
l = []
i = 1
ind = 0
while True:
    #print(ind, flag)
    flag[ind] = i
    l.append(ind+1)
    if not flag[A[ind]-1]:
        ind = A[ind]-1
    else:
        ind = A[ind]-1
        break
    i += 1

if K < flag[ind] -1:
    print(l[K])
    exit()

if ind != 0:
    K -= flag[ind] -1
    i -= flag[ind] -1
    print(l[K%i+i-1])
else:
    print(l[K%i])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, K = mi()
A = li()
flag = [0]*N
l = []
i = 1
ind = 0
while True:
    flag[ind] = i
    l.append(ind+1)
    if not flag[A[ind]-1]:
        ind = A[ind]-1
    else:
        ind = A[ind]-1
        break
    i += 1

if K <= flag[ind] - 1:
    print(l[K])
    exit()

if ind != 0:
    K -= flag[ind] -1
    i -= flag[ind] -1
    l = l[flag[ind] -1:]
print(l[K%i])
# union-find
# https://note.nkmk.me/python-union-find/

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        # 各要素の親要素を格納する

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            return self.find(self.parents[x])
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return
    
    def size(self, x):
        x = self.find(x)    
        return self.parents[x]*(-1)

def main():
    n, m = map(int, input().split())
    friend = UnionFind(n)

    for _ in range(m):
        a, b = map(int, input().split())
        friend.union(a-1, b-1)
    
    ans = 0
    for i in range(n):
        ans = max(ans, friend.size(i))
    print(ans)

if  __name__ == "__main__":
     main()


### FIXED CODE ###

d, t, s = map(int, input().split())
if s*t >= d:
    print('Yes')
else:
    print('No')
def seek_dup(s):
    t_list = [t for (t, d) in s]
    #d_list = [d for (t, d) in s]

    for t, d in reversed(s):
        if t_list.count(t) > 1:
            return (t, d)
        else:
            continue
        
    return None

N, K = map(int, input().split())
menu = []

for i in range(N):
    t, d = map(int, input().split())
    menu.append((t, d))

sorted(menu, key = lambda x:x[1], reverse=True)
ans = sum([d for (t, d) in menu[:K]]) + len(set([t for (t, d) in menu[:K]]))**2

selected_menu = menu[:K]
#t_list = [t for (t, d) in selected_menu]
#d_list = [d for (t, d) in selected_menu]
p = ans
for m in menu[K:]:
    t_list = [t for (t, d) in selected_menu]
    d_list = [d for (t, d) in selected_menu]
    
    if m[0] not in t_list:
        d = seek_dup(selected_menu)
        if d == None:
            continue
        
        #selected_menu.remove(d)
        #selected_menu.append(m)
    
    p += (m[1] - d[1]) + 2 * len(set(t_list)) + 1 
    #print(ans, p)
    ans = max(ans, p)

print(ans)    
    

### FIXED CODE ###

N, K = map(int, input().split())
menu_ = []

for i in range(N):
    t, d = map(int, input().split())
    menu_.append((t, d))

menu = sorted(menu_, key = lambda x:x[1], reverse=True)
neta = set()
duplicates = []

for m in menu[:K]:
    if m[0] in neta:
        duplicates.append(m[1])
    else:
        neta.add(m[0])

p = sum([d for (t, d) in menu[:K]]) + len(neta)**2
ans = p

for m in menu[K:]:
    if m[0] not in neta and duplicates:
        neta.add(m[0])
        duplicate = duplicates.pop()
        
        p += (m[1] - duplicate) + 2 * len(neta) - 1 
        #print(ans, p)
        ans = max(ans, p)

print(ans)
n, m = input().split()
a = list(map(int, input().split()))
print(max(n-sum(a),-1))

### FIXED CODE ###

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

if int(n)-sum(a) < 0:
    print("-1")
else:
    print(int(n)-sum(a))
N = int(input())
L = map(int, input().split())
if max(L) * 2 < Sum(L):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
if max(L) * 2 < sum(L):
  print("Yes")
else:
  print("No")
n, x = map(int,input().split())

def rec(lv,ls):
    if lv == 0:
        return [1]
    else:
        ret = rec(lv-1,ls)
        for i in range(0,len(ret) -1):
            if ret[i]>0 and ret[i+1]>0:
                ret[i+1] += ret[i]
                ret[i] = 0  #deleted tag

        while 0 != ret.count(0):
            ret.remove(0)
        return [-1,*ret,1,*ret,-1]

#print( rec(n, list()) )


count = 0
for e in rec(n, list() ):
    abs_e = abs(e)

    if x == 0:
        break

    if x>=abs_e:
        x -= abs_e
        count += e if e>0 else 0
    else:
        count += x if e>0 else 0
        x = 0
    #print(x," ",count)

print(count)


### FIXED CODE ###


# post-placed for
# counter for counter in iterator
#  

#Shiti Go San
def sgs(s:str)->bool:
    return True if all( s.count(c)>0 for c in "753") else False





n = int( input() )


def recursive(s:str)->int:
    if n < int(s):
        return 0

    ret = 1 if sgs(s) else 0

    for x in "753":
       ret += recursive( s + x )
    
    return ret

print( recursive('0') )
N = int(input())
A = list(map(int,input().split()))

if 0 in A:
  print(0)
  
else:
  ans = 1
  for a in A:
    ans *= 1
    if ans>10**18:
      ans = -1
      break
  print(ans)

### FIXED CODE ###

A,B = map(int,input().split())
print(A*B)
n = int(input())
a = list(map(int, input().split()))
l = []
for i in a:
    count = 0
    for j in range(1, 20):
        if i%(2**j) == 0:
            count += 1
        else:
            l.append(count)
            break
print(min(l))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
l = []
for i in a:
    count = 0
    for j in range(1, 31):
        if i%(2**j) == 0:
            count += 1
        else:
            l.append(count)
            break
print(min(l))
import sys

class Okojo:
    def __init__(self, line):
        self.line = line
        self.l = []
        self.r = []
        self.get_lr()

    def get_lr(self):
        for i in range(len(self.line)):
            if self.line[i] == 'L':
                self.l.append(i)
            else:
                self.r.append(i)

    def get_next(self, state):
        nex = [0] * len(self.line)
        for i in range(len(self.l)):
            nex[self.l[i] - 1] += state[self.l[i]]
        for i in range(len(self.r)):
            nex[self.r[i] + 1] += state[self.r[i]]
        return nex


def resolve():
    line = sys.stdin.readline()

    okojo = Okojo(line)

    now = [1] * len(line)
    before1 = now
    for i in range(10 ** 100):
        before2 = before1
        before1 = now
        now = okojo.get_next(before1)
        if before1 == now:
            break
        elif before2 == now:
            if i % 2 == 0:
                now = before1
            break

    print(*now)


resolve()


### FIXED CODE ###

def resolve():
    line = input()
    result = [0] * len(line)

    r_odd = 0
    r_even = 0
    for i in range(len(line)):
        if line[i] == 'L':
            if i % 2 == 0:
                result[i] += r_even
                result[i-1] += r_odd
            else:
                result[i] += r_odd
                result[i-1] += r_even
            r_odd = 0
            r_even = 0
        elif line[i] == 'R':
            if i % 2 == 0:
                r_even += 1
            else:
                r_odd += 1
    l_odd = 0
    l_even = 0
    for i in range(len(line)-1, -1, -1):
        if line[i] == 'R':
            if i % 2 == 0:
                result[i] += l_even
                result[i+1] += l_odd
            else:
                result[i] += l_odd
                result[i+1] += l_even
            l_odd = 0
            l_even = 0
        elif line[i] == 'L':
            if i % 2 == 0:
                l_even += 1
            else:
                l_odd += 1

    print(*result)
    
resolve()
A, B, X = map(int, input().split())
ans = 0

if (X - B * 10) // A > pow(10, 9):
  ans = pow(10, 9)  
else:
        for i in range(1, 10):
       	    num = (X - i * B) // A
        if i == 10 and num > pow(10, 9):
            ans = pow(10, 9)
        if pow(10, i) > num >= pow(10, i - 1):
            ans = max(ans, num)
        elif num >= pow(10, i):
            ans = max(ans, pow(10, i) - 1)

print(ans)


### FIXED CODE ###

N = int(input())
f = [list(map(int, input().split())) for _ in range(N)]
p = [list(map(int, input().split())) for _ in range(N)]

ans = []
stk = []

stk.append([0] * N)

for i in range(10):
    len_stk = len(stk)
    for j in range(len_stk):
        total = 0
        arr = []
        for k in range(N):
            open_cnt = stk[j][k] + f[k][i]
            arr.append(open_cnt)
            total += p[k][open_cnt]
        ans.append(total)
        stk.append(arr)

print(max(ans))
A = [int(v) for v in input()]

for i in range(2):
  total = A[0]
  if i == 0:
    total += A[1]
  else:
    total -= A[1]
  for j in range(2):
    if j == 0:
      total += A[2]
    else:
      total -= A[2]
    for k in range(2):
      if k == 0:
        total += A[3]
      else:
        total -= A[3]
      if total == 7:
        print(A[0], end='')
        if i == 0:
          print('+{}'.format(A[1]), end='')
        else:
          print('-{}'.format(A[1]), end='')
        if j == 0:
          print('+{}'.format(A[2]), end='')
        else:
          print('-{}'.format(A[2]), end='')
        if k == 0:
          print('+{}=7'.format(A[3]))
        else:
          print('-{}=7'.format(A[3]))
        return

### FIXED CODE ###

A = [int(v) for v in input()]

flag = False
for i in range(2):
  if flag:
    break
  total = A[0]
  if i == 0:
    total += A[1]
  else:
    total -= A[1]
  for j in range(2):
    if flag:
      break
    total2 = total
    if j == 0:
      total2 += A[2]
    else:
      total2 -= A[2]
    for k in range(2):
      total3 = total2
      if k == 0:
        total3 += A[3]
      else:
        total3 -= A[3]
      if total3 == 7:
        print(A[0], end='')
        if i == 0:
          print('+{}'.format(A[1]), end='')
        else:
          print('-{}'.format(A[1]), end='')
        if j == 0:
          print('+{}'.format(A[2]), end='')
        else:
          print('-{}'.format(A[2]), end='')
        if k == 0:
          print('+{}=7'.format(A[3]))
        else:
          print('-{}=7'.format(A[3]))
        flag = True
        break
x = int (import)
print (x ** 3)

### FIXED CODE ###

x = int(input())
print (x ** 3)
import math
import sys

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.insert(0, 0)
B = [0] * (N+1)

def operation():
  global A, B, N
  for i in range(1, N+1):
    left = math.ceil(i - A[i] - 0.5)
    right = math.floor(i + A[i] + 0.5)
    if left < 1:
      left = 1
    if right > N:
      right = N
    for j in range(left, right+1):
      B[j] += 1


operation()

#print(A)
#print(B)

for _ in range(K):
  for i in range(1, N+1):
    if A[i] != B[i]:
      A[i] = B[i]
    B[i] = 0
  operation()
  if A == B:
    ans = [N]* N
	print(ans)
    sys.exit()

print(A[1:])



### FIXED CODE ###

import math

N, K = map(int, input().split())
K = min(41, K)
A = list(map(int, input().split()))
A.insert(0, 0)

def operation():
  global A, N
  B = [0] * (N+1)
  for i in range(1, N+1):
    left = max(1, math.ceil(i - A[i] - 0.5))
    right = min(N, math.floor(i + A[i] + 0.5))
    B[left] += 1
    if right+1 <= N:
      B[right+1] -= 1
  for i in range(1, N+1):
    B[i] += B[i-1]
  return B


operation()

#print(A)
#print(B)

for _ in range(K):
  A = operation()

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

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split(" ")))
t=[0 for i in range(n)]
for i in range(n-1):
  b=a[i]
  t[b-1]=t[b-1]+1
for j in range(n):
  print(t[j])
import sys, math
from collections import deque

readline = sys.stdin.readline

S = int(readline())

M = 10 ** 9
rS = math.ceil(math.sqrt(S))

while True:
    rem = rS ** 2 - S


    if rem <= M:
        b = rem
        break
    else:
        b = 0
        a = rem // M + 1
        c = math.floor(rem ** 0.5)
        while a < c:
            if rem % a == 0:
                b = a
                break
            a += 1
        if b != 0:
            break
    
    if rS == M:
        rS -= 50
    else:
        rS += 1
print('0 0 {} {} {} {}'.format(rS, b, rem // b, rS))

### FIXED CODE ###

import sys, math
from collections import deque

readline = sys.stdin.readline

S = int(readline())

M = 10 ** 9
rS = math.ceil(math.sqrt(S))

while True:
    rem = rS ** 2 - S

    if rem == 0:
        print('0 0 {} {} {} {}'.format(rS, 0, 0, rS))
        exit(0)

    if rem <= M:
        b = rem
        break
    else:
        b = 0
        a = rem // M + 1
        c = math.floor(rem ** 0.5)
        while a < c and a < M:
            if rem % a == 0:
                b = a
                break
            a += 1
        if b != 0:
            break
    
    if rS >= M:
        rS = M - 1000
    else:
        rS += 1


print('0 0 {} {} {} {}'.format(rS, b, rem // b, rS))
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
ans=sum(B)
for i in range(N):
    if A[i+1]-A[i]==1:
        ans=+C[A[i]]
print(ans)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
ans=sum(B)
for i in range(N-1):
    if A[i+1]-A[i]==1:
        ans+=C[A[i]-1]
print(ans)
a = [i for i in range(int((A-1)*100/8 ), int((A+1)*100/8 ))]
b = [i for i in range(int((B-1)*100/10), int((B+1)*100/10))]

a = [i for i in a if int(i*0.08) == A]
b = [i for i in b if int(i*0.10) == B]

ans = list(set(a) & set(b))
if ans and min(ans) > 0:
    print(min(ans))
else:
    print(-1)


### FIXED CODE ###

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

a = [i for i in range(int((A-1)*100/8 ), int((A+1)*100/8 ))]
b = [i for i in range(int((B-1)*100/10), int((B+1)*100/10))]

a = [i for i in a if int(i*0.08) == A]
b = [i for i in b if int(i*0.10) == B]

ans = list(set(a) & set(b))
if ans and min(ans) > 0:
    print(min(ans))
else:
    print(-1)
import itertools

N = int(sys.stdin.readline())
P = [int(v) for v in sys.stdin.readline().split()]
Q = [int(v) for v in sys.stdin.readline().split()]
Ps = [list(v) for v in itertools.permutations(range(1, N + 1),N)]
Ps = sorted(Ps)

def find(l1):
    for i, l3 in enumerate(Ps):
        if l3 == l1:
            return i
    return 0


print(abs(find(P) - find(Q)))



### FIXED CODE ###

import sys
import itertools

N = int(sys.stdin.readline())
P = [int(v) for v in sys.stdin.readline().split()]
Q = [int(v) for v in sys.stdin.readline().split()]
Ps = [list(v) for v in itertools.permutations(range(1, N + 1),N)]
Ps = sorted(Ps)

def find(l1):
    for i, l3 in enumerate(Ps):
        if l3 == l1:
            return i
    return 0

print(abs(find(P) - find(Q)))
N, A, B = [int(s) for s in input().split()]
r = 0;
def sumdig(n):
    r = 0;
    d = n % 10;
    r += d;
    n = (n - d) / 10;
    d = n % 10;
    r += d;
    n = (n - d) / 10;
    d = n % 10;
    r += d;
    n = (n - d) / 10;
    d = n % 10;
    r += d;
    n = (n - d) / 10;
    return r;
for n in range(1, N + 1):
    s = sumdig(n)
    if (s >= A and s <= B):
        r += n;
print(r)


### FIXED CODE ###

A, B, C, D = map(int, input().split())
L = A+B
R = C+D
if L > R:
  print("Left")
if L == R:
  print("Balanced")
if L < R:
  print("Right")
n, *s = map(int, open(0).read().split())

c0 = s.count('AC')
c1 = s.count('WA')
c2 = s.count('TLE')
c3 = n - (c0 + c1 + c2)

print('AC x ' + str(c0), 'WA x ' + str(c1), sep='\n')
print('TLE x ' + str(c2), 'RE x ' + str(c3), sep='\n')

### FIXED CODE ###

n, *s = open(0).read().split()
n = int(n)

c0 = s.count('AC')
c1 = s.count('WA')
c2 = s.count('TLE')
c3 = n - (c0 + c1 + c2)

print('AC x ' + str(c0), 'WA x ' + str(c1), sep='\n')
print('TLE x ' + str(c2), 'RE x ' + str(c3), sep='\n')
from functools import lru_cache

L = input().split()
sprime = 998244353 # approx 10**9
N = int(L[0])
A = int(L[1])
B = int(L[2])
K = int(L[3])

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

@lru_cache(maxsize=N)
def factorial(m):
	a = 1
	for i in range(1,m):
		a = (a*i) % sprime
	return a

def binom(m):
	if N == m:
		return 1
	elif m == 1:
		return N
	elif m > N:
		return 0
	else:
		return (factorial(N) * modinv(factorial(m),sprime) * modinv(factorial(N-m),sprime)) % sprime

# max is A*N + B*N
sum = 0
for i in range(0,N):
	if (K - A*i) % B == 0:
		j = (K-A*i)//B
		sum += (binom(N,i) * binom(N,j)) % sp

print(sum)



### FIXED CODE ###

N,A,B,K = map(int,input().split())
sprime = 998244353 # approx 10**9
A,B = sorted((A,B))
if (A+B) * N < K:
	print(0)
	exit()
 
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
 
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
 
memo = [0] * (N+1)
memo[0] = memo[N] = 1
for i in range(1,N//2+1):
	v = memo[i-1] * (N-i+1) * modinv(i,sprime)
	v = v % sprime
	memo[i] = memo[N-i] = v
 
# max is A*N + B*N
sum = 0
for b in range(N+1):
  a = (K-b*B)//A
  if 0 <= a <= N and a*A+b*B == K:
    sum += memo[a]*memo[b]
    sum %= sprime

print(sum)
ss = input()
set_ss = set(ss)
if len(set_ss) != 2 :
  print("No")
else:
	for s in set(ss):
    	if ss.count(s) != 2:
          print("No")
          break
    else:
    	print("Yes") 

### FIXED CODE ###

ss = input()
set_ss = set(ss)
if len(set_ss) != 2 :
  print("No")
else:
  for s in set(ss):
    if ss.count(s) != 2:
      print("No")
      break
  else:
    print("Yes")
#!/usr/bin/env python3
from collections import defaultdict
from math import comb
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main(A, N):
    d1 = defaultdict(int)
    d2 = defaultdict(int)

    for i, a in enumerate(A):
        d1[i+a] += 1
    
    for i, a in enumerate(A):
        d2[i-a] += 1

    mn_x = min(min(d1.keys()), min(d2.keys()))
    mx_x = max(max(d1.keys()), max(d2.keys()))

    cnt = 0
    for x in range(mn_x, mx_x+1):
        cnt += d1[x]* d2[x]

    print(cnt)
    pass

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    main(A, N)


### FIXED CODE ###

#!/usr/bin/env python3
from collections import defaultdict

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main(A, N):
    d1 = defaultdict(int)
    d2 = defaultdict(int)

    for i, a in enumerate(A):
        d1[i+a] += 1
    
    for i, a in enumerate(A):
        d2[i-a] += 1

    cnt = 0
    for x in list(d1.keys())+list(d2.keys()):
        cnt += d1[x]* d2[x]

    print(cnt//2)
    pass

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    main(A, N)
a,b,c,d=map(int, input().split())
print('Balanced' if  a+b==c+d 'Left' a+b>c+d else 'Right')

### FIXED CODE ###

a,b,c,d=map(int, input().split())
print('Balanced' if  a+b==c+d else 'Left' if a+b>c+d else 'Right')
MOD=10**9+7
N,K=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ans=set()
if 0 in ls:
  ans.add(0)
else:
  als=sorted(ls, key=lambda x: -abs(x))
  mul=1
  for i in range(K):
    mul*=als[i]
  if mul>0:
    ans.add(mul)
  else:
    ls2=als[:K]
    ls3=als[K:]
    M2=max(ls2)
    m2=min(ls2)
    M3=max(ls3)
    m3=max(ls3)
    ans=set()
    if M2!=0:
      ans.add(mul*m3//M2)
      ans.add(mul*m3//m2)
    if m2!=0:
      ans.add(mul*M3//M2)
      ans.add(mul*M3//m2)
print(max(ans)%MOD)


### FIXED CODE ###

MOD=10**9+7
N,K=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ans=set()
ls=sorted(ls, key=lambda x: -abs(x))
mul=1
sign=0
zeroflag=0
flag=[0 for _ in range(N)]
for i in range(K):
  flag[i]=1
  if ls[i]<0:
    sign=(sign+1)%2
if sign==1:
  if 0 in ls:
    zeroflag=1
  a=[0,0,0,0]
  b=[0,0,0,0]
  for j in range(K,N):
    if ls[j]>0:
      for k in range(K):
        if ls[K-1-k]<0:
          a[0]=ls[j]
          b[0]=j
          a[1]=ls[K-1-k]
          b[1]=K-1-k
          break
      break
  for j in range(K,N):
    if ls[j]<0:
      for k in range(K):
        if ls[K-1-k]>0:
          a[2]=ls[j]
          b[2]=j
          a[3]=ls[K-1-k]
          b[3]=K-1-k
          break
      break
  if a==[0,0,0,0]:
    flag.reverse()
  elif b[0]==0 and b[1]==0:
    flag[b[2]]=1
    flag[b[3]]=0
  elif b[2]==0 and b[3]==0:
    flag[b[0]]=1
    flag[b[1]]=0
  elif abs(a[0]*a[3])>abs(a[1]*a[2]):
    flag[b[0]]=1
    flag[b[1]]=0
  else:
    flag[b[2]]=1
    flag[b[3]]=0
if sign==1 and a==[0,0,0,0] and zeroflag==1:
  print(0)
else:
  mul=1
  for i in range(N):
    if flag[i]==1:
      mul=mul*ls[i]%MOD
  print(mul)
def init():
  global top
  top = 0

def isEmpty():
  global top
  return top == 0

def isFull():
  global top, MAX
  return top >= MAX

def push(x):
  global top, s
  if isFull():
    return False
  s[top] = x
  top += 1


def pop():
  global top, s
  if isEmpty():
    return False
  s[top + 1]
  top -= 1
  return s[top]


def calc(i_1, i_2, op):
  if op == '+':
    return i_1 + i_2
  elif op == '-':
    return i_1 - i_2
  else:
    return i_1 * i_2

data = list(map(str, input().split()))
top = 0
MAX = 100
s = [0 for i in range(MAX)]
for i in data:
  if i == '+' or i == '*' or i == '-':
    a = pop()
    b = pop()
    push(calc(int(b), int(a), i))
  else:
    push(i)
print(s[0])



### FIXED CODE ###

def init():
  global top
  top = -1

def isEmpty():
  global top
  return top == -1

def isFull():
  global top, MAX
  return top >= MAX

def push(x):
  global top, s
  if isFull():
    return False
  s[top] = x
  top += 1


def pop():
  global top, s
  if isEmpty():
    return False
  top -= 1
  return s[top]


def calc(i_1, i_2, op):
  if op == '+':
    return i_1 + i_2
  elif op == '-':
    return i_1 - i_2
  else:
    return i_1 * i_2

data = list(map(str, input().split()))
top = 0
MAX = 100
s = [0 for i in range(MAX)]
for i in data:
  if i == '+' or i == '*' or i == '-':
    a = pop()
    b = pop()
    push(calc(int(b), int(a), i))
  else:
    push(i)
print(s[0])