Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from scipy.sparse.csgraph import floyd_warshall
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations, combinations_with_replacement
from heapq import heappop, heappush, heapify
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    n = int(input())
    ans = [0 for _ in range(n)]
    for x in range(1,n):
        for y in range(1,n):
            for z in range(1,n):
                if x*x+y*y+z*z+x*y+y*z+x*z-1 >= n+1:
                    break
                ans[x*x+y*y+z*z+x*y+y*z+x*z-1] += 1
    for i in range(n):
        print(ans[i])
if __name__ == "__main__":
    main()

Fixed submission:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from scipy.sparse.csgraph import floyd_warshall
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations, combinations_with_replacement
from heapq import heappop, heappush, heapify
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    n = int(input())
    ans = [0 for _ in range(n)]
    for x in range(1,n):
        for y in range(1,n):
            for z in range(1,n):
                if x*x+y*y+z*z+x*y+y*z+x*z >= n+1:
                    break
                ans[x*x+y*y+z*z+x*y+y*z+x*z-1] += 1
    for i in range(n):
        print(ans[i])
if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from scipy.sparse.csgraph import floyd_warshall
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations, combinations_with_replacement
from heapq import heappop, heappush, heapify
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    ans = 1000-int(int(input())%1000)
    if ans == 1000:
        print(0)
    else:
        print(ans)
if __name__ == "__main__":1
    main()

Fixed submission:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from scipy.sparse.csgraph import floyd_warshall
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations, combinations_with_replacement
from heapq import heappop, heappush, heapify
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    ans = 1000-int(int(input())%1000)
    if ans == 1000:
        print(0)
    else:
        print(ans)
if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
n=int(input())
ans=n*(n+1)*(n+2)//6
for i in range(n-1):
    u=map(int,input().split())
    ans-=min(u)*(n-max(u)+1)
print(ans)

Fixed submission:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from scipy.sparse.csgraph import floyd_warshall
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations, combinations_with_replacement
from heapq import heappop, heappush, heapify
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    n = int(input())
    ans = n*(n+1)*(n+2)//6
    for i in range(n-1):
        u,v = map(int,input().split())
        if u > v:
            u,v = v,u
        ans -= (u)*(n-v+1)
    print(ans)
    
if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input()) # n=1
def inpm(): return map(int,input().split()) # x=1,y=2
def inpl(): return list(map(int, input().split())) # a=[1,2,3,4,5,...,n]
def inpls(): return list(input().split())  # a=['1','2','3',...,'n']
def inplm(n): return list(int(input()) for _ in range(n)) # x=[] 複数行
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return sorted([list(map(int, input().split())) for _ in range(n)]) # [[1,1,1,1],[2,2,2,2],[3,3,3,3]] 

def main():
    N = inp()
    n = []
    while N > 0:
        n.append(N%10)
        N //= 10
    l = len(n)
    ans = 0
    for i in range(l):
        if n[i] == 10:
            n[i+1] += 1
            n[i] = 0
        if n[i] == 0:
            continue
        if n[i] <= 4:
            ans += n[i]
        elif n[i] == 5 and (i == l-1 or n[i+1] <= 4):
            ans += n[i]
        else:
            ans += 10 - n[i]
            n[i] = 0
            n[i+1] += 1
        if i == l-1:
            if n[i] == 0:
                ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input()) # n=1
def inpm(): return map(int,input().split()) # x=1,y=2
def inpl(): return list(map(int, input().split())) # a=[1,2,3,4,5,...,n]
def inpls(): return list(input().split())  # a=['1','2','3',...,'n']
def inplm(n): return list(int(input()) for _ in range(n)) # x=[] 複数行
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return sorted([list(map(int, input().split())) for _ in range(n)]) # [[1,1,1,1],[2,2,2,2],[3,3,3,3]] 

def main():
    n = list(input())
    l = len(n)
    ans = 0
    for i in range(l):
        n[i] = int(n[i])
    for i in range(l-1,-1,-1):
        if n[i] <= 4:
            ans += n[i]
        elif n[i] == 5 and (i == 0 or n[i-1] <= 4):
            ans += n[i]
        else:
            ans += 10 - n[i]
            n[i] = 0
            if i != 0:
                n[i-1] += 1
        if i == 0 and n[i] == 0:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
