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

from collections import deque

H, W = map(int, input().split())
items = []
black = []
for i in range(H):
    tmp = input()
    for j in range(W):
        if tmp[j] == "#":
            black.append((i, j))
    items.append(list(tmp))

que = deque()

for b in black:
    que.append(b)

ans = 0
d4 = [(1, 0), (0, -1), (-1, 0), (0, 1)]
while len(que) != H * W:
    tmp = list(que)
    for b in list(tmp):
        x, y = b[0], b[1]
        for d in d4:
            dx = d[0]
            dy = d[1]
            if 0 <= x + dx <= H - 1 and 0 <= y + dy <= W - 1:
                tar = items[x + dx][y + dy]
                if tar == ".":
                    que.append((x + dx, y + dy))
                    items[x + dx][y + dy] = "#"
    ans += 1
print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
items = []
black = []
for i in range(H):
    tmp = list(input())
    for j in range(W):
        if tmp[j] == "#":
            black.append((i, j))
    items.append(tmp)

que = []
for b in black:
    que.append(b)

ans = 0
d4 = [(1, 0), (0, -1), (-1, 0), (0, 1)]
next_que = que
while len(que) != H * W:
    tmp = next_que
    next_que = []
    for b in list(tmp):
        x, y = b[0], b[1]
        for d in d4:
            dx = d[0]
            dy = d[1]
            if 0 <= x + dx <= H - 1 and 0 <= y + dy <= W - 1:
                tar = items[x + dx][y + dy]
                if tar == ".":
                    next_que.append((x + dx, y + dy))
                    que.append((x + dx, y + dy))
                    items[x + dx][y + dy] = "#"
    ans += 1
print(ans)
### BUGGY CODE ###

#pypy
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
A.append(0)

#累積和
for _ in range(K):
    B = [0]*(N+1)
    for i in range(N):
        l = max(0,i-A[i])
        r = min(N-1, i+A[i])
        B[l] += 1
        B[r+1] -= 1
    for i in range(1,N):
        B[i] += B[i-1]
    A,B = B,A
    if min(A) == N:
        break
A.pop()
print(*A)


### FIXED CODE ###

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

#累積和
for _ in range(K):
    B = [0]*N
    for i in range(N):
        l = max(0,i-A[i])
        r = min(N-1, i+A[i])
        B[l] += 1
        if r+1 < N: B[r+1] -= 1
    for i in range(1,N):
        B[i] += B[i-1]
    B, A = A, B
    if min(A) == N:
        break

print(*A)
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
AC = [0]*N

for i in range(N-1):
  if S[i]+S[i+1] == "AC":
    AC[i] += 1

for j in range(Q):
  l,r = map(int,input().split())
  print(sum(AC[l-1:r-1]))

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
t = [0]*(N+1)

for i in range(N):
  t[i+1] = t[i] + (1 if S[i:i+2] == "AC" else 0)
  
for j in range(Q):
  l,r = map(int,input().split())
  print(t[r-1] - t[l-1])
### BUGGY CODE ###

N = int(input())

def count(i,j):
    cnt = 0
    for k in range(1,N+1):
        temp = list(str(k))
        if temp[0]==str(i) and temp[-1]==str(j):
            cnt += 1
    return cnt

ans = 0
for i in range(1,10):
    for j in range(1,10):
        ans += count(i,j)*count(j,i)
print(ans)

### FIXED CODE ###

N = int(input())

from collections import defaultdict
counter = defaultdict(int)

for k in range(1,N+1):
    temp = list(str(k))
    counter[(int(temp[0]),int(temp[-1]))] += 1

ans = 0
for i in range(1,10):
    for j in range(1,10):
        ans += counter[(i,j)]*counter[(j,i)]
print(ans)
### BUGGY CODE ###

N = int(input())
a= map(int,input().split())
 
ans = 1
for i in a:
    ans *= i
if(ans > 1e18):
    print(-1)
else:
    print(ans)


### FIXED CODE ###

N = int(input())
a = map(int,input().split())
 
