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

def main():
  n, m = map(int, input().split())
  def zs(num):
    k = 6 - len(str(num))
    return '0' * k + str(num)
  lst = [[-1] for i in range(n + 1)]
  cities = []
  for i in range(m):
    temp = tuple(map(int, input().split()))
    lst[temp[0]].append(temp[1])
    cities.append(temp)
  for l in lst:
    l.sort()
  for tpl in cities:
    a = lst[tpl[0]].index(tpl[1])
    print(zs(tpl[0]) + zs(a))
if __name__ == '__main__':
  main()

### FIXED CODE ###

n, m = map(int, input().split())
def zs(num):
    k = 6 - len(str(num))
    return '0' * k + str(num)
lst = []
for i in range(m):
  lst.append(tuple(map(int, input().split())))
slst = sorted(lst)
dic = {}
temp = 0
for i in range(m):
  if slst[i][0] == slst[i - 1][0]:
    temp += 1
  else:
    temp = 1
  dic[slst[i]] = zs(slst[i][0]) + zs(temp)
for i in lst:
  print(dic[i])
### BUGGY CODE ###

from sys import stdin
h, n = map(int, input().split())
magic = [list(map(int, stdin.readline().split())) for _ in range(n)]
ans = [float('inf')]*(h+1)
ans[-1] = 0

for i in range(h, 0, -1):
    if ans[i] == float('inf'):
        continue
    else:
        for j in magic:
            if i-j[0] <= 0:
                ans[0] = min(ans[i]+j[1], ans[0])
            else:
                ans[i-j[0]] = min(ans[i]+j[1], ans[i-j[0]])
print(ans[0])




### FIXED CODE ###

def num():
    from sys import stdin
    h, n = map(int, input().split())
    magic = [list(map(int, stdin.readline().split())) for _ in range(n)]
    INF = float('inf')
    ans = [INF]*(h+1)
    ans[-1] = 0

    for i in range(h, 0, -1):
        if ans[i] != INF:
            for j, k in magic:
                if i-j < 0:
                    num = ans[i]+k
                    if ans[0] > num:
                        ans[0] = num
                else:
                    num = ans[i]+k
                    if ans[i-j] > num:
                        ans[i-j] = num
    return ans[0]
print(num())
### BUGGY CODE ###

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

for i in range(N):
    print(A.index(i+1)+1, end=' ')


### FIXED CODE ###

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

A2 = [0]*N

i =1
for a in A:
  A2[a-1] = i
  i+=1

print(*A2)
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)]

INF = float('inf')

d = [[INF] * W for _ in range(H)]


def bfs(i, j):
    q = deque()
    q.append((i, j))
    d[i][j] = 0

    while len(q):
        x, y = q.popleft()
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x + dx
            ny = y + dy

            if (0 <= nx < H) and (0 <= ny < W) and d[nx][ny] > d[x][y] + 1:
                q.append((nx, ny))
                d[nx][ny] = d[x][y] + 1


for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            bfs(i, j)

res = 0
for i in range(H):
    for j in range(W):
        res = max(res, d[i][j])

print(res)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)]

# d = [[2001] * W for _ in range(H)]


def bfs(q):
    res_q = deque()
    while len(q):
        x, y = q.popleft()
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x + dx
            ny = y + dy

            if (0 <= nx < H) and (0 <= ny < W) and grid[nx][ny] != '#':
                res_q.append((nx, ny))
                grid[nx][ny] = '#'
    return res_q


q = deque()
for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            q.append((i, j))

res = 0
while len(q):
    res += 1
    q = bfs(q)

print(res - 1)
### BUGGY CODE ###

input(); n = list(map(int, input().split()))
prod = 1
for i in n:
    prod *= i
print(-1 if prod > 10**18 else prod)

### FIXED CODE ###

input(); n = list(map(int, input().split()))
if 0 in n:
    print(0); exit()
prod = 1
for i in n:
    prod *= i
    if prod > 10**18: prod = -1; break
print(prod)
### BUGGY CODE ###