l = list(map(int,input().split()))	
l.sort()
ans=0
if l[0]+l[1]>l[n-1]:
    print((n*(n-1)*(n-2))//6)
    exit()
else:
    for i in range(n-2):
        for j in range(n-i-2):
            j+=i+1
            if l[i]+l[j]>l[n-1]:
                ans+=((n-j-1)*(n-j))//2
                break
            for k in range(n-j-1):
                k+=j+1
                if l[i]+l[j]>l[k]:
                    ans+=1
                else:
                    break
print(ans)


Fixed submission:
def main():
    n = int(input())
    l = list(map(int,input().split()))
    l.sort()
    l.append(10**7)
    ans=0

    for i in range(n-2):
        for j in range(i+1,n-1):
            ok=j
            ng=n
            while ng-ok>1:
                mid = (ok + ng)//2
                if l[mid] < l[i] + l[j]:
                    ok=mid
                else:
                    ng=mid  
            ans+=ok-j
            
    print(ans)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
l = list(map(int,input().split()))	
l.sort()
ans=0
if l[0]+l[1]>l[n-1]:
    print((n*(n-1)*(n-2))//6)
    exit()
else:
    for i in range(n-2):
        for j in range(n-i-2):
            j+=i+1
            for k in range(n-j-1):
                k+=j+1
                if l[i]+l[j]>l[k]:
                    ans+=1
                else:
                    break
print(ans)


Fixed submission:
def main():
    n = int(input())
    l = list(map(int,input().split()))
    l.sort()
    l.append(10**7)
    ans=0

    for i in range(n-2):
        for j in range(i+1,n-1):
            ok=j
            ng=n
            while ng-ok>1:
                mid = (ok + ng)//2
                if l[mid] < l[i] + l[j]:
                    ok=mid
                else:
                    ng=mid  
            ans+=ok-j
            
    print(ans)

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
#import math
#import copy
#import sys
#import bisect
#input = sys.stdin.readline
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
def lcm(a, b):
    return((a*b)//gcd(a,b))
def div(x):#約数配列
    div=[1]
    check=2
    while(x!=1 and check <= int(x**0.5)+2):
        if(x%check==0):
            div.append(check)
            while(x%check==0):
                x=x//check
        check+=1
    if x != 1:
      div.append(x)
    return div
def div2(x):#素因数分解配列
    div2=[]
    check=2
    while(x!=1 and check <= int(x**0.5)+2):
        while x%check==0:
            div2.append(check)
            x/=check
        check+=1
    if x != 1:
      div2.append(x)
    return div2

def main():
    #x,y = map(int,input().split())           x=1,y=2
    #a = input().split()                      a=['1','2','3',...,'n']
    #a = list(map(int,input().split()))       a=[1,2,3,4,5,...,n]
    #li = input().split('T')	              FFFTFTTFF => li=['FFF', 'F', '', 'FF']
    #複数行の「1 2 3 4」型の入力を一配列に
    #x = sorted([list(map(int, input().split())) for _ in range(n)])
    #ソート x.sort(key=lambda y:y[1])
    # print("Yes")  print("No")  x=[[0 for _ in range(n)] for _ in range(n)]
    s=list(input())
    k=int(input())
    index=cnt=key=0
    while index<len(s)-1:
        if s[index]==s[index+1]:
            cnt+=1
            index+=2
        else:
            index+=1
    if s[0]==s[len(s)-1]:
        if s[0]==s[1] or s[len(s)-2]==s[len(s)-1]:
            key=0
        else:
            key=1
    print(cnt*k+key*(k-1))



main()

Fixed submission:
def main():
    s=list(input())
    k=int(input())
    n=len(s)

    ans=cnt=key=0
    for i in range(n-1):
        if key==0 and s[i]==s[i+1]:
            cnt+=1
            key=1
        elif key==1 and s[i]==s[i+1]:
            key=0
        else:
            key=0
    ans=cnt*k
    a=b=1
    for i in range(n-1):
        if s[i]==s[i+1]:
            a+=1
        else:
            break
    for i in range(n-1):
        if s[n-1-i]==s[n-2-i]:
            b+=1
        else:
            break
    if a!=n and s[0]==s[n-1]:
        ans+=(((a+b)//2)-(a//2)-(b//2))*(k-1)
    if a==n:
        if n%2==0:
            print(cnt*k)
            return
        else:
            print((n*k)//2)
            return
    print(ans)
main()
Buggy python submission (verdict: Time Limit Exceeded):
def yakusu(x):
    ans=[1]
    check=2
    while(x!=1):
        if(x%check==0):
            ans+=[check]
            while(x%check==0):
                x=x//check
        check+=1  
    return ans
def main():
    a,b = map(int,input().split())	
    ans=0
    y1=yakusu(a)
    for i in y1:
        if b%i==0:
            ans+=1
    print(ans)

main()



Fixed submission:
def yakusu(x):
    ans=[1]
    check=2
    while(x!=1 and check <= int(x**0.5)+2):
        if(x%check==0):
            ans.append(check)
            while(x%check==0):
                x=x//check
        check+=1
    if x != 1:
      ans.append(x)
    return ans
def main():
    a,b = map(int,input().split())	
    ans=0
    y1=yakusu(a)
    for i in y1:
        if b%i==0:
            ans+=1
    print(ans)
 
main()

Buggy python submission (verdict: Time Limit Exceeded):
a,b = map(int,input().split())	
ko=[]
for i in range(min(a,b)):
    i+=1
    if(a%i==0 and b%i==0):
        ko+=[i]
for i in range(len(ko)):
    for j in range(ko[i]//2):
        j+=2
        if ko[i]!=2 and ko[i]%j==0:
            ko[i]=0
            break
ans=0
for i in range(len(ko)):
    if ko[i]!=0:
        ans+=1
print(ans)

Fixed submission:
def yakusu(x):
    ans=[1]
    check=2
    while(x!=1 and check <= int(x**0.5)+2):
        if(x%check==0):
            ans.append(check)
            while(x%check==0):
                x=x//check
        check+=1
    if x != 1:
      ans.append(x)
    return ans
def main():
    a,b = map(int,input().split())	
    ans=0
    y1=yakusu(a)
    for i in y1:
        if b%i==0:
            ans+=1
    print(ans)
 
main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
def main():
    n,m = map(int,input().split())
    dp = [[10**10 for _ in range(2**n)] for _ in range(m+1)]
    dp[0][0] = 0
    for i in range(m):
        a,b = map(int,input().split())
        c = list(map(int,input().split()))
        S = 0
        for j in range(b):
            x = pow(2,c[j]-1)
            S |= x
        for j in range(2**n):
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])
        for j in range(2**n):
            dp[i+1][j|S] = min(dp[i+1][j|S],dp[i][j]+a)
    if dp[m][2**n-1] == 10**10:
        print(-1)
    else:
        print(dp[m][2**n-1])

if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.readline
def main():
    n,m = map(int,input().split())
    dp = [[10**10 for _ in range(2**n)] for _ in range(m+1)]
    dp[0][0] = 0
    for i in range(m):
        a,b = map(int,input().split())
        c = list(map(int,input().split()))
        S = 0
        for j in range(b):
            x = pow(2,c[j]-1)
            S |= x
        for j in range(2**n):
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])
        for j in range(2**n):
            dp[i+1][j|S] = min(dp[i+1][j|S],dp[i][j]+a)
    if dp[m][2**n-1] == 10**10:
        print(-1)
    else:
        print(dp[m][2**n-1])

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n,m = map(int,input().split())
    dp = [[10**10 for _ in range(2**n)] for _ in range(m+1)]
    dp[0][0] = 0
    for i in range(m):
        a,b = map(int,input().split())
        c = list(map(int,input().split()))
        S = 0
        for j in range(b):
            x = pow(2,c[j]-1)
            S |= x
        for j in range(2**n):
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])
        for j in range(2**n):
            dp[i+1][j|S] = min(dp[i+1][j|S],dp[i][j]+a)
    if dp[m][2**n-1] == 10**10:
        print(-1)
    else:
        print(dp[m][2**n-1])

if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.readline
def main():
    n,m = map(int,input().split())
    dp = [[10**10 for _ in range(2**n)] for _ in range(m+1)]
    dp[0][0] = 0
    for i in range(m):
        a,b = map(int,input().split())
        c = list(map(int,input().split()))
        S = 0
        for j in range(b):
            x = pow(2,c[j]-1)
            S |= x
        for j in range(2**n):
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])
        for j in range(2**n):
            dp[i+1][j|S] = min(dp[i+1][j|S],dp[i][j]+a)
    if dp[m][2**n-1] == 10**10:
        print(-1)
    else:
        print(dp[m][2**n-1])

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import bisect
input = sys.stdin.readline

