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

import heapq
import copy
n=int(input())
a=list(map(int,input().split()))
m1=min(a[:n])
s1=sum(a[:n])
ca=copy.deepcopy(a)
f=ca[:n]
heapq.heapify(f)
fs=sum(ca[:n])
t=ca[n:]
ls=sum(heapq.nsmallest(n,t))
ans=fs-ls
for i in range(n,2*n):
    heapq.heappush(f,a[i])
    fs=fs+a[i]-heapq.heappop(f)
    t=a[i+1:]
    ls=sum(heapq.nsmallest(n,t))
    ans=max(ans,fs-ls)
print(ans)

### FIXED CODE ###

import heapq
import copy
n=int(input())
a=list(map(int,input().split()))
ca=copy.deepcopy(a)
f=ca[:n]
heapq.heapify(f)
fs=sum(f)
fsl=[0 for i in range(n+1)]
fsl[0]=fs
for i in range(n,2*n):
    heapq.heappush(f,a[i])
    fs=fs+a[i]-heapq.heappop(f)
    fsl[i-n+1]=fs
l=list(map(lambda x:-x,ca[2*n:]))
heapq.heapify(l)
ls=sum(l)
lsl=[0 for i in range(n+1)]
lsl[-1]=ls
for i in range(n,2*n):
    heapq.heappush(l,-a[3*n-i-1])
    ls=ls-a[3*n-i-1]-heapq.heappop(l)
    lsl[2*n-i-1]=ls
ans=-float('inf')
for i in range(n+1):
    ans=max(ans,fsl[i]+lsl[i])
print(ans)
### BUGGY CODE ###

N = int(input())
list_a = [int(x) for x in input().split()]

ans = 0

for i in range(N) :
    X = list_a[i]
    T0 = list_a.count(X)
    T1 = list_a.count(X+1)
    T2 = list_a.count(X+2)
    Tm1 = list_a.count(X-1)
    Tm2 = list_a.count(X-2)
    ans = max(ans,T0+T1+T2,T0+T1+Tm1,T0+Tm1+Tm2)

print(ans)


### FIXED CODE ###

N = int(input())
list_a = [int(x) for x in input().split()]

list_X = []

for X in list_a :
    list_X.append(X)
    list_X.append(X+1)
    list_X.append(X-1)

from collections import Counter
print(max(Counter(list_X).values()))
### BUGGY CODE ###

input();a,s=list(map(int,input().split())),0
for i in set(a):
  b=a.count(i)
  if i>b:s+=b
  else:s+=abs(i-b)
print(s)

### FIXED CODE ###

from collections import Counter
input();a=Counter(list(map(int,input().split())))
print(sum([v if k>v else v-k for k,v in a.items()]))
### BUGGY CODE ###

import sys
import math
import heapq
from collections import deque
from itertools import combinations
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

H,W=LI()
MP=[input() for _ in range(H)]
CORD=[(i,j) for i in range(H) for j in range(W)]

max_dist = 0
visited=set()
for st, en in combinations(CORD, 2):
    if MP[st[0]][st[1]] == "." and MP[en[0]][en[1]] == ".":
        QUE=deque()
        visited.add(st)
        QUE.append((st[0], st[1], 0))
        res = 0
        while QUE:
            ii, jj, dist = QUE.popleft()
            if (ii, jj) == en:
                res = dist
                visited.clear()
                # print("st:{} en:{} dist:{}".format(st, en, dist))
                break
            for iii, jjj in [(ii-1,jj),(ii+1,jj),(ii,jj-1),(ii,jj+1)]:
                if iii >= 0 and jjj >= 0 and iii < H and jjj < W and MP[iii][jjj] != '#' and not (iii, jjj) in visited:
                    QUE.append((iii, jjj, dist+1))
                    visited.add((iii, jjj))

        max_dist = max(res, max_dist)

print(max_dist)


### FIXED CODE ###

import sys
import math
import heapq
from collections import deque
from itertools import combinations
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

H,W=LI()
MP=[input() for _ in range(H)]
CORD=[(i,j) for i in range(H) for j in range(W)]