if __name__ == '__main__':
	S = input()
	LEN = len(S)
	r = LEN
	l = LEN-1
	count = 0
	lst = []
	while(l >= 0):
		amari = int(S[l:r])%2019
		
		if amari in lst:
			count += 1
		elif amari == 0:
			count += 1
			lst.append(count)
		else:
			lst.append(amari)
		l -= 1

	print(count)

### FIXED CODE ###

def POW(x, n, mod):
    ans = 1
    # n が 0 になるまで計算を続ける
    while n > 0:
        if n % 2 == 1:
            ans *= x%mod
        x = (x*x)%mod						#x = x**2
        n >>= 1						#ビットシフト
    return ans

if __name__ == '__main__':
	S = input()
	L = len(S)
	lst = [0] * 2019
	lst[0] = 1
	amari = 0
	ans = 0
	for i in range(1,L+1):
		amari = ( int(S[L-i]) * POW(10,i-1,2019) + amari ) % 2019
		lst[amari] += 1

	for i in range(2019):
		m = lst[i]
		ans += m * (m-1) / 2

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

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

for i in range(n):
  b=b*a[i]
if b>10**18:
  print(-1)
else:
  print(b)

### FIXED CODE ###

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

for i in range(n):
  b=b*a[i]
  if b>10**18:
    b=-1
    break
  
print(b)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    s = input()
    L = len(s)
    dp = [[0] * 13 for _ in range(L + 1)]
    dp[0][0] = 1

    for i in range(L):
        for j in range(13):
            if s[i] == "?":
                for k in range(10):
                    dp[i + 1][(j * 10 + k) % 13] += dp[i][j] % mod
            else:
                k = int(s[i])
                dp[i + 1][(j * 10 + k) % 13] += dp[i][j] % mod

    print(dp[-1][5] % mod)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

s = input()
L = len(s)
MOD = 10 ** 9 + 7
dp = [[0 for _ in range(13)] for _ in range(L + 1)]
dp[0][0] = 1

for i in range(1, L + 1):
    if s[i - 1] == "?":
        for j in range(10):
            for k in range(13):
                dp[i][(k * 10 + j) % 13] += dp[i - 1][k] % MOD
    else:
        for k in range(13):
            dp[i][(k * 10 + int(s[i - 1])) % 13] += dp[i - 1][k] % MOD

print(dp[-1][5] % MOD)
### BUGGY CODE ###

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

ans = 1
for a in A:
  ans *= a

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

### FIXED CODE ###

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

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

from heapq import heappush, heappop

if __name__ == '__main__':
    # ??????????????\???
    # ???????????????
    h = []
    while True:
        raw_input = input()
        if raw_input == 'end':
            break
        if raw_input.startswith('insert'):
            data = raw_input.split(' ')
            heappush(h, (-1*int(data[1]), data[1]))
        elif raw_input == 'extract':
            pri, item = heappop(h)
            print(item)

### FIXED CODE ###

from heapq import heappush, heappop

if __name__ == '__main__':
    # ??????????????\???
    # ???????????????
    h = []
    while True:
        raw_input = input()
        if raw_input == 'extract':
            pri, item = heappop(h)
            print(item)
        elif raw_input == 'end':
            break
        else:
            cmd, pri = raw_input.split()
            heappush(h, (-1*int(pri), pri))
### BUGGY CODE ###

n = int(input())
v = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]
indices = range(n)
l = []
for i in range(1 << n):
  l.append([indices[j] for j in range(n) if (i & (1 << j))])
l.pop(0)#[]
#c.index()
max_diff = 0
for s in l:
  cost = 0
  value = 0
  for i in s:
    cost += c[i]
    value += v[i]
    if value - cost > max_diff:
      max_diff = value - cost
print(max_diff)
  


### FIXED CODE ###

n = int(input())
v = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]

total = 0
for i in range(n):
  if v[i] > c[i]:
    total += v[i] - c[i]
print(total)
### BUGGY CODE ###