def main():
    n,k,q = map(int,input().split())
    a=[int(input()) for _ in range(q)]
    point=[k for i in range(n)]
    for i in range(q):
        for j in range(n):
            if(j!=(a[i]-1) and point[j]>0):
                point[j]-=1
    
    for i in range(n):
        if(point[i]>0):
            print("Yes")
        else:
            print("No")

main()

Fixed submission:
n,k,q = map(int,input().split())
a=[int(input()) for _ in range(q)]
point=[k-q for i in range(n)]
for i in range(q):
    point[a[i]-1]+=1
 
for i in range(n):
    if(point[i]>0):
        print("Yes")
    else:
        print("No")

Buggy python submission (verdict: Time Limit Exceeded):
n,k,q = map(int,input().split())
a=[int(input()) for _ in range(q)]
point=[k for i in range(n)]
for i in range(q):
    for j in range(n):
        if(j!=(a[i]-1)):
            point[j]-=1

for i in range(n):
    if(point[i]>0):
        print("Yes")
    else:
        print("No")






Fixed submission:
n,k,q = map(int,input().split())
a=[int(input()) for _ in range(q)]
point=[k-q for i in range(n)]
for i in range(q):
    point[a[i]-1]+=1
 
for i in range(n):
    if(point[i]>0):
        print("Yes")
    else:
        print("No")
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import bisect
input = sys.stdin.readline
 