max_dist = 0
for i in range(len(CORD)):
    st = CORD[i]
    if MP[st[0]][st[1]] == ".":
        QUE=deque()
        visited = [[0]*W for i in range(H)]
        visited[st[0]][st[1]] = 1
        QUE.append((st[0], st[1], 0))
        res = 0
        while QUE:
            ii, jj, dist = QUE.popleft()
            max_dist = max(max_dist, dist)
            for iii, jjj in [(ii-1,jj),(ii+1,jj),(ii,jj-1),(ii,jj+1)]:
                if iii >= 0 and jjj >= 0 and iii < H and jjj < W and MP[iii][jjj] != '#' and not visited[iii][jjj]:
                    QUE.append((iii, jjj, dist+1))
                    visited[iii][jjj] = 1


print(max_dist)
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh_, dw_ = map(int, input().split())

mvs = [(-1,0),(1,0),(0,1),(0,-1)]
fs = []

for i in range(H):
    r = list(input())
    fs.append(r)

INF = 1 << 50
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0
q = deque([])
q.appendleft((ch-1,cw-1,0))
while len(q)>0:
    h,w,cnt = q.popleft()
    if cnt > dps[h][w]:continue
    dps[h][w] = cnt
    for dh in range(-2,3):
        for dw in range(-2,3):
            hn = h + dh
            wn = w + dw
            if 0<=hn<H and 0<=wn<W:
                if dps[hn][wn] != INF:continue
                if fs[hn][wn] == ".":
                    if (dh,dw) in mvs:
                        q.appendleft((hn, wn, cnt))
                    else:
                        q.append((hn, wn, cnt+1))

ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -1)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh_, dw_ = map(int, input().split())

fs = []
for i in range(H):
    r = list(input())
    fs.append(r)

walks = [(-1,0),(1,0),(0,1),(0,-1)]
magics = []
for i in range(-2,3):
    for j in range(-2,3):
        if i==j==0:continue
        if (i,j) not in walks:
            magics.append((i,j))

INF = 1 << 50
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0
q = deque([])
q.appendleft((ch-1,cw-1,0))
while len(q)>0:
    h,w,cnt = q.popleft()
    if cnt > dps[h][w]:continue
    dps[h][w] = cnt
    for dh, dw in walks:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] != INF:continue
            if fs[hn][wn] == ".":
                q.appendleft((hn, wn, cnt))
    for dh, dw in magics:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] != INF:continue
            if fs[hn][wn] == ".":
                q.append((hn, wn, cnt+1))

ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -1)
### BUGGY CODE ###

num = input()
a = input().split()

b=1
for i in a:
	b *= int(i)

if b > 10**18:
  b = -1

print(b)

### FIXED CODE ###

num = input()
a = input().split()

b=1
if '0' in a:
	b = 0
else:
	for i in a:
		b *= int(i)
		if b > 10**18:
			b = -1
			break

print(b)
### BUGGY CODE ###

import math

N = int(input())
Ai = list(map(int,input().split()))
    
#print(Ai)
def create_list():
  MAXI = N
  
  sn = [0 for _ in range(MAXI+1)]
  judge = 0
  for i in range(1,MAXI+1):
    sn[i] = sn[i-1] + Ai[i-1]
     
  return sn

base = create_list()
#print(base)
count = 0
for i in range(N):
  for j in range(i+1,N+1):
    if(base[j]-base[i] == 0):
      count += 1
print(count)

### FIXED CODE ###

N = int(input())
Ai = list(map(int,input().split()))
    
#print(Ai)
def create_list():
  MAXI = N
  
  sn = [0 for _ in range(MAXI+1)]
  judge = 0
  for i in range(1,MAXI+1):
    #print(str(i)+'+1 when '+S[i-1])
    sn[i] = sn[i-1] + Ai[i-1]
     
  return sn

def iCj(i, j):
  mot = 1
  chi = 1
  for x in range(j):
    chi *= i-x
    mot *= x+1
  comb = int(chi/mot)
  return comb


base = create_list()
#print(base)
count = 0
base.sort()
#print(base)
#for i in range(N):
#  for j in range(i+1,N+1):
#    if(base[j]-base[i] == 0):
#      count += 1
    #  print(str(j)+' - '+str(i))
    #else:
    #  print(str(j)+' = '+str(i))