x = sorted(a)
ans = 1
for i in x:
    ans *= i
    if(ans == 0):
        break
    if(ans > 1e18):
        break
if(ans > 1e18):
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

#132_E

import queue
import sys
sys.setrecursionlimit(300000)
INF=10**9
 
n,m=map(int,input().split())

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

s,t=map(int,input().split())
s,t=s-1,t-1
    
def bfs(s,t):
    que=queue.Queue()
    que.put(s)
    d[s]=0
    visit[s]=True
    while not que.empty():
        q=que.get()
        if q==t:
            return d[t]
        for x in edges[q]:
            for y in edges[x]:
                for z in edges[y]:
                    if visit[z]==False:
                        que.put(z)
                        d[z]=d[q]+1
                        visit[z]=True
    return d[t]
                
visit=[False for _ in range(n)]
d=[INF for _ in range(n)]

ans=bfs(s,t)
print(ans if ans!=INF else -1)

### FIXED CODE ###

#### 132_E

import queue
import sys
sys.setrecursionlimit(300000)
 
n,m=map(int,input().split())

edges=[[] for i in range(3*n)]
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    u0,u1,u2=u,u+n,u+2*n
    v0,v1,v2=v,v+n,v+2*n
    edges[u0].append(v1)
    edges[u1].append(v2)
    edges[u2].append(v0)
    
s,t=map(int,input().split())
s,t=s-1,t-1
    
def bfs(s,t):
    que=queue.Queue()
    que.put(s)
    d[s]=0
    visit[s]=True
    while not que.empty():
        q=que.get()
        if q==t:
            return d[t]
        for z in edges[q]:
            if visit[z]==False:
                que.put(z)
                d[z]=d[q]+1
                visit[z]=True
    return d[t]
                
visit=[False for _ in range(3*n)]
d=[-1 for _ in range(3*n)]