def main():
    n,m = map(int,input().split())
    a = list(map(int,input().split()))	
    for i in range(m):
        a.sort()
        a[n-1]=a[n-1]//2
    print(sum(a))


main()

Fixed submission:
import sys
import bisect
input = sys.stdin.readline
 
def main():
    n,m = map(int,input().split())
    a = list(map(int,input().split()))
    cnt=0
    while(cnt<m):
        a.sort()
        a[n-1]=a[n-1]//2
        cnt+=1
        if(cnt==m):
            break
        for i in range(n-1):
            if(a[n-1]<=a[n-i-2]):
                a[n-i-2]=a[n-i-2]//2
                cnt+=1
                if(cnt==m):
                    break
    print(sum(a))


main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n=int(input())
    s=[input() for i in range(n)]
    count=0
    
    for i in range(n):
        s[i]=''.join(sorted(s[i]))
        
        
    for i in range(n-1):
        for j in range(n-i-1):
            if(s[i]==s[i+j+1]):
                count+=1
    
    print(count)
    
main()

Fixed submission:
def main():
    n=int(input())
    s= ["".join(sorted(input())) for i in range(n)]
    check = {}
    ans = 0
    for i in s:
        if i in check:
            ans += check[i]
            check[i] += 1
        else:
            check[i] = 1
            
    print(ans)
    
main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import bisect
input = sys.stdin.readline

def main():
    n=int(input())
    h = list(map(int,input().split()))

    ans="Yes"

    for i in range(n-1):
        b=h[0]
        h.pop(0)
        if(b>=min(h)+2):
            ans="No"
        if(ans=="No"):
            break
        
    print(ans)
    
main()

Fixed submission:
import sys
import bisect
input = sys.stdin.readline

def main():
    n=int(input())
    h = list(map(int,input().split()))

    ans="Yes"
    m=0

    for i in range(n):
        if(m>=h[i]+2):
            ans="No"
        else:
            m=max(m,h[i])
        if(ans=="No"):
            break
        
    print(ans)
    
main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import bisect
input = sys.stdin.readline

def main():
    n=int(input())
    h = list(map(int,input().split()))

    ans="Yes"

    for i in range(n-1):
        a=n-i-1
        for j in range(a):
            if(h[i]>=h[i+j+1]+2):
                ans="No"
            if(ans=="No"):
                break
        if(ans=="No"):
            break
        
    
    print(ans)
    
main()

Fixed submission:
import sys
import bisect
input = sys.stdin.readline