#  print( base[r[i]] - base[l[i]] )#sum(rnum)-sum(lnum) )
i = 0
while(i<N+1):
  this = 1
  j = i+1
  while(j < N+1 and base[j] == base[i]):
    this += 1
    j += 1
  if(this >= 2):
    count += iCj(this,2)
  i += this
print(count)
### BUGGY CODE ###


K=int(input())
S=input()
M=len(S)
N=K+M
mod=10**9+7
ans=pow(26,N,mod)
class Data():
    def __init__(self):
        self.power=1
        self.rev=1     
class Combi():
    def __init__(self,N,mod):
        self.lists=[Data() for _ in range(N+1)]
        self.mod=mod  
        for i in range(2,N+1):
            self.lists[i].power=((self.lists[i-1].power)*i)%self.mod
        self.lists[N].rev=pow(self.lists[N].power,self.mod-2,self.mod)
        for j in range(N,0,-1):
            self.lists[j-1].rev=((self.lists[j].rev)*j)%self.mod

    def combi(self,K,R):
        if K<R:
            return 0
        else:
            return ((self.lists[K].power)*(self.lists[K-R].rev)*(self.lists[R].rev))%self.mod
        
c=Combi(N,mod)
for i in range(M):
    ans-=c.combi(N,i)*pow(25,N-i,mod)
    ans%=mod
print(ans)


### FIXED CODE ###

K=int(input())
S=input()
M=len(S)
N=K+M
mod=10**9+7
ans=pow(26,N,mod)
class Data():
    def __init__(self):
        self.power=1
        self.rev=1     
class Combi():
    def __init__(self,N,mod):
        self.lists=[Data() for _ in range(N+1)]
        self.mod=mod  
        for i in range(2,N+1):
            self.lists[i].power=((self.lists[i-1].power)*i)%self.mod
        self.lists[N].rev=pow(self.lists[N].power,self.mod-2,self.mod)
        for j in range(N,0,-1):
            self.lists[j-1].rev=((self.lists[j].rev)*j)%self.mod

    def combi(self,K,R):
        if K<R:
            return 0
        else:
            return ((self.lists[K].power)*(self.lists[K-R].rev)*(self.lists[R].rev))%self.mod
        
c=Combi(2*10**6,mod)
for i in range(M):
    ans-=c.combi(N,i)*pow(25,N-i,mod)
    ans%=mod
print(ans%mod)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

for i in range(N):
    A_num = A.pop(i)
    print(max(A))
    A.insert(i, A_num)


### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
b = sorted(a)[::-1]
mx = b[0]
mx2 = b[1]

for i in a:
    if i == mx:
        print(mx2)
    else:
        print(mx)
### BUGGY CODE ###

N=int(input())
TT=[]
for _ in range(N):
    w,s,v=list(map(int,input().strip().split(' ')))
    TT+=[(w,s,v)]
TT=sorted(TT,key=lambda X:X[1]+X[0])
dp=[[0]*(10**4+1) for i in range(N)]

#for L in range()
#dp[i][weight]=max(dp[i-1][weight-W[i]]+V[i],dp[i-1][weight]
for i in range(N):
    if i==0:
        dp[0][TT[0][0]]=TT[0][2]
        continue
    
    
    for weight in range(1,10**4+1):
        if TT[i][1]>=weight-TT[i][0] and weight-TT[i][0]>=0:
            dp[i][weight]=max(dp[i-1][weight],dp[i-1][weight-TT[i][0]]+TT[i][2])
        else:
            dp[i][weight]=dp[i-1][weight]
print(max(dp[-1]))

### FIXED CODE ###

N=int(raw_input())
TT=[]
for _ in xrange(N):
    w,s,v=list(map(int,raw_input().strip().split(' ')))
    TT+=[(w,s,v)]
TT=sorted(TT,key=lambda X:X[1]+X[0])
dp=[[0]*(2*10**4+1) for i in xrange(N)]
 
#for L in range()
#dp[i][weight]=max(dp[i-1][weight-W[i]]+V[i],dp[i-1][weight]
for i in xrange(N):
    if i==0:
        dp[0][TT[0][0]]=TT[0][2]
        continue
    
    
    for weight in xrange(1,2*10**4+1):
        if TT[i][1]>=weight-TT[i][0] and weight-TT[i][0]>=0:
            dp[i][weight]=max(dp[i-1][weight],dp[i-1][weight-TT[i][0]]+TT[i][2])
        else:
            dp[i][weight]=dp[i-1][weight]
