Harryxun/stf_run huggingface dataset:
from math import ceil
class sqrt_tree:
    def __init__(self,dat,f):
        self.dat = dat
        self.sq = int(len(dat) ** 0.5)
        self.f = f
        self.baqet = [self.f(dat[i * self.sq:(i + 1) * self.sq]) for i in range(self.sq)]
    
    #query
    def q(self,l,r):
        r += 1
        if ceil(l / self.sq) >= r // self.sq:
            return self.f(self.dat[l:r])
        ret = self.f(self.baqet[ceil(l / self.sq):r // self.sq])
        if l % self.sq:
            ret = self.f(ret,self.f(self.dat[l:l + self.sq]))
        if r % self.sq:
            ret = self.f(ret,self.f(self.dat[r - r % self.sq:r]))
        return ret

import sys
f = sys.stdin

_, d = map(int, f.readline().split())

x,y = {},{}
for line in f:
    xi, yi, bi = map(int, line.split())
    if bi not in x:
        x[bi],y[bi] = [],[]
    x[bi].append(xi)
    y[bi].append(yi)

b = sorted(x.keys())

xmax = sqrt_tree([max(x[bi]) for bi in b],max)
xmin = sqrt_tree([min(x[bi]) for bi in b],min)
ymax = sqrt_tree([max(y[bi]) for bi in b],max)
ymin = sqrt_tree([min(y[bi]) for bi in b],min)

def get_lr(b,d):
    l = r = 0
    while r < len(b) - 1:
        for k in range(r,-1,-1):
            if b[k] + d < b[r]:
                break
            l = k
        for k in range(l,len(b)):
            if b[l] + d < b[k]:
                break
            r = k
        yield l,r
        r += 1
   
max_size = max((xmax.q(l,r) - xmin.q(l,r)) * (ymax.q(l,r) - ymin.q(l,r)) for l,r in get_lr(b,d))
print(max_size)

### FIXED CODE ###

import math
def segmentTree(dat, f, sentinel):
        pad = 2 ** math.ceil(math.log(len(dat),2))
        dat = [0] * pad + dat + [sentinel] * (pad - len(dat))
        for i in range(pad - 1, 0, -1):
            dat[i] = f(dat[i * 2],dat[i * 2 + 1])
        return dat

def get_lr(b,d):
    l = r = 0
    while r < len(b):
        while b[l] + d < b[r]:
            l += 1
        for r in range(r,len(b)):
            if b[l] + d < b[r]:
                r -= 1
                break
        r += 1
        yield l,r
        l += 1
    
import sys
f = sys.stdin

_, d = map(int, f.readline().split())

xyb = []
for line in f:
    xyb.append(tuple(map(int, line.split())))
from operator import itemgetter
xyb.sort(key=itemgetter(2))

x = [xybi[0] for xybi in xyb]
y = [xybi[1] for xybi in xyb]
b = [xybi[2] for xybi in xyb]

xmax = segmentTree(x,max,sentinel = 0)
xmin = segmentTree(x,min,sentinel = 2000000)
ymax = segmentTree(y,max,sentinel = 0)
ymin = segmentTree(y,min,sentinel = 2000000)


pad = len(xmax) // 2
max_size = 0
def create_index(l,r):
    index = []
    ia = index.append
    while l < r:
        if r & 1:
            r -= 1
            ia(r)
        if l & 1:
            ia(l)
            l += 1
        l >>= 1
        r >>= 1
    return index

for l,r in get_lr(b,d):
    l += pad 
    r += pad
    index = create_index(l,r)

    now_xmax = max(xmax[i] for i in index)
    now_ymax = max(ymax[i] for i in index)
    if max_size < now_xmax * now_ymax:
        max_size = max(max_size,((now_xmax - min(xmin[i] for i in index)) * (now_ymax - min(ymin[i] for i in index))))
print(max_size)
n,a,b = map(int,input().split())

print(max(b*(n-1)+a-(a*(n-1)+b)+1),0)

### FIXED CODE ###

from sys import stdin
n,a,b = [int(x) for x in stdin.readline().rstrip().split()]

saisyou = a*(n-1)+b
saidai = b*(n-1)+a

if n == 1 and a!= b:
    print(0)
    exit()
elif a > b:
    print(0)
    exit()
else:
    print(saidai-saisyou+1)
a,b=map(int,input().split())
n=b-a
print(int(n*(n+1)/2-b))

### FIXED CODE ###

n = int(input())
if n > 999:
    print("ABD")
    exit()
print("ABC")
L,R = map(int,input().split())
a = []
b = []
if R - L >= 2018:
  print("0")
else:
  for i in range (0,R-L+1):
    d = (L + i) % 2019
    a.append(d)
  for i in range (0,R-L+1):
    for j in range (i+1,R-L+1):
      x = (a[i] * a[j]) % 2019
      b.append(x)
print(min(b))

### FIXED CODE ###

L, R = map(int,input().split())
b = 2018
if R - L >= 2019:
  print(0)
else:
  L = L % 2019
  R = R % 2019
  for i in range(L, R):
    for j in range(i + 1, R + 1):
      if b > (i * j) % 2019:
        b = (i * j) % 2019
  print(b)
n,k=map(int,input().split())
if k=1:
 print("0")
else:
print(n-k) 

### FIXED CODE ###

n,k=map(int,input().split())
if k==1:
	print("0")
else:
	print(n-k)
x=intput()
if x=='ABC':
    print("ARC")
else:
    print("ABC")


### FIXED CODE ###

x=input()
if x=='ABC':
    print("ARC")
else:
    print("ABC")
import math
A, B = 3, 4
lcm = A//math.gcd(A, B)*B

print(lcm)

### FIXED CODE ###

import fractions
A,B=map(int,input().split())
print(A*B//fractions.gcd(A,B))
K,X = map(int,input().split())

for i in range(X-(K-1),X+(K+1)):
  print(i + " ")

### FIXED CODE ###

K,X = map(int,input().split())
for i in range(X-(K-1),X+K):
  print(str(i) + " ")
a,b =map(int,input().split())
c = 1
for i in range(a-1):
  if (b-2*i)%4==0:
    c = 0
    break
if c ==1:
  print("No")
else:
  print("Yes")


### FIXED CODE ###

x = list(map(int,input().split()))
print (x.index(0)+1)
s = input()
w = list("keyence")

st = ""
i_w = 0
delete = []

for i in s:
    if i == w[i_w]:
        i_w += 1
        if not st == "":
            delete.append(st)
            st = ""
    else:
        st += i
else:
    if not st == "":
        delete.append(st)

if i_w == 7 and len(delete) <= 1:
    ans = "YES"
else:
    ans = "NO"
print(ans)


### FIXED CODE ###

s = input()

w = "keyence"
ans = "NO"

# keyencexxxxx
if s[:7] == w:
    ans = "YES"

# xxxxkeyence
if s[-7:] == w:
    ans = "YES"

# key xxx ence
for i in range(1, 7):
    ss = w[:i]
    tt = w[-7+i:]
    if s[: len(ss)] == ss and s[-len(tt):] == tt:
        ans = "YES"
        break

print(ans)
def Treemake(node,parent,root,num):
    A.append([node,parent,root,num])
    for i,j in root:
        Treemake(i,node,Tree[i],j)


n=int(input())
AB=[list(map(int,input().split()))+[i+1] for i in range(n-1)]
Tree=[[] for _ in range(n)]
A=[]
for a,b,c in AB:
    Tree[a-1].append([b-1,c])
Treemake(0,-1,Tree[0],0)

color=[0]*n
for node,parent,root,num in A:
    flag=0
    for i,j in enumerate(root):
        i=i+1
        if color[num]==i:flag=1
        color[j[1]]=i+flag

print(max(color))
for i in range(1,n):
    print(color[i])

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)


def rootedTree(node,parent,root,add):
    A.append([node,parent,root,add])
    for root_num,num in root:
        if len(tree[root_num])!=0:
            rootedTree(root_num,node,tree[root_num],num)
        else:
            A.append([root_num,node,tree[root_num],num])


n=int(input())
AB=[list(map(int,input().split()))+[i+1] for i in range(n-1)]
A=[]
tree=[[] for i in range(n+1)]
for a,b,c in AB:
    tree[a] +=[[b,c]]

rootedTree(1,0,tree[1],0)
ans=[0]*n
for node,parent,root,num in A:
    flag=0
    for i,j in enumerate(root):
        if ans[num]==i+1:flag=1
        if flag:
            ans[j[1]]=i+2
            continue
        ans[j[1]]=i+1

print(max(ans))
for i in range(1,n):print(ans[i])
r=map(int,raw_input().split())
print ('%f %f' (float(2*M_PI*r),float(r*r*M_PI))

### FIXED CODE ###

import math
r = float(raw_input())
print "%f %f" % (math.pi* r*r, math.pi*r*2)
INF =10001
N = int(input())
K = 2
h = [int(i) for i in input().split()]
i = 2
dp = [INF for i in range(N)]
dp[0],dp[1] = 0,abs(h[1]-h[0])
 
while not i==N:
	l = min(len(dp[:i]),K)
    dp[i] = min([dp[i-j]+abs(h[i] - h[i-j]) for j in range(1,l)])
    i+=1
    
print(dp[N-1])

### FIXED CODE ###

INF =10001
N = int(input())
h = [int(i) for i in input().split()]
i = 2
dp = [INF for i in range(N)]
dp[0],dp[1] = 0,abs(h[1]-h[0])

while not i==N:
    dp[i] = min(dp[i-2]+abs(h[i] - h[i-2]),dp[i-1]+abs(h[i] - h[i-1]))
    i+=1
    
print(dp[N-1])
N = int(input())
A = sorted(map(int,input().split()),reverse = True)
answer = 0
i = 1
s = 0
answer = A[0]
while True:
    s = i-(i-1)%2
    answer += A[s]
    #print(i,s)
    i += 1
    if i == N-1:
        break
    
print(answer)

### FIXED CODE ###

N = int(input())
A = sorted(map(int,input().split()),reverse = True)
answer = 0
i = 1
s = 0
answer = A[0]
if N == 2:
    anwer=A[0]
else:
    while True:
        s = (i+1)//2
        answer += A[s]
        i += 1
        if i == N-1:
            break
    
print(answer)
# (10-x) ways: (0,x)-(9-x,9) -> (-x, x)
# (x) ways:    (10-x,0)-(9,x-1) -> (10-x, -10 + x)

def solve(D):
  leading_zeros = 0
  while D[-1] == 0:
    D.pop()
    leading_zeros += 1

  if len(D) >= 2:
    h,t = D.popleft(), D.pop()
    c = h + t

    if not D:
      r = t - (leading_zeros == 0) if c == 9 else 0
    elif 9 <= c <= 10:
      r = t - (leading_zeros == 0)
      c -= 10
      D[0] += c*10
      D[-1] += 1
      i = len(D)-1
      while i > 0 and D[i] == 10:
        D[i] = 0
        D[i-1] += 1
        i -= 1

  while len(D) > 1:
    h,t = D.popleft(), D.pop()
    c = h + t

    if -1 <= c <= 0:
      r *= 10-t
      D[0] += c*10
    elif 9 <= c <= 10:
      r *= t
      c -= 10
      D[0] += c*10
      D[-1] += 1
      i = len(D)-1
      while i > 0 and D[i] == 10:
        D[i] = 0
        D[i-1] += 1
        i -= 1
    else:
      r = 0
      D.clear()

  if len(D) == 1:
    r *= 10 if D[0] == 0 else 0

  if r != 0 and leading_zeros > 0:
    r *= 9
    r = str(r)+'0'*(leading_zeros-1)

  return r


from collections import deque

D = deque(map(int,input()))
print(solve(D))

### FIXED CODE ###

# (10-x) ways: (0,x)-(9-x,9) -> (x, -x)           <- This should never happens when D > 0
# (x) ways:    (10-x,0)-(9,x-1) -> (x-10, 10 - x)

def solve(d, k, outer):
  if k <= 1:
    return 10**k if d == 0 else 0
  # if d >= 10**k:
  #   return 0

  t = (-d)%10 # 10-d%10 doesn't work when d = 10
  d -= t*10**(k-1) - t
  return (10-t-outer)*solve(abs(d//10), k-2, 0)

D = int(input())
result = 0
for k in range(1,20):
  result += solve(D, k, 1)

print(result)
N = int(input())

A = int(input().split())

b = sum(reverse(a)) for a in A

print(sum(severse(b)))

### FIXED CODE ###

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

A = [1/a for a in A]

print(1/sum(A))
A, V = map(int, input().split())
B, W = map(int, input().split())
T = int(input())

if V <= W:
    print("NO")
    exit()

s = V - W
if D < s * T:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

A, V = map(int, input().split())
B, W = map(int, input().split())
T = int(input())

if V <= W:
    print("NO")
    exit()

d = abs(A - B)
s = V - W

if d <= s * T:
    print("YES")
else:
    print("NO")
import fileinput
import math
for line in fileinput.input():
    a, b = map(int, line.split())
    gcd = math.gcd(a, b)
    lcm = a * b // gcd
    print(gcd, lcm)

### FIXED CODE ###

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

import fileinput
import math
for line in fileinput.input():
    a, b = map(int, line.split())
    g = gcd(a, b)
    lcm = a * b // g
    print(g, lcm)
a,b=map(int,rnput().split())
a+b=c
if c%2==1:
  print("IMPOSSIBLE")
else:
  print(c//2)


### FIXED CODE ###

a,b=map(int,input().split())
if (a+b)%2==1:
  print("IMPOSSIBLE")
else:
  print((a+b)//2)
n = int(input())
s = input()

min_num = n
white_num = s.count('.')
black_num = 0

if white_num == n or s.count('#') == n:
    print(0)
else:
    for i in range(n):
        if s[i] == '#':
            black_num += 1
        else:
            white_num -= 1
        if min_num >= black_num + white_num
            min_num = black_num + white_num
    print(min_num)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
s = list(input())
res = 10**9

cta = 0
ctb = 0
a = [0]*n
b = [0]*n
for i in range(n):
    if s[i] == '.':
        cta += 1
    else:
        ctb += 1
    a[i] = cta
    b[i] = ctb
for i in range(n):
    res = min(res,b[i]+a[-1]-a[i])
res = min(res,a[-1],b[-1])
print(res)
N=int(input())
a=list(map(int,input().split()))
b4=[x for x in a if x%4==0]
a4=[x for x in a if x%4!=0]
b2=[x for x in a4 if x%2==0]
c=[x for x in a4 if x%2!=0]
if len(b4)==0 and (len(c)==0 and len(b2)>1):
    print('Yes')
elif len(b4)==0 and len(c)!=0
    print('No')
elif len(b4)+1<len(c):
    print('No')
elif len(b4)<len(c) and len(b2)>0:
    print('No')
else:
    print('Yes')

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
b4=[x for x in a if x%4==0]
a4=[x for x in a if x%4!=0]
b2=[x for x in a4 if x%2==0]
c=[x for x in a4 if x%2!=0]
if len(b4)==0 and (len(c)==0 and len(b2)>1):
    print('Yes')
elif len(b4)==0 and len(c)!=0:
    print('No')
elif len(b4)+1<len(c):
    print('No')
elif len(b4)<len(c) and len(b2)>0:
    print('No')
else:
    print('Yes')
import math
N, K = map(int, input().split())
#S = list(input())
ans = []
for i in range(1, N+1):
    if i < K:
        ans.append(1/N * (0.5) ** (math.ceil(math.log2(K/i))))
    else:
        ans.append(1/N)
print(sum(ans))

### FIXED CODE ###

import math
N, K = map(int, input().split())
#S = list(input())
ans = []
for i in range(1, N+1):
    if i < K:
        ans.append(1/N * (0.5) ** (math.ceil(math.log2(K/i))))
    else:
        ans.append(1/N)
print(sum(ans))
N=int(input())
count=0
C=[]
for i in range(N):
 if(i!=0):
  a=int(i/2)
  if(i%2==0):
    count +=1
    while(a%2!=1):
     count +=1
     a=int(a/2)
  else:
     count =0
  C.append(count)
b=max(C)
for i inrange(N):
 C[i]==b
 print(i)

### FIXED CODE ###

N = int(input())

if(N<2):
  print(N)
elif(2<=N<4):
  print(2)
elif(4<=N<8):
  print(4)
elif(8<=N<16):
  print(8)
elif(16<=N<32):
  print(16)
elif(32<=N<64):
  print(32)
elif(64<=N):
  print(64)
# -*- coding: utf-8 -*-
a, b = map(int, input().split())
cnt = 0

# 偶数
if a % 2 != 0:
    a = a - 1

# 奇数


# 組み合わせ
nCr = {}

# https://qiita.com/derodero24/items/91b6468e66923a87f39f
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n, r) in nCr: return nCr[(n, r)]
    nCr[(n, r)] = cmb(n - 1, r) + cmb(n - 1, r - 1)
    return nCr[(n, r)]


#
cnt = cnt + cmb(a, 2) + cmb(b, 2)
print(cnt)


### FIXED CODE ###

# -*- coding: utf-8 -*-
a, b = map(int, input().split())
cnt = 0

# 偶数
#if a != 0:
#    if a % 2 != 0:
#        a = a - 1

# 奇数


# 組み合わせ
nCr = {}

# https://qiita.com/derodero24/items/91b6468e66923a87f39f
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n, r) in nCr: return nCr[(n, r)]
    nCr[(n, r)] = cmb(n - 1, r) + cmb(n - 1, r - 1)
    return nCr[(n, r)]


#
if a > 1:
    cnt = cnt + cmb(a, 2)

if b > 1:
    cnt = cnt + cmb(b, 2)
print(cnt)
S = int(input.())

h = S // 3600
m = S // 60 % 60
s = S % 60

print(h + ':' + m + ':' + s)

### FIXED CODE ###

S = int(input())

h = S // 3600
m = S // 60 % 60
s = S % 60

print('{0}:{1}:{2}'.format(h, m, s))
import numpy as np
import sys
buf = sys.stdin.buffer

H,W = map(int,buf.readline().split())
# 周りに壁を、0,1化、壁を0で持つ
grid = np.zeros((H+2,W+2),dtype=np.bool)
grid[1:-1,1:] = (np.frombuffer(buf.read(H*(W+1))+b'\n',dtype='S1') == b'.').reshape((H,W+1))

# x軸方向の集計
def F(transpose):
  x = grid
  if transpose:
    x = (x.T).copy()
  x = np.ravel(x) # to 1D array
  L = len(x)
  
  left_zero = -np.arange(L) # 左の壁のindexの-1倍
  left_zero[x] = 0
  np.minimum.accumulate(left_zero, out=left_zero)
  
  right_zero = np.arange(L) # 逆順ソートした上で左の壁のindex
  right_zero[x[::-1]] = 0
  np.maximum.accumulate(right_zero, out=right_zero)
  
  y = left_zero
  y += L-right_zero[::-1]
  
  return y.reshape(grid.T.shape).T if transpose else y.reshape(grid.shape)
  
answer = (F(False) + F(True)).max()-5
print(answer)


### FIXED CODE ###

import numpy as np

H,W = map(int,input().split())
temp = np.array([list(input()) for _ in range(H)])
# 周りに壁を、0,1化
map = np.zeros((H+2,W+2),dtype=np.int32)
map[1:-1,1:-1][temp == '.'] = 1

# x軸正方向の集計
def F():
  x = map.copy()
  for row in range(1,H+1):
    zero_idx = np.nonzero(x[row]==0)[0]
    x[row, zero_idx[1:]] = 1-np.diff(zero_idx) # cumsumで求められるように変形
  x = x.cumsum(axis = 1)
  return x

# y軸
def G():
  x = map.T.copy()
  for row in range(1,W+1):
    zero_idx = np.nonzero(x[row]==0)[0]
    x[row, zero_idx[1:]] = 1-np.diff(zero_idx) # cumsumで求められるように変形
  x = x.cumsum(axis = 1)
  return x.T

answer = np.zeros_like(map)
# x軸
answer += F()
# 逆順
map = map[:,::-1]
answer += F()[:,::-1]
map = map[:,::-1]

# y軸
answer += G()
# 逆順
map = map[::-1,:]
answer += G()[::-1,:]

answer = np.max(answer) - 3
print(answer)
a, b = (int(x) for x in input().split())

if a % 2 == b % 2:
    print((a + b) / 2)
else:
    print("impossible"

### FIXED CODE ###

a, b = (int(x) for x in input().split())

if a % 2 == b % 2:
    print(int((a + b) / 2))
else:
    print("IMPOSSIBLE")
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
import numpy as np

K, S = MAP()

count = 0

for X in range(0, K+1):
	for Y in range0, (K+1):
		Z = S - X - Y
		if 0 <= Z <= K:
			count += 1
print(count)

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
import numpy as np

K, S = MAP()

cnt = 0

for X in range(K+1):
	for Y in range(K+1):
		Z = S - X - Y
		if 0 <= Z <= K:
			cnt += 1
print(cnt)
#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))
  
n,x,t=input2()
ans=(math.ceil(n/x))*t
print(ans)

### FIXED CODE ###

import math

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))
  
n,x,t=input2()
ans=(math.ceil(n/x))*t
print(ans)
n,ans=int(input()),0
for i in range(n):
  a,b=input().split();a=int(a)
  if b=="JPY":ans+=a
  else:ans+=a*380000
print(ans)

### FIXED CODE ###

n,ans=int(input()),0
for i in range(n):
  a,b=input().split();a=float(a)
  if b=="JPY":ans+=a
  else:ans+=a*380000
print(ans)
import math

N = int(input())
xy_list = [0] * N
for i in range(N):
    xy_list.append(input().split())
result = 0
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        city1 = math.pow(xy_list[i][0] - xy_list[j][0], 2)
        city2 = math.pow(xy_list[i][1] - xy_list[j][1], 2)
        result += math.sqrt(city1 + city2)
print(result / N)


### FIXED CODE ###

import math

N = int(input())
xy_list = []
for i in range(N):
    xy_list.append([int(i) for i in input().split()])
result = 0
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        city1 = math.pow(xy_list[i][0] - xy_list[j][0], 2)
        city2 = math.pow(xy_list[i][1] - xy_list[j][1], 2)
        result += math.sqrt(city1 + city2)
print("{:.10f}".format(result / N))
import sys
import bisect
from collections import deque

fastinput = sys.stdin.readline
N = int(fastinput())
A = [int(fastinput()) for j in range(N)]
surface = deque([A[0]])#常に小さい順にソートされている
color = 1
for n,a in enumerate(A):
    if n==0:
        continue
    else:
        pos = bisect.bisect_left(surface,a) -1 #a未満の最大の整数
        if pos==0:
            color += 1
            surface.appendleft(a)
        else:
            surface[pos-1] = a
print(color)


### FIXED CODE ###

import sys
import bisect
from collections import deque

fastinput = sys.stdin.readline
N = int(fastinput())
A = [int(fastinput()) for j in range(N)]
surface = deque([A[0]])#常に小さい順にソートされている
surfMax = A[0]
surfMin = A[0]
color = 1
for n,a in enumerate(A):
    if n==0:continue

    if color == 1:
        c = surface[0]
        if a>c:
            surface[0] = a
            surfMax = a
            surfMin = a
        if a==c:
            surface.appendleft(a)
            color += 1
        if a<c:
            surface.appendleft(a)
            color += 1
            surfMin = a

    else:    
        if a<=surfMin:
            color += 1
            surface.appendleft(a)
            surfMin = a
        elif a>surfMax:
            surface[color-1] = a
            surfMax = a
        else:
            pos = bisect.bisect_left(surface,a) -1 #a未満の最大の整数
            surface[pos] = a
            if pos==0:
                surfMin = a
            if pos == color-1:
                surfMax = a
print(color)
n, k = map(int, input().split())
dislikes = input().split()

payment = n
while True:
    tmp = str(payment)
    for t in tmp:
        if t in dislikes:
            break
    else:
        break
    payment += 1
print(payment)

### FIXED CODE ###

import itertools

haiku = list(map(int, input().split()))
p = list(itertools.permutations(haiku, 3))
print("YES" if (5, 7, 5) in p else "NO")
S=input()
l=len(S)
num=0
for i in range(l):
  if S[i]==A or S[i]==G or S[i]==C or S[i]==T:
    num+=1
  elif num>ans:
    ans=num
    num=0
  else:
    num=0
print(ans)

### FIXED CODE ###

S = input()

ans = 0
tmp = 0
flag = False

for i in S:
    if (i == "A") or (i == "C") or (i == "G") or (i == "T"):
        tmp += 1
        flag = True
    elif (tmp > ans) and flag:
        ans = tmp
        tmp = 0
        flag = False
    elif flag:
        tmp = 0
        flag = False

if (ans < tmp):
    ans = tmp

print(ans)
A,B = map(int, input().strip())
print(max(0, A-(2*B)))

### FIXED CODE ###

A,B = map(int, input().strip().split(' '))
print(max(0, A-(2*B)))
x1,y1,x2,y2=list(map(int,input().split()))

d=((x1-x2)**2+(y1-y2)**2)**0.5

print(d)

### FIXED CODE ###

x1,y1,x2,y2=list(map(float,input().split()))

d=((x1-x2)**2+(y1-y2)**2)**0.5

print(d)
import math
ABC=input().rstrip('\n').split()

A=int(ABC[0])
B=int(ABC[1])
C=int(ABC[2])

if a*a+b*b+c*c+a*b-2*a*c-2*b*c>0  :
    print ("Yes")
else :
    print ("No")

### FIXED CODE ###

import math
ABC=input().split()
 
a=int(ABC[0])
b=int(ABC[1])
c=int(ABC[2])
 
if a*a+b*b+c*c-2*a*b-2*a*c-2*b*c>0 and a+b<c  :
    print ("Yes")
else :
    print ("No")
H, W = map(int, input().split())
F = [list(input()) for _ in range(H)]

move = (-1, 1)
count = []

def dfs(i, j, seen):
    seen.add((i, j))
    if F[i][j] == '#':
        next = '.'
    else:
        next = '#'

    for m in move:
        if 0 <= i+m < H and F[i+m][j] == next and (i+m, j) not in seen:
            seen.add((i+m, j))
            if F[i][j] == '#':
                count.append((i+m, j))

            dfs(i+m, j, seen)
        if 0 <= j+m < W and F[i][j+m] == next and (i, j+m) not in seen:
            seen.add((i, j+m))
            if F[i][j] == '#':
                count.append((i, j+m))
            dfs(i, j+m, seen)

for i in range(H):
    for j in range(W):
        if F[i][j] == '#':
            dfs(i, j, set())

print(len(count))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

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

move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
seen = [[0] * W for _ in range(H)]

# Fの点を頂点とするグラフを考える。グラフの連結成分に'#'がbコ, '.'がwコある場合、
# b*wが条件を満たす

def dfs(sy, sx):
    seen[sy][sx] = 1
    b, w = 1, 0
    
    for dy, dx in move:
      ny = sy + dy
      nx = sx + dx
      if 0 <= ny < H and 0 <= nx < W and F[ny][nx] != F[sy][sx] and not seen[ny][nx]:
        p = dfs(ny, nx)
        b += p[1]  # 逆にしている
        w += p[0]  # 天才か？
    return (b, w)
        
count = 0
for i in range(H):
    for j in range(W):
        if not seen[i][j]:
            b, w = dfs(i, j)
            count += b * w

print(count)