print(bfs(s,t)//3)
### BUGGY CODE ###

def comb(n):
    return (n * (n - 1)) // 2


def main():
    n, m = [int(a) for a in input().split()]

    AB = [
        [int(a) for a in input().split()]
        for _ in range(m)
    ]

    table = {i: (1, set([i])) for i in range(n)}  # (便利さ,行ける島集合)

    current_benrisa = 0
    max_hubensa = comb(n)

    reversed_benrisa = []
    for ai, bi in reversed(AB):
        reversed_benrisa.append(current_benrisa)
        s1_benrisa, s1_set = table[ai-1]
        s2_benrisa, s2_set = table[bi-1]
        if s1_set is s2_set:  # 変化なし
            continue

        new_benri = s1_benrisa + s2_benrisa
        new_set = s1_set.union(s2_set)
        for t in new_set:
            table[t] = (new_benri, new_set)

        inc = s1_benrisa * s2_benrisa
        current_benrisa += inc
        continue

    for a in reversed(reversed_benrisa):
        print(max_hubensa - a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def comb(n):
    return (n * (n - 1)) // 2


def main():
    n, m = [int(a) for a in input().split()]

    AB = [
        [int(a) for a in input().split()]
        for _ in range(m)
    ]

    table = {i: {i} for i in range(n)}  # (便利さ,行ける島集合)

    current_benrisa = 0
    max_hubensa = comb(n)

    reversed_benrisa = []
    for ai, bi in reversed(AB):
        reversed_benrisa.append(current_benrisa)
        s1_set = table[ai - 1]
        s2_set = table[bi - 1]
        if s1_set is s2_set:  # 変化なし
            continue

        s1_benrisa = len(s1_set)
        s2_benrisa = len(s2_set)
        # new_benri = s1_benrisa + s2_benrisa
        if len(s1_set) > len(s2_set):
            s1_set.update(s2_set)
            for t in s2_set:
                table[t] = s1_set
        else:
            s2_set.update(s1_set)
            for t in s1_set:
                table[t] = s2_set

        # new_set = s1_set.union(s2_set)
        # for t in new_set:
        #     table[t] = (new_benri, new_set)

        inc = s1_benrisa * s2_benrisa
        current_benrisa += inc
        continue

    for a in reversed(reversed_benrisa):
        print(max_hubensa - a)


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

N = int(input())
Y = [[] for _ in range(10)]
c = 0
for i in range(N):
    s = input()
    l = len(s)
    if s not in Y[l-1]:
        Y[l-1].append(s)
        c += 1
# print(Y)
print(c)

### FIXED CODE ###

N = int(input())
Y = []
for i in range(N):
    Y.append(input())
print(len(set(Y)))
### BUGGY CODE ###

from collections import deque
 
def cnt():
    n, q = map(int, input().split())
    s = input()
    qs = []
    for i in range(q):
        qs.append(list(map(int, input().split())))
    for l, r in qs:
        que = deque(maxlen = 2)
        cnt = 0
        for a in s[l-1: r]:
            que.append(a)
            if que == deque(['A', 'C']):
                cnt += 1
        print(cnt)
        
cnt()

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
qs = [list(map(int, input().split())) for i in range(Q)]
t =[0] * N
for i in range(N-1):
    t[i+1] = t[i] + (1 if S[i:i+2] == 'AC' else 0)
def ans(l, r):
    return t[r-1] - t[l-1]
for l, r in qs:
    print(ans(l,r))
### BUGGY CODE ###

from collections import deque
N, Q = map(int, input().split())
S = input()
l = [0 for i in range(Q)]
r = [0 for i in range(Q)]

for i in range(Q):
    l[i], r[i] = map(int, input().split())

for i in range(Q):
    print(S[l[i]-1:r[i]].count('AC'))


### FIXED CODE ###

n,q = map(int,input().split())
s = list(input())

#a[i]:s[0]~s[i]までに何個ACがあったか
a = [0]*n
#end[i]:s[i]がACの'C'か
end = [False]*n
for i in range(1,n):
    if s[i] == 'C' and s[i-1] == 'A':
        a[i] = a[i-1]+1
        end[i] = True
    else:
        a[i] = a[i-1]

for i in range(q):
    L,R = map(int,input().split())
    L,R = L-1,R-1
    if L == 0:
        print(a[R])
    else:
        if end[L]:
            print(a[R]-a[L-1]-1)
        else:
            print(a[R]-a[L-1])
### BUGGY CODE ###

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

def plus_minus(idx):
    ans = [0] * n
    indicator = 1
    for new_i in range(idx, idx + n):
        ans[new_i % n] = indicator
        indicator *= -1
    #print(idx, ans)
    return ans

ans = []
for dam in range(n):
    total = 0
    pm = plus_minus(dam)
    for i, a in enumerate(A):
        total += pm[i] * a
    ans.append(total)

print(*ans, sep=" ")

### FIXED CODE ###

from collections import defaultdict as dd

n = int(input())
A = list(map(int, input().split()))
odd_ac = dd(int)
even_ac = dd(int)
for i, a in enumerate(A):
    if i % 2 == 0:
        even_ac[i] = even_ac[i-2] + a
    else:
        odd_ac[i] = odd_ac[i-2] + a
#print(odd_ac)
#print(even_ac)

ans = []
for dam in range(n):
    is_odd = dam % 2
    total = 0
    if is_odd:
        total += odd_ac[n-2] - odd_ac[dam-2]
        total -= even_ac[n-1] - even_ac[dam-1]
        total += even_ac[dam-1]
        total -= odd_ac[dam-2]
    else:
        total += even_ac[n-1] - even_ac[dam-2]
        total -= odd_ac[n-2] - odd_ac[dam-1]
        total -= even_ac[dam-2]
        total += odd_ac[dam-1]

    ans.append(total)

print(*ans, sep=" ")
### BUGGY CODE ###

A,B,Q = map(int,input().split())
jinjya = [0]*(A+1)+[float('inf')]#範囲を絞るために両サイドに0と無限を挿入
tera =[0]*(B+1)+[float('inf')]
for i in range(A):
  jinjya[i+1] =int(input())
for i in range(B):
  tera[i+1] =int(input())

for i in range(Q):
  x=int(input())
#出発地点の前後の神社と寺の場所を知りたい。つまり出発点より前にある対象のインデックス
  L=0
  R=A+2
  while R-L>1:
    P=(L+R)//2
    if x<jinjya[P]:
      R=P
    else:
      L=P
  jinjya_L=L
  
  L=0
  R=B+2
  while R-L>1:
    P=(L+R)//2
    if x<tera[P]:
      R=P
    else:
      L=P
  tera_L=L

#xの左側の神社と寺のインデックスがわかったのでそれらに対して距離を測って最小を探す。
#両サイドのダミーに注意する。
  a=jinjya[jinjya_L]
  b=jinjya[jinjya_L+1]
  c=tera[tera_L]
  d=tera[tera_L+1]
  if jinjya_L==0:
    a=b
  if tera_L==0:
    c=d
  answer=min(abs(x-a)+abs(a-c),abs(x-c)+abs(c-a),abs(x-b)+abs(b-c),abs(x-c)+abs(c-b),abs(x-a)+abs(a-d),abs(x-d)+abs(d-a),abs(x-b)+abs(b-d),abs(x-d)+abs(d-b))
  print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.readline

A,B,Q = map(int,input().split())
jinjya = [-float('inf')]+[int(input()) for _ in range(A)]+[float('inf')]#範囲を絞るために両サイドに0と無限を挿入
tera =[-float('inf')]+[int(input()) for _ in range(B)]+[float('inf')]

for i in range(Q):
  x=int(input())
#出発地点の前後の神社と寺の場所を知りたい。つまり出発点より前にある対象のインデックス
  L=0
  R=A+2
  while R-L>1:
    P=(L+R)//2
    if x<jinjya[P]:
      R=P
    else:
      L=P
  jinjya_L=L
  
  L=0
  R=B+2
  while R-L>1:
    P=(L+R)//2
    if x<tera[P]:
      R=P
    else:
      L=P
  tera_L=L
#xの左側の神社と寺のインデックスがわかったのでそれらに対して距離を測って最小を探す。
  a=jinjya[jinjya_L]
  b=jinjya[jinjya_L+1]
  c=tera[tera_L]
  d=tera[tera_L+1]
  if jinjya_L==0:
    a=b
  if tera_L==0:
    c=d
  answer=min(abs(x-a)+abs(a-c),abs(x-c)+abs(c-a),abs(x-b)+abs(b-c),abs(x-c)+abs(c-b),abs(x-a)+abs(a-d),abs(x-d)+abs(d-a),abs(x-b)+abs(b-d),abs(x-d)+abs(d-b))
  print(answer)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000)

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

num_dict = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6
}