print(max(dp[-1]))
### BUGGY CODE ###

S=raw_input()
A=[s for s in S]

while True:
    A_new=[]
    i=0
    while i<len(A):
        if i<len(A)-1:
            if A[i]!=A[i+1]:
                i+=2
            else:
                A_new.append(A[i])
                i+=1
        else:
            A_new.append(A[i])
            i+=1
    if A==A_new:
        break
    else:
        A=A_new[:]
print len(S)-len(A)

### FIXED CODE ###

S=raw_input()
A=[]
Ans=0
for i in range(len(S)):
    if len(A)>0:
        if A[-1]!=S[i]:
            A.pop()
            Ans+=2
        else:
            A.append(S[i])
    else:
        A.append(S[i])

print Ans
### BUGGY CODE ###

inp = [input() for i in range(2)]
N = int(inp[0])
A = inp[1].split()
A = [int(i) for i in A]
B = 0
for k in A:
    a = A.count(k)
    B += (a - 1) / 2

for k in range(N):
    c = A.count(A[k]) - 1
    counter = B - c
    print(int(counter))


### FIXED CODE ###

import math
inp = [input() for i in range(2)]
N = int(inp[0])
A = list(map(int, inp[1].split()))
# B = 0
d = {}
for k in A:
    # a = A.count(k)
    # B += (a - 1) / 2
    if k in d.keys():
        d[k] += 1
    else:
        d[k] = 1

# for k in range(N):
#     c = A.count(A[k]) - 1
#     counter = B - c
#     print(int(counter))

p = {}
for k in d.keys():
    cnt = d[k]
    p[k] = cnt * (cnt-1) / 2

total = sum(p.values())

for item in A:
    print(int(total - d[item] + 1))
### BUGGY CODE ###

def topological_sort(V, to):
    cnt = [0]*V
    s = []
    for i in range(V):
        for j in to[i]:
            cnt[j] += 1
    Q = [i for i in range(V) if cnt[i]==0]
    while len(Q) > 0:
        i = Q[0]
        del Q[0]
        s.append(i)
        for k in to[i]:
            cnt[k] -= 1
            if cnt[k] == 0:
                Q.append(k)
    return s

N,M = map(int,input().split())
to = [[] for i in range(N)]
From = [[] for i in range(N)]
for i in range(N-1+M):
    x, y = list(map(int,input().split()))
    to[x-1].append(y-1)
    From[y-1].append(x-1)
s = topological_sort(N, to)
s = [(s[i],i) for i in range(N)]
s.sort()
for i in range(N):
    k = -1
    I = -1
    for j in From[i]:
        if k < s[j][1]:
            k = s[j][1]
            I = j
    print(I+1)

### FIXED CODE ###

from collections import deque

def topological_sort(V, to):
    cnt = [0]*V
    for i in range(V):
        for j in to[i]:
            cnt[j] += 1
    Q = deque(i for i in range(V) if cnt[i]==0)
    res = []
    while Q:
        i = Q.popleft()
        res.append(i)
        for k in to[i]:
            cnt[k] -= 1
            if cnt[k] == 0:
                Q.append(k)
    return res

N,M = map(int,input().split())
to = [[] for i in range(N)]
From = [[] for i in range(N)]
for i in range(N-1+M):
    x, y = list(map(int,input().split()))
    to[x-1].append(y-1)
    From[y-1].append(x-1)
s = topological_sort(N, to)
s = [(s[i],i) for i in range(N)]
s.sort()
for i in range(N):
    k = -1
    I = -1
    for j in From[i]:
        if k < s[j][1]:
            k = s[j][1]
            I = j
    print(I+1)
### BUGGY CODE ###

def main():
    N = int(input())
    S = [sorted(input()) for i in range(N)]
    ans = 0
    for i in range(N):
        for j in range(i + 1, N):
            if S[i] == S[j]:
                ans += 1

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import collections
import math


def main():
    N = int(input())
    S = ["".join(sorted(input())) for i in range(N)]
    cnt = collections.Counter(S)
    ans = 0
    for v in cnt.values():
        if v != 1:
            ans += math.factorial(v) // (math.factorial(v - 2) * 2)

    print(ans)


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