import sys
f=lambda:map(int,sys.stdin.readline().split())
h,n=f()
INF=10**9
dp=[[INF]*(h+1) for _ in range(n+1)]
dp[0][0]=0
for i in range(n):
  a,b=f()
  for j in range(h+1):
    dp[i+1][j]=min(dp[i][j],dp[i+1][max(j-a,0)]+b)
print(dp[n][h])

### FIXED CODE ###

import sys
f=lambda:map(int,sys.stdin.readline().split())
h,n=f()
INF=10**9
dp=[[INF]*(h+1) for _ in range(n+1)]
dp[0][0]=0
for i in range(n):
  a,b=f()
  for j in range(h+1):
    dp[i+1][j]=min(dp[i][j],dp[i+1][max(j-a,0)]+b)
print(dp[n][h])
### BUGGY CODE ###

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

es = tuple(es)
der = tuple(der)
def shortest_path(S,n,w,es): 
  d = [10**15] * n #d[i] : s→iの最短距離
  d[S] = 0
  while True:
    update = False
    for p,q,r in es: # e: 辺iについて [from,to,cost]
      if d[p] != 10**15 and d[q] > d[p] + r:
        d[q] = d[p] + r
        update = True       
    if not update:
      break
  return d

chk = [0]*n
ES = tuple(shortest_path(s-1,n,m*2,es))
DER = tuple(shortest_path(t-1,n,m*2,der))
cost = 10**15
for i in range(n-1,-1,-1):
  cost = min(cost,ES[i]+DER[i])
  chk[i] = 10**15-cost
chk = tuple(chk)

print(*chk, sep="\n")

### FIXED CODE ###

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

es = tuple(es)
egg = tuple(egg)

import heapq
def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**18] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

ES = dijkstra_heap(s-1,es)
EDGE = dijkstra_heap(t-1,egg)
cost = 0
chk = [0]*n
for i in range(n-1,-1,-1):
  cost = max(cost,10**15-ES[i]-EDGE[i])
  chk[i] = cost
chk = tuple(chk)
print(*chk, sep="\n")
### BUGGY CODE ###

dice = list(map(int, input().split()))
dice2 = list(map(int, input().split()))
mask = {
    'N': (1, 5, 2, 3, 0, 4),
    'R': (0, 2, 4, 1, 3, 5)
    }

a, b = dice2[0], dice2[1]

find = True
lim = 0

n_cmp_flg = False
while dice[0] != a:
    dice = [dice[x] for x in mask['N']]
    lim += 1
    if lim == 4:
        if n_cmp_flg:
            find = False
            break
        else:
            n_cmp_flg = True
            dice = [dice[x] for x in mask['R']]
            lim = 0
lim = 0
while dice[1] != b:
    dice = [dice[x] for x in mask['R']]
    lim += 1
    if lim == 4:
        find = False

if find:
    if dice == dice2:
        print("Yes")
    else:
        print("No")
else:
    print("No")



### FIXED CODE ###

dice = list(map(int, input().split()))
dice2 = list(map(int, input().split()))
mask = {
    'N': (1, 5, 2, 3, 0, 4),
    'R': (0, 2, 4, 1, 3, 5)
    }

a, b = dice2[0], dice2[1]

find = False

for i in range(4):

    for j in range(4):
        if dice == dice2:
            find = True
            break
        dice = [dice[x] for x in mask['R']]

    if dice == dice2:
        find = True
        break
    dice = [dice[x] for x in mask['N']]

dice = [dice[x] for x in mask['R']]
dice = [dice[x] for x in mask['N']]
for j in range(4):
    if dice == dice2:
        find = True
        break
    dice = [dice[x] for x in mask['R']]

dice = [dice[x] for x in mask['N']]
dice = [dice[x] for x in mask['N']]
for j in range(4):
    if dice == dice2:
        find = True
        break
    dice = [dice[x] for x in mask['R']]

if find:

    print("Yes")
else:
    print("No")
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    ans=1
    for i in range(1,N+1):
        ans *= i
    print(ans%(10**9+7))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    ans=1
    for i in range(1,N+1):
        ans = ans%(10**9+7) * i%(10**9+7)
        
    print(ans%(10**9+7))

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