# Aの各要素の画数
count_list = [num_dict[a] for a in A]

# 最小の画数
min_matches = min(count_list)

# 画数の最小の値のうち最大の数値
min_num_list = []
[min_num_list.append(a) for a in A if num_dict[a] == min_matches]
min_num = max(min_num_list)


# 数値とあまり消化数のペア
A.sort(reverse=True)
res = {a: num_dict[a]-min_matches for a in A}


def dfs(nums, target, num_count):
    if len(nums) > num_count:
        return None
    if target == 0:
        return nums
    elif target < 0:
        return None
    else:
        for a in A:
            ret = dfs(nums+[a], target-res[a], num_count)
            if ret is not None:
                return ret
        return None


for num_count in range(N//min_matches, 0, -1):
    # あまりの本数
    mod = N - min_matches*num_count

    # あまりをどう分配するか(DFS)
    share = dfs([], mod, num_count)
    if share is not None:
        out_list = sorted([min_num]*(num_count-len(share))+share, reverse=True)
        out_list = [str(item) for item in out_list]
        print(''.join(out_list))
        break


### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10000)


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

num_dict = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6
}
A.sort(reverse=True)

# dpを計算
dp = defaultdict(lambda: -1e18)
dp[0] = 0

for i in range(2, N+1):
    dp[i] = max([dp[i-num_dict[a]]+1 for a in A])