def main():
    n=int(input())
    h = list(map(int,input().split()))

    ans="Yes"
    m=0

    for i in range(n):
        if(m>=h[i]+2):
            ans="No"
        else:
            m=max(m,h[i])
        if(ans=="No"):
            break
        
    print(ans)
    
main()

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
h = list(map(int,input().split()))

ans="Yes"

for i in range(n-1):
    a=n-i-1
    for j in range(a):
        if(h[i]>=h[i+j+1]+2):
            ans="No"

print(ans)

Fixed submission:
import sys
import bisect
input = sys.stdin.readline

def main():
    n=int(input())
    h = list(map(int,input().split()))

    ans="Yes"
    m=0

    for i in range(n):
        if(m>=h[i]+2):
            ans="No"
        else:
            m=max(m,h[i])
        if(ans=="No"):
            break
        
    print(ans)
    
main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import bisect
input = sys.stdin.readline
 
def main():
    n=int(input())
    a=[0 for _ in range(n)]
    for i in range(n):
        a[i]=int(input())
    M=max(a)
    ans=0
    for i in range(n):
        if(a[i]!=M):
            ans=M
        else:
            ans=0
            for j in range(n-1):
                if(j>=i):
                    j+=1
                if(a[j]>ans):
                    ans=a[j]
            
        print(ans)        
main()




Fixed submission:
import sys
import bisect
input = sys.stdin.readline

def main():
    n=int(input())
    a=[0 for _ in range(n)]
    for i in range(n):
        a[i]=int(input())
    M=max(a)
    cnt=0
    ans=0
    S=0
    for i in range(n):
        if(a[i]!=M and a[i]>S):
            S=a[i]
        elif(a[i]==M):
            cnt+=1
    
    for i in range(n):
        if(a[i]!=M or cnt>1):
            ans=M
        else:
            ans=S
        print(ans)        
main()

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=[0 for _ in range(n)]
for i in range(n):
    a[i]=int(input())
M=max(a)
ans=0
for i in range(n):
    if(a[i]!=M):
        ans=M
    else:
        ans=0
        for j in range(n-1):
            if(j>=i):
                j+=1
            ans=max(ans,a[j])
        
    print(ans)        



Fixed submission:
import sys
import bisect
input = sys.stdin.readline

def main():
    n=int(input())
    a=[0 for _ in range(n)]
    for i in range(n):
        a[i]=int(input())
    M=max(a)
    cnt=0
    ans=0
    S=0
    for i in range(n):
        if(a[i]!=M and a[i]>S):
            S=a[i]
        elif(a[i]==M):
            cnt+=1
    
    for i in range(n):
        if(a[i]!=M or cnt>1):
            ans=M
        else:
            ans=S
        print(ans)        
main()
Buggy python submission (verdict: Runtime Error):
import bisect
def LIS(a):
    lis = [a[0]]
    for i in range(len(a)):
        if i != 0 and a[i] >= lis[-1]:
            lis.append(a[i])
        else:
            index = bisect.bisect_right(lis,a[i])
            lis[index] = a[i]
    return len(lis)

def main():
    n = int(input())
    a = [-int(input()) for _ in range(n)]
    print(LIS(a))

if __name__ == "__main__":
    main()

Fixed submission:
import bisect
from collections import deque
def LIS(a):
    lis = deque()
    lis.append(-1)
    for i in range(len(a)):
        index = bisect.bisect_left(lis,a[i])
        if index == 0:
            lis.appendleft(a[i])
        else:
            lis[index-1] = a[i]
    return len(lis)

def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    print(LIS(a))

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter,defaultdict,deque
import sys
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
    
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n=inp()
    a=inplm(n)
    aa=[-1 for _ in range(10**5)]
    index=0
    for i in range(n):
        for j in range(10**5):
            if a[i]>aa[j]:
                aa[j]=a[i]
                if index<j:
                    index=j
                break
    print(index+1)


if __name__ == "__main__":
    main()

Fixed submission:
import bisect
from collections import deque
def LIS(a):
    lis = deque()
    lis.append(-1)
    for i in range(len(a)):
        index = bisect.bisect_left(lis,a[i])
        if index == 0:
            lis.appendleft(a[i])
        else:
            lis[index-1] = a[i]
    return len(lis)

def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    print(LIS(a))

if __name__ == "__main__":
    main()