l,r = map(int,input().split())
c = [4*10**18]
for i in range(l,r):
    for j in range(i+1,r+1):
        c.append((i*j)%2019)
print(min(c))

### FIXED CODE ###

l,r = map(int,input().split())
r = min(r,l+2019)
c = [4*10**18]
for i in range(l,r):
    for j in range(i+1,r+1):
        c.append((i*j)%2019)
print(min(c))
### BUGGY CODE ###

s = input()
q = int(input())
query = [list(input().replace(' ','')) for _ in range(q)]

r = False
for i in range(q):
    if r:
        if len(query[i]) == 1:
            r = False
        elif query[i][1] == '1':
            s = s + query[i][2]
        else:
            s = query[i][2] + s
    else:
        if len(query[i]) == 1:
            r = True
        elif query[i][1] == '1':
            s = query[i][2] + s
        else:
            s = s + query[i][2]

if r:
    print(s[::-1])
else:
    print(s)

### FIXED CODE ###

from collections import deque

s = deque(input())
q = int(input())
query = [input().split() for _ in range(q)]

reverse = False
for i in query:
    if len(i) == 1:
        if reverse:
            reverse = False
        else:
            reverse = True
    else:
        if reverse:
            if i[1] == '1':
                s.append(i[2])
            else:
                s.appendleft(i[2])
        else:
            if i[1] == '1':
                s.appendleft(i[2])
            else:
                s.append(i[2])
if reverse:
    s = reversed(s)
    s = ''.join(s)
    print(s)
else:
    s = ''.join(s)
    print(s)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

import sys
input = sys.stdin.readline

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

from collections import defaultdict
G = defaultdict(list)

for _ in range(n-1):
    u,v = map(int,input().split())
    G[u-1].append(v-1)
    G[v-1].append(u-1)

from bisect import bisect
ansl = [0 for i in range(n)]
dp = [float("inf") for _ in range(n+1)]
dp[0] = -1
used = [0 for i in range(n)]
used[0] = 1


stack = []
def dfs(pos):
    idx = bisect(dp, al[pos] - 1)
    stack.append((idx, dp[idx]))
    dp[idx] = min(al[pos], dp[idx])
    ansl[pos] = bisect(dp, 10**18) - 1
    for i in range(n):
        if dp[i] == "inf":
            ansl[pos] = i
            break
    for v in G[pos]:
        if used[v] == 0:
            used[v] = 1
            dfs(v)
            idx, k = stack.pop()
            dp[idx] = k


dfs(0)
flag = False
for i in range(n):
    print(ansl[i])




### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

import sys
input = sys.stdin.readline

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

from collections import defaultdict
G = defaultdict(list)

for _ in range(n-1):
    u,v = map(int,input().split())
    G[u-1].append(v-1)
    G[v-1].append(u-1)

from bisect import bisect
ansl = [0 for i in range(n)]
dp = [float("inf") for _ in range(n+1)]
dp[0] = -1
used = [0 for i in range(n)]
used[0] = 1


stack = []
def dfs(pos):
    idx = bisect(dp, al[pos] - 1)
    stack.append((idx, dp[idx]))
    dp[idx] = min(al[pos], dp[idx])
    ansl[pos] = bisect(dp, 10**18) - 1
    for v in G[pos]:
        if used[v] == 0:
            used[v] = 1
            dfs(v)
            idx, k = stack.pop()
            dp[idx] = k


dfs(0)
flag = False
for i in range(n):
    print(ansl[i])
### BUGGY CODE ###

N, C = map(int, input().split())
sushi = [[int(x) for x in input().split()] for _ in range(N)]

ans = 0
for i in range(N + 1):
    # OA
    if i == 0:
        oa_x = 0
        oa_v = 0
    else:
        oa_x = sushi[i - 1][0]
        oa_v = sum([sushi[ii][1] for ii in range(i)])

    for j in range(N + 1):
        # OB
        if j == 0:
            ob_x = 0
            ob_v = 0
        else:
            ob_x = C - sushi[j - 1][0]
            ob_v = sum([sushi[jj][1] for jj in range(N - 1, j - 2, -1)])

        v = oa_v + ob_v

        # 2OA + OB
        x = 2 * oa_x + ob_x
        if x < C:
            ans = max(ans, v - x)

         # OA + 2OB
        x = oa_x + 2 * ob_x
        if x < C:
            ans = max(ans, v - x)