#!/usr/bin/env python3
#n,p = map(int,input().split())
s = input()
p = 2019
n = len(s)
u_i = []
ans = 0
amari = [0]*p
amari[0] += 1
for i in range(n):
    amari[int(s[i:])%p] += 1

for i in amari:
    ans+= i*(i-1)//2
print(ans)


### FIXED CODE ###

p = 2019
s = input()
n = len(s)
l = [0 for i in range(p)]
l[0] = 1
ten = 1
cnt = 0
 
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i+1
else:
    for i in range(n):
        cnt = (cnt + int(s[-i-1]) * ten) % p
        l[cnt] += 1
        ten = (ten * 10) % p
    for i in l:
        if i > 1:
            ans += i * (i - 1) // 2
print(ans)
### BUGGY CODE ###

def main():
    item_count, capacity = [int(x) for x in input().split()]
    weights, values = [], []
    for _ in range(item_count):
        w, v = [int(x) for x in input().split()]
        weights.append(w)
        values.append(v)
    # dp[i][j]
    # = (i番目までの品物を、重さがj以下になるように選んだときの価値の最大値)
    dp = [[0] * (capacity + 1) for _ in range(item_count)]
    for item_i in range(item_count):
        for weight_i in range(1, capacity + 1):
            if (w := weights[item_i]) <= weight_i:
                dp[item_i][weight_i] = max(
                    dp[item_i - 1][weight_i - w] + values[item_i],
                    dp[item_i - 1][weight_i])
            else:
                dp[item_i][weight_i] = dp[item_i - 1][weight_i]
    print(dp[item_count - 1][capacity])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    item_count, capacity = [int(x) for x in input().split()]
    weights, values = [], []
    for _ in range(item_count):
        w, v = [int(x) for x in input().split()]
        weights.append(w)
        values.append(v)
    # dp[i][j]
    # = (i番目までの品物を、重さがj以下になるように選んだときの価値の最大値)
    dp = [[0] * (capacity + 1) for _ in range(item_count)]
    for item_i in range(item_count):
        for weight_i in range(1, capacity + 1):
            w = weights[item_i]
            if w <= weight_i:
                dp[item_i][weight_i] = max(
                    dp[item_i - 1][weight_i - w] + values[item_i],
                    dp[item_i - 1][weight_i])
            else:
                dp[item_i][weight_i] = dp[item_i - 1][weight_i]
    print(dp[item_count - 1][capacity])


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

import numpy

H, W = map(int,input().split())

board = []

for l in range(H):
    line = list(map(int,input().split()))
    board.append(line)

board = numpy.reshape(board,(H,W))

trajectory = numpy.array([[i, j] if i % 2 == 0 else [i, W - 1 - j] for i in range(H) for j in range(W)])

move = []

for index in range(len(trajectory) - 1):
    i, j = trajectory[index]
    ni, nj = trajectory[index + 1]
    
    if board[i][j] %2 == 1 and index < len(trajectory):
        board[i][j] += -1
        board[ni][nj] += 1
        move.append([i+1,j+1,ni+1,nj+1])
        
print(len(move))
for m in move:
    print(*m)

### FIXED CODE ###

import numpy

H, W = map(int,input().split())
board = [list(map(int,input().split())) for l in range(H)]

board = numpy.reshape(board,(H,W))
cboard = board.copy()

move = []

for i in range(H):
    for j in range(W-1):
        if board[i,j] % 2 == 1:
            board[i,j+1] += 1
            board[i,j] += -1
            move.append([i+1,j+1,i+1,j+2])
            
for i in range(H-1):
    if board[i,W-1] % 2 == 1:
        board[i,W-1] += -1
        board[i+1,W-1] +=1
        move.append([i+1,W,i+2,W])
        
print(len(move))
for m in move:
    print(*m)
### BUGGY CODE ###

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

BC = []
for _ in range(M):
    b, c = map(int, input().split())
    BC.append((b, c))
    
cards = A[:]
cards  =sorted(cards)

opes = BC[:]
opes = sorted(opes, reverse=True, key=lambda x: x[1])

#print(cards)
#print(opes)

top_list = []
for b, c in opes:
    top_list += [c] * b
top_list += [0] * N
    