num_count = dp[N]

out_list = []
res_N = N
for _ in range(num_count):
    for a in A:
        if dp[res_N]-1 == dp[res_N-num_dict[a]]:
            out_list.append(str(a))
            res_N = res_N - num_dict[a]
            break

print(''.join(out_list))
### BUGGY CODE ###

N = int(input())
from collections import defaultdict

G = defaultdict(list)
EdaNum = defaultdict(int)

for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
    EdaNum[(a,b)] = i
    
ans = [-1]*(N-1)

que = [[1,-1,-1]]
K = 0
visited = [False]*(N+1)

for i in range(1,N+1):
    K = max(K,len(G[i]))

while que != []:
    #print(que)
    now,parent,parentcolor = que.pop()
    visited[now]=True
    used = [False]*(K+1)
    nowcolor = 1
    for i in G[now]:
        #print(i,parent)
        if i != parent:
            if nowcolor == parentcolor:
                nowcolor += 1
            ans[EdaNum[(min(now,i),max(now,i))]] = nowcolor
            nowcolor += 1
            if len(G[i])!=1:
                que.append([i,now, nowcolor-1])
    #print(que)

print(K)
for i in ans:
    print(i)

### FIXED CODE ###

N = int(input())
from collections import defaultdict

G = defaultdict(list)
EdaNum = defaultdict(int)

for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
    EdaNum[(a,b)] = i
    
ans = [-1]*(N-1)

que = [[1,-1,-1]]
K = 0
visited = [False]*(N+1)

for i in range(1,N+1):
    K = max(K,len(G[i]))

while que != []:
    #print(que)
    now,parent,parentcolor = que.pop()
    visited[now]=True
    nowcolor = 1
    for i in G[now]:
        #print(i,parent)
        if i != parent:
            if nowcolor == parentcolor:
                nowcolor += 1
            ans[EdaNum[(min(now,i),max(now,i))]] = nowcolor
            nowcolor += 1
            if len(G[i])!=1:
                que.append([i,now, nowcolor-1])
    #print(que)

print(K)
for i in ans:
    print(i)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
abs_a = []
minus = 0

for i in range(n):
  if a[i] < 0: minus += 1
  else:break

if minus % 2 == 0:
  for i in range(n):
    if a[i] < 0:
      abs_a.append(abs(a[i]))
    else:
      abs_a.append(a[i])
  print(sum(abs_a))
else:
  for i in range(n):
    if a[i] < 0:
      abs_a.append(abs(a[i]))
    else:
      abs_a.append(a[i])
    min_abs_a = min(abs_a)
  print(sum(abs_a)-min_abs_a*2)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
abs_a = []
minus = 0

for i in range(n):
  if a[i] < 0: minus += 1

for i in range(n):
  abs_a.append(abs(a[i]))
  
if minus % 2 == 0:
  print(sum(abs_a))
else:
  min_abs_a = min(abs_a)
  print(sum(abs_a)-min_abs_a*2)
### BUGGY CODE ###

import sys
from functools import lru_cache
sys.setrecursionlimit(1000000)
readline = sys.stdin.readline

N = int(readline())

adj = [[] for i in range(N)]
for i in range(N - 1):
    A, B = map(int, readline().split())
    A -= 1
    B -= 1
    adj[A].append(B)
    adj[B].append(A)

mod = 10 ** 9 + 7
pow2 = [1] * (N + 1)
for i, j in zip(range(N), range(1, N + 1)):
    pow2[j] = pow2[i] * 2 % mod

ans = 0


@lru_cache(maxsize=None)
def dfs(node, parent):
    global ans
    cnt = 1
    
    for child in adj[node]:
        if child != parent:
            cnt += dfs(child, node)
    
    ans += (pow2[cnt] - 1) * (pow2[N-cnt] - 1)
    ans %= mod
    
    return cnt

dfs(0, None)

ans = (ans - N * pow2[N-1] + pow2[N] - 1) % mod
ans = ans * pow(pow2[N], mod - 2, mod) % mod

print(ans)


### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline

N = int(readline())
graph = [[] for _ in range(N + 1)]
for i in range(N - 1):
    a, b = map(int, readline().split())
    lb = 1 << i
    graph[a].append(b)
    graph[b].append(a)

root = 1
parent = [0] * (N + 1)
order = []
stack = [root]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

MOD = 10**9 + 7
x = (MOD + 1) // 2
power_inv = [1] * (N + 100)
for i in range(1, N + 100):
    power_inv[i] = power_inv[i - 1] * x % MOD

size = [1] * (N + 1)
p_size = [N - 1] * (N + 1)
prod = [1] * (N + 1)
coef = [1] * (N + 1)
for v in order[::-1]:
    p = parent[v]
    x = size[v]
    size[p] += x

ans = 0
for i in size[2:]:
    ans += 1 - power_inv[i] - power_inv[N - i] + power_inv[N]
    ans %= MOD
ans = ans - N * power_inv[1] + 1 - power_inv[N]
ans %= MOD

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

from sys import stdin
n,h=map(int,input().split())
l=list(map(int,stdin.readline().split()))
c=[0]*n
c[0]=0
c[1]=abs(l[0]-l[1])
for i in range(2,n):
    c[i]=min( c[j]+abs(l[i]-l[j]) for j in range(max(0,i-h),i) )
print(c[-1])

### FIXED CODE ###

n,h=map(int,input().split())
l=list(map(int,input().split()))
c=[10**9]*n
c[0]=0
c[1]=abs(l[0]-l[1])
for i in range(2,n):
    c[i]=min( c[j]+abs(l[i]-l[j]) for j in range(max(0,i-h),i) )
print(c[-1])
### BUGGY CODE ###

def gcd(m,n):
  x=max(m,n)
  y=min(m,n)
  if x==0:
    return 0
  while y!=0:
    x,y=y,x%y
  return x

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

for i in range(n):
  a[i],a[n-1]=a[n-1],a[i]
  temp = a[0]
  for j in range(n-1):
    temp=gcd(temp,a[j])
  b.append(temp)
  a[i],a[n-1]=a[n-1],a[i]
  
print(max(b))

### FIXED CODE ###

def gcd(m,n):
  x=max(m,n)
  y=min(m,n)
  while y!=0:
    x,y=y,x%y
  return x

n = int(input())
a = list(map(int, input().split()))
b = []
l = [0]
r = [0]

for i in range(n):
  l.append(gcd(a[i],l[i]))
  r.append(gcd(a[n-1-i],r[i]))

for i in range(n):
  b.append(gcd(l[i],r[n-1-i]))
  
print(max(b))
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for i in range(m):
    i = a.index(max(a))
    a[i] = a[i] // 2
print(sum(a))


### FIXED CODE ###

import heapq
n, m = map(int, input().split())
a = list(map(lambda x: int(x) * -1, input().split()))
heapq.heapify(a)
for _ in range(m):
    tmp = (heapq.heappop(a) * (-1)) // 2
    heapq.heappush(a, -tmp)
print(sum(a) * -1)
### BUGGY CODE ###

import sys
import bisect
input=sys.stdin.readline

N=int(input())
A=[int(input()) for _ in range(N)]
l=[]
for x in A:
    if len(l)>0:
        tmp=bisect.bisect_left(l,x)
        if tmp==0:l=[x]+l
        else:
            l[tmp-1]=x
    else:l.append(x)
print(len(l))

### FIXED CODE ###

import sys
import bisect
input=sys.stdin.readline

N=int(input())
A=[-int(input()) for _ in range(N)]
l=[A[0]]
for x in A[1::]:
    tmp=bisect.bisect(l,x)
    if tmp==len(l):l.append(x)
    else: l[tmp]=x
print(len(l))
### BUGGY CODE ###

n = input()
al = [int(x) for x in input().split()]
aset = set(al)

# {number: count}
counts_d = {i: sum(a == i for a in al) for i in aset}

vset = set(counts_d.values())
# Count of count
v_counts = {v: sum(v == i for i in counts_d.values()) for v in vset}