print(ans)


### FIXED CODE ###

from itertools import accumulate

N, C = map(int, input().split())
sushi = [[int(x) for x in input().split()] for _ in range(N)]


def solve():
    """
    O(N)
    Bを固定したときの最適なAを事前に計算
    """
    V = [0] * (N + 1)
    for i in range(N):
        V[i + 1] = V[i] + sushi[i][1]

    f1 = [0] + [V[a + 1] - sushi[a][0] for a in range(N)]
    f2 = [0] + [V[a + 1] - 2 * sushi[a][0] for a in range(N)]

    g1 = [x for x in accumulate(f1, max)]
    g2 = [x for x in accumulate(f2, max)]

    ans = 0
    for j in range(N + 1):
        # OA
        if j == 0:
            i = N
        else:
            i = j - 1

        # OB
        if j == 0:
            ob_x = 0
        else:
            ob_x = C - sushi[j - 1][0]
        ob_v = V[N] - V[j - 1]

        # 2OA + OB
        ans = max(ans, g2[i] + ob_v - ob_x)

        # OA + 2OB
        ans = max(ans, g1[i] + ob_v - 2 * ob_x)
    print(ans)


solve()
### BUGGY CODE ###

R,C,K = map(int,input().split())
dp = [[[0 for l in range(4)] for _ in range(C+1)] for f in range(R+1)]
vl = [[0 for _ in range(C+1)] for f in range(R+1)]

for i in range(K):
	r,c,v = map(int,input().split())
	vl[r][c] = v

for i in range(1, R+1):
	for j in range(1, C+1):
		for k in range(4):
			dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k])
		dp[i][j][0] = max(dp[i][j][0], dp[i-1][j][0], dp[i-1][j][1], dp[i-1][j][2], dp[i-1][j][3])
		if vl[i][j] >= 1:
			for k in range(3, 0, -1):
				dp[i][j][k] = max(dp[i][j][k-1]+vl[i][j], dp[i][j][k])
		
print(max(dp[R][C][0], dp[R][C][1], dp[R][C][2], dp[R][C][3]))

### FIXED CODE ###

R,C,K = map(int,input().split())
dp0 = [[0 for _ in range(C+1)] for f in range(R+1)]
dp1 = [[0 for _ in range(C+1)] for f in range(R+1)]
dp2 = [[0 for _ in range(C+1)] for f in range(R+1)]
dp3 = [[0 for _ in range(C+1)] for f in range(R+1)]
vl = [[0 for _ in range(C+1)] for f in range(R+1)]

for i in range(K):
	r,c,v = map(int,input().split())
	vl[r][c] = v

for i in range(1, R+1):
	for j in range(1, C+1):
		dp0[i][j] = max(dp0[i][j], dp0[i-1][j], dp1[i-1][j], dp2[i-1][j], dp3[i-1][j])
		dp3[i][j] = max(dp3[i][j], dp3[i][j-1], dp2[i][j-1]+vl[i][j], dp2[i][j]+vl[i][j])
		dp2[i][j] = max(dp2[i][j], dp2[i][j-1], dp1[i][j-1]+vl[i][j], dp1[i][j]+vl[i][j])
		dp1[i][j] = max(dp1[i][j], dp1[i][j-1], dp0[i][j-1]+vl[i][j], dp0[i][j]+vl[i][j])

print(max(dp0[R][C], dp1[R][C], dp2[R][C], dp3[R][C]))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
ans = count1 = count2 = 0