#print(cards)
#print(top_list)

ans = 0
for x, y in zip(cards, top_list[:N]):
    ans += max(x, y)

print(ans)
    

            


### FIXED CODE ###

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

BC = []
for _ in range(M):
    b, c = map(int, input().split())
    BC.append((b, c))
    
cards = A[:]
opes = BC[:]

cards_dict = {}

for c in cards:
    if c in cards_dict:
        cards_dict[c] += 1
    else:
        cards_dict[c] = 1

for b, c in opes:
    if c in cards_dict:
        cards_dict[c] += b
    else:
        cards_dict[c] = b
        
cards_dict = sorted(cards_dict.items(), reverse=True)
#print(cards_dict)

num = 0
ans = 0
for k, v in cards_dict:
    if num + v > N:
        ans += k * (N-num)
        num = N
    else:
        ans +=  k * v
        num += v
    if num == N:
        break
        
print(ans)
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
for i in range(Q):
    l,r = map(int,input().split())
    print(S[l-1:r].count('AC'))

### FIXED CODE ###

import bisect

N,Q = map(int,input().split())
S = input()
L = []
for i in range(N):
    if S[i:i+2] == 'AC':
        L.append(i)
for i in range(Q):
    l,r = map(int,input().split())
    a = bisect.bisect_left(L,l-1)
    b = bisect.bisect_right(L,r-2)
    print(b-a)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from collections import deque
def solve(N,A):
    ans = 0
    lis = []
    for i in range(N):
        ind = bisect_left(lis,A[i])
        if ind == 0:
            lis.insert(0,A[i])
        else:
            lis[ind-1] = A[i]
    ans = len(lis)
    return ans
print(solve(N,A))

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort

def solve(N,A):
    ans = 0
    lis = []
    for i in range(N):
        ind = bisect_right(lis,-A[i])
        if ind == len(lis):
            lis.append(-A[i])
        else:
            lis[ind] = -A[i]
    ans = len(lis)
    return ans
print(solve(N,A))
### BUGGY CODE ###

N = int(input())
S = input()


def main():
    def search(s, t):
        if len(t) > len(s):
            return 0
        for i in range(len(s) - len(t) + 1):
            if s[i:i + len(t)] == t:
                return 1
        return 0

    ans = 0
    for i in range(1, N):
        S1 = S[:i]
        S2 = S[i:]
        ok = 0
        ng = len(S2) + 1
        k = (ok + ng) // 2
        while ng - ok > 1:
            if search(S1, S2[:k]):
                ok = k
                k = (k + ng) // 2
            else:
                ng = k
                k = (k + ok) // 2
        ans = max(ans, k)
        if ans > N - i - 1:
            break
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict

N = int(input())
S = input()
mod1 = 10 ** 9 + 7
mod2 = 10 ** 9 + 9
base1 = 1007
base2 = 2009

ok = 0
ng = N // 2 + 1
mid = (ok + ng) // 2
while ng - ok > 1:
    seen1 = defaultdict(lambda: 10 ** 5)
    seen2 = defaultdict(lambda: 10 ** 5)
    rh1 = 0
    rh2 = 0
    for i in range(mid):
        rh1 += ord(S[i]) * pow(base1, mid - i - 1, mod1)
        rh2 += ord(S[i]) * pow(base2, mid - i - 1, mod2)
        rh1 %= mod1
        rh2 %= mod2
    seen1[rh1] = 0
    seen2[rh2] = 0
    flag = 0
    for i in range(1, N - mid + 1):
        if flag == 1:
            break
        rh1 = (rh1 * base1 + ord(S[i + mid - 1]) - ord(S[i - 1]) * pow(base1, mid, mod1)) % mod1
        rh2 = (rh2 * base2 + ord(S[i + mid - 1]) - ord(S[i - 1]) * pow(base2, mid, mod2)) % mod2
        if i - seen1[rh1] >= mid and i - seen2[rh2] >= mid:
            ok = mid
            mid = (ok + ng) // 2
            flag = 1
        else:
            if seen1[rh1] == 10 ** 5:
                seen1[rh1] = i
            if seen2[rh2] == 10 ** 5:
                seen2[rh2] = i
    if flag == 0:
        ng = mid
        mid = (ok + ng) // 2

print(ok)