whole_patterns = sum(
    (int(k * (k - 1) / 2)) * v for k, v in v_counts.items() if k > 1
)

[print(whole_patterns - counts_d[a] + 1) for a in al]


### FIXED CODE ###

import collections

n = input()
al = tuple(x for x in input().split())
aset = set(al)

# {number: count}
ccc = collections.Counter
counts_d = ccc(al)

# Count of count
v_counts = ccc(v for v in counts_d.values())

whole_patterns = sum(
    (int(k * (k - 1) / 2)) * v for k, v in v_counts.items() if k > 1
)

[print(whole_patterns - counts_d[a] + 1) for a in al]
### BUGGY CODE ###

def binSearch(array, num):
    n = len(array)
    l = -1
    r = n

    while l + 1 < r:
        m = (l + r) // 2
        if num <= array[m]:
            r = m
        else:
            l = m

    return r


n = int(input())

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

a.sort()
b.sort()
c.sort()

ans = 0
for i in range(len(b)):
    a_idx = binSearch(a, b[i])
    c_idx = binSearch(c, b[i] + 1)
    l = len(c[c_idx:])
    ans += a_idx * (n - c_idx)
print(ans)


### FIXED CODE ###

import bisect

n = int(input())

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

a.sort()
c.sort()

ans = 0
for i in range(len(b)):
    a_idx = bisect.bisect_left(a, b[i])
    c_idx = bisect.bisect_right(c, b[i])
    ans += a_idx * (n - c_idx)
print(ans)
### BUGGY CODE ###

X = int(input())
A = 1
K = 1
while K < X:
    A += 1
    K = A ** 5
S = A - 1
w = 0
while w != 1:
    Q = S ** 5 - X
    if Q < 0:
        B = 0
        while (Q < B**5):
            B -= 1
        if (Q == B**5):
            w += 1
        else:
            S += 1
        
    elif Q > 0:
        B = 0
        while (Q > B**5):
            B += 1
        if (Q == B**5):
            w += 1
        else:
            S += 1
print(S,B)

### FIXED CODE ###

X = int(input())
for i in range (240):
    for j in range (240):
        s = (i -120)**5 - (j -120)**5
        if s == X:
            A = i-120
            B = j -120
print(A,B)
### BUGGY CODE ###

import numpy as np
n,x,y = map(int,input().split())
a = np.zeros(n-1)
for i in range(n-1):
    for j in range(i+1,n):
        dist = min(j-i, abs(i-x+1)+1+abs(j-y+1), abs(i-y+1)+1+abs(j-x+1))
        a[dist-1] += 1
for ans in a:
    print(int(ans))

### FIXED CODE ###

n,x,y = map(int,input().split())
a = [0]*(n-1)
for i in range(n-1):
    for j in range(i+1,n):
        dist = min(j-i, abs(i-x+1)+1+abs(j-y+1))
        a[dist-1] += 1
for ans in a:
    print(ans)
### BUGGY CODE ###

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, = read_line(int)
a = read_line(*([int] * n))

def price(aa, skip):
    sum = 0

    prev = 0
    for i in range(len(aa)):
        if i == skip:
            continue
        sum += abs(prev - aa[i])
        prev = aa[i]

    sum += abs(prev)
    return sum

for i in range(len(a)):
    print(price(a, i))


### FIXED CODE ###

#!/usr/bin/env python

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, = read_line(int)
a = read_line(*([int] * n))

def price(aa):
    sum = 0

    prev = 0
    for i in range(len(aa)):
        sum += abs(prev - aa[i])
        prev = aa[i]

    sum += abs(prev)
    return sum

aa = [0] + a + [0]
price_all = 0

for i in range(len(aa) - 1):
    price_all += abs(aa[i] - aa[i + 1])

for i in range(1, len(aa) - 1):
    p = price_all
    p -= abs(aa[i - 1] - aa[i])
    p -= abs(aa[i] - aa[i + 1])
    p += abs(aa[i - 1] - aa[i + 1])
    print(p)