n,k=map(int,input().split())
count1+=n//k
if k%2==0:count2+=(n+k//2)//k
# for ii in itertools.product(range(1,n//k+2), repeat=3):
#     print(ii)
# print(count)
a=len(list(itertools.product(range(count1),repeat=3)))
b=len(list(itertools.product(range(count2),repeat=3)))
print(a+b)


### FIXED CODE ###

ans = count1 = count2 = 0
n,k=map(int,input().split())
count1+=n//k
if k%2==0:count2+=(n+k//2)//k
print(count1**3+count2**3)
### BUGGY CODE ###

N, K = map(int, input().split())
H = [int(input()) for _ in range(N)]
H = sorted(H, reverse=True)
ans = 1e9
for i in range(N-K+1):
    h = H[i:i+K]
    dh = max(h)-min(h)
    if dh < ans:
        ans = dh
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
H = [int(input()) for _ in range(N)]
H = sorted(H)
ans = 1e9
for i in range(N-K+1):
    ans = min(ans, H[i+K-1]-H[i])
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def main():
    N = II()
    a_list = []

    for i in range(N):
        a = II()
        a_list.append(a)

    g = []

    from bisect import bisect_left

    for i in range(N):
        a = a_list[i]
        if len(g) == 0:
            g.append(a)
        else:
            pos = bisect_left(g, a)
            dprint(g, a, pos)
            if pos >= 1:
                g[pos-1] = a
            else:
                g = [a] + g
    dprint(g)
    print(len(g))
main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def main():
    N = II()
    a_list = []

    for i in range(N):
        a = II()
        a_list.append(a)


    from bisect import bisect_left
    from collections import deque
    g = deque()

    for i in range(N):
        a = a_list[i]
        if len(g) == 0:
            g.appendleft(a)
        else:
            pos = bisect_left(g, a)
            dprint(g, a, pos)
            if pos >= 1:
                g[pos-1] = a
            else:
                #g.insert(0, a)
                g.appendleft(a)
    dprint(g)
    print(len(g))
main()
### BUGGY CODE ###

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

count = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            if L[i] < L[j] + L[k]:
                if L[j] < L[i] + L[k]:
                    if L[k] < L[i] + L[j]:
                        count += 1

print(count)

### FIXED CODE ###

import sys
import bisect

N = int(sys.stdin.readline())
L = list(map(int, sys.stdin.readline().split()))
L = sorted(L)

count = 0
for a_i in range(N-1):
    for b_i in range(a_i+1, N):
        max_c = bisect.bisect_left(L, L[a_i]+L[b_i])
        if max_c > b_i:
            count += max_c - b_i - 1
        
print(count)
### BUGGY CODE ###

N, M = [int(item) for item in input().split()]
price_list = sorted([int(item) for item in input().split()])

ticket_list = []
total_price_list = []
total_m = 0

def discount(price_list, ticket_num):
    total_ticket =0

    while total_ticket < ticket_num:
        price_list[-1] = int(price_list[-1]/2)
        price_list.sort()
        total_ticket += 1

    return price_list

res = discount(price_list, M)
print(sum(res))

### FIXED CODE ###

import heapq as hp
N, M = [int(item) for item in input().split()]
price_list = sorted([-1 * int(item) for item in input().split()])

total_m = 0

def discount(price_list, ticket_num):
    total_ticket =0
    hp.heapify(price_list)

    while total_ticket < ticket_num:
        temp = hp.heappop(price_list)
        hp.heappush(price_list, -1* (-1*temp//2))
        total_ticket += 1

    return price_list

res = discount(price_list, M)
print(-1 * sum(res))
### BUGGY CODE ###

import collections
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
a = a[::-1]
x,answer,num = collections.Counter(a),1,-1
while a != []:
	if x[a[0]]>=4 and num==-1:
		answer = a[0]**2
		num = 1
		break
	elif x[a[0]]>=2:
		answer *= a[0]
		num += 1
		if num==1:
			break
	a = a[x[a[0]]:]
print(max(answer*num,0))

### FIXED CODE ###

import collections
n = int(input())
a = [int(i) for i in input().split()]
x,y,z = collections.Counter(a),[0],[0,0]
for i in x.keys():
	if x[i]>=4:
		y.append(i)
	if x[i]>=2:
		z.append(i)
y,z = sorted(y),sorted(z)
print(max(y[-1]**2,z[-1]*z[-2]))