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

s=input()
n=len(s)
m=2019
s_int=[]
ans=0
for i in range(n):
  s_int.append(int(s[i]))

for i in range(n-1):
  x=s_int[i]
  for j in range(i+1,n):
    x=(x*10+s_int[j])%m
    if x==0:
      ans+=1
print(ans)

### FIXED CODE ###

mod2019=[0]*2019
mod2019[0]=1
t=input()
n=len(t)
s=[]
for i in range(n):
  s.append(int(t[i]))
x=1
y=0
for i in reversed(range(n)):
  y+=s[i]*x
  mod2019[y%2019]+=1
  x=(x*10)%2019
ans=0
for i in range(2019):
  ans+=mod2019[i]*(mod2019[i]-1)
print(ans//2)
### BUGGY CODE ###

N, A, B = map(int, input().split())
ball = 0
cnt = 0

while N > 0:
  if cnt % 2 == 0:	# 青
    i = min(A, N)
    ball += i
  else:				# 赤
    i = min(B, N)
  N -= i
  cnt += 1

print(ball)


### FIXED CODE ###

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

if N == 0:
  print(0)
  exit()

cnt = N // (A + B)
rem = N % (A + B)

ans = 0

if rem >= A:
  ans = A * (cnt + 1)
else:
  ans = A * cnt + rem

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

# coding: utf-8
def II(): return int(input())
def ILI(): return list(map(int, input().split()))


def read():
    N = II()
    return (N,)


def solve(N):
    ans = []
    for h in range(1, 3501):
        flag = False
        for n in range(1, 3501):
            w = (4 * h * n - N * h - N * n) / (N * h * n)
            if w > 0 and int(w) == w:
                ans = [h, n, w]
                flag = True
                break
        if flag:
            break
    ans = " ".join(map(str, map(int, ans)))
    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()


### FIXED CODE ###

# coding: utf-8
def II(): return int(input())
def ILI(): return list(map(int, input().split()))


def read():
    N = II()
    return (N,)


def solve(N):
    ans = []
    for h in range(1, 3501):
        flag = False
        for n in range(1, 3501):
            if 4 * h * n - N * h - N * n == 0:
                continue
            div, mod = divmod(N * h * n, 4 * h * n - N * h - N * n)
            if mod == 0 and div > 0:
                ans = [h, n, div]
                flag = True
                break
        if flag:
            break
    ans = " ".join(map(str, ans))
    return ans


def main():
    params = read()
    print(solve(*params))


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

K,S = map(int,input().split(" "))
a = 0
ans = 0
while a <= K:
  b = 0
  while b <= K:
    if S-(a+b) <= K and S-(a+b) >= 0:
       ans+=1
    b += 1
  a+=1
print(ans)

### FIXED CODE ###

#B問題
K,S=map(int,input().split())
count=0
for y in range(K+1):
    x=0
    for x in range(K+1):
        z=S-(x+y)
        if z <= K and z >= 0:
            count+=1
print(count)
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
# sx, sy = map(int, input().split())
# gx, gy = map(int, input().split())
# sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
c = [input() for i in range(H)]
INF = 10**9
def bfs():
    dist = [[INF for i in range(W)] for j in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    q = deque()
    q.append([sx, sy])
    dist[sx][sy] = 0
    while q:
        p = q.popleft()
        if p[0] == gx and p[1] == gy:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx and nx < H and 0 <= ny and ny < W:
                if c[nx][ny] != '#' and dist[nx][ny] == INF:
                    q.append([nx, ny])
                    dist[nx][ny] = dist[p[0]][p[1]] + 1
    return dist[gx][gy]

ans = -1
for i in range(H):
    for j in range(W):
        for k in range(H):
            for l in range(W):
                sx, sy = i, j
                gx, gy = k, l
                if c[sx][sy] == '#' or c[gx][gy] == '#':
                    continue
                if bfs() == INF:
                    continue
                ans = max(ans, bfs())
print(ans)

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
c = [input() for i in range(H)]

INF = -1

def bfs():
    dist = [[INF for i in range(W)] for j in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    q = deque()
    q.append([sx, sy])
    dist[sx][sy] = 0
    while q:
        p = q.popleft()
        # if p[0] == gx and p[1] == gy:
        #     break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx and nx < H and 0 <= ny and ny < W:
                if c[nx][ny] != '#' and dist[nx][ny] == INF:
                    q.append([nx, ny])
                    dist[nx][ny] = dist[p[0]][p[1]] + 1
    ret = -1
    for i in range(H):
        ret = max(ret, max(dist[i]))
    return ret

ans = -1
for i in range(H):
    for j in range(W):
            sx, sy = i, j
            if c[sx][sy] == '#':
                continue
            ans = max(ans, bfs())
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(n)]
num = []
for i in range(n):
    for _ in range(l[i][1]):
        num.append(l[i][0])
num = sorted(num)
print(sum(num[:m]))

### FIXED CODE ###

n, m = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(n)]
l.sort(key=lambda x: x[0])
num = 0
ansum = 0
for i in range(n):
    if num + l[i][1] < m:
        ansum += l[i][0] * l[i][1]
        num += l[i][1]
    else:
        ansum += l[i][0] * (m - num)
        break
print(ansum)
### BUGGY CODE ###

X = input()
S = [X[0]]
for i in range(2, len(X)+1):
    if X[i-1] == 'S':
        S.append('S')
    else:
        if 'S' in S:
            S.remove('S')
        else:
            S.append('T')
print(len(S))


### FIXED CODE ###

X = input()
s = 0
t = 0
for x in X:
    if x == 'S':
        s += 1
    else:
        if s > 0:
            s -= 1
        else:
            t += 1
print(s+t)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
for i in range(1,N+1):
  print(A.count(i))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ma = [0 for i in range(N)] 
for i in range(len(A)):
  ma[A[i]-1] += 1
for i in range(len(ma)):
  print(ma[i])
### BUGGY CODE ###

import math
def comb(x,y):
    f = 1
    for i in range(y):
        f *= (x-i)
        f //= (i+1)

    return f

n,m = map(int,input().split())

cnt = [0]
for i in range(2,m+1):
    while m!=i:
        if m%i==0:
            m //=i
            cnt[-1]+=1
        else:
            cnt.append(0)
            break
    if m==i:
        cnt[-1]+=1
        break
cnt = [item for item in cnt if cnt != 0]


res = 1
r = 10**9 +7
for item in cnt:
    res = (res* comb(item+n-1,item))%r

print(res%r)


### FIXED CODE ###

import math
def comb(x,y):
    f = 1
    for i in range(y):
        f *= (x-i)
        f //= (i+1)

    return f

n,m = map(int,input().split())

i = 2
cnt = []
while i*i<=m:
    c = 0
    while m%i == 0:
        m //= i
        c += 1
    if c>0:
        cnt.append(c)
    i+=1
if m>1:
    cnt.append(1)
        

res = 1
r = 10**9 +7
for item in cnt:
    res = (res* comb(item+n-1,item))%r

print(res%r)
### BUGGY CODE ###

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

b = [0] * (n - 1)
for i in range(n - 1):
    b[i] = sum(a[i + 1 : n])
ans = 0
for i in range(n - 1):
    ans += a[i] * b[i]

print(ans % (10 ** 9 + 7))

### FIXED CODE ###

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

all_sum = (sum(a) ** 2)
diff = [(a[i] ** 2) for i in range(n)]

ans = (all_sum - sum(diff)) // 2

print(ans % (10 ** 9 + 7))
### BUGGY CODE ###

n = int(input())
ls = list(map(int, input().split()))
lsa = []
for j in range(n):
    k = ls.index(j + 1)
    lsa += [k + 1]
for m in range(n):
    print(lsa[m], end = " ") 


### FIXED CODE ###

n = int(input())
ls = list(map(int,input().split()))
ls2 = [0 for i in range(n)]
for j in range(n):
    a = ls[j]
#aは出席番号j+1番目の順位
    ls2[a - 1] = j + 1
for k in range(n):
    print(ls2[k], end = " ")
### BUGGY CODE ###

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

broken = []
for _ in range(M):
  broken.append(int(input()))

mod = 10 ** 9 + 7
f2, f1 = 0, 1
for i in range(1, N + 1):
  if i in broken:
    if i - 1 in broken:
      print(0)
      exit()
    f2 = f1
    f1 = 0
    continue
  f = f2 + f1
  f2 = f1
  f1 = f
print(f % mod)

### FIXED CODE ###

import sys
 
n, m = list(map(int, input().split()))
if m > 0:
    aaa = set(map(int, sys.stdin))
else:
    aaa = set()
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if 1 not in aaa else 0
MOD = 10 ** 9 + 7
 
for i in range(2, n + 1):
    if i in aaa:
        continue
    dp[i] = (dp[i - 2] + dp[i - 1]) % MOD
print(dp[n])
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
for i in range(1,N+1):
  print(A.count(i))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans_list = [0]*N

for i in range(N-1):
  ans_list[A[i]-1] += 1
  
for j in range(N):
  print(ans_list[j])
### BUGGY CODE ###

k = int(input())
a = [1,2,3,4,5,6,7,8,9]
for i in range(k):
    test = a.pop(0)
    temp = test % 10
    if temp == 0:
        a.append(test * 10)
        a.append(test * 10 + 1)
    elif temp == 9:
        a.append(test * 10 + 8)
        a.append(test * 10 + 9)
    else:
        a.append(test * 10 + temp - 1)
        a.append(test * 10 + temp)
        a.append(test * 10 + temp + 1)
print(test)

### FIXED CODE ###

import queue

k = int(input())
a = queue.Queue()
for i in range(9):
    a.put(i + 1)
for i in range(k):
    test = a.get()
    temp = test % 10
    if temp == 0:
        a.put(test * 10)
        a.put(test * 10 + 1)
    elif temp == 9:
        a.put(test * 10 + 8)
        a.put(test * 10 + 9)
    else:
        a.put(test * 10 + temp - 1)
        a.put(test * 10 + temp)
        a.put(test * 10 + temp + 1)
print(test)
### BUGGY CODE ###

N = int(input())

numbers = [num for num in range(1, N)]
    
print(sum(numbers))


### FIXED CODE ###


N = int(input())

calc_N =  N-1

if calc_N % 2 == 1:
    O = calc_N // 2
    output = (1+calc_N) * O + O + 1
else :
    O = calc_N // 2
    output = (1+calc_N) * O
    
print(output)
### BUGGY CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**7)

N = int(input())

def pToHW(p):
    p = int(p) - 1
    return divmod(p, N)

P = list(map(pToHW, input().split()))
INF = 10**18

minDist = [[INF] * N for _ in range(N)]
isFilled = [[True] * N for _ in range(N)]


def dfs(h, w):
    dist = minDist[h][w] + (1 if isFilled[h][w] else 0)
    for toH, toW in ((h + 1, w), (h - 1, w), (h, w + 1), (h, w - 1)):
        if 0 <= toH < N and 0 <= toW < N:
            if minDist[toH][toW] > dist:
                minDist[toH][toW] = dist
                dfs(toH, toW)

for i in range(N):
    minDist[i][0] = 0
    minDist[0][i] = 0
    minDist[i][N - 1] = 0
    minDist[N - 1][i] = 0
for i in range(N):
    dfs(i, 0)
    dfs(0, i)
    dfs(i, N - 1)
    dfs(N - 1, i)

ans = 0
for h, w in P:
    ans += minDist[h][w]
    isFilled[h][w] = False
    dfs(h, w)
print(ans)


### FIXED CODE ###

import sys
import numpy as np

if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    cc = CC('my_module')

    @cc.export('solve', 'i4(i4, i4[:])')
    def solve(N, P):
        minDist = np.ones((N, N), dtype=np.int32)
        isFilled = np.ones((N, N), dtype=np.int32)

        for h in range(N):
            for w in range(N):
                minDist[h][w] = min(h, N - h - 1, w, N - w - 1)

        ans = 0
        for p in P:
            h, w = divmod(p, N)
            ans += minDist[h][w]
            isFilled[h][w] = False

            st = [(h, w)]
            while st:
                h, w = st.pop()
                dist = minDist[h][w] + isFilled[h][w]

                if h + 1 < N and minDist[h + 1][w] > dist:
                    minDist[h + 1][w] = dist
                    st.append((h + 1, w))
                if h - 1 >= 0 and minDist[h - 1][w] > dist:
                    minDist[h - 1][w] = dist
                    st.append((h - 1, w))
                if w + 1 < N and minDist[h][w + 1] > dist:
                    minDist[h][w + 1] = dist
                    st.append((h, w + 1))
                if w - 1 < N and minDist[h][w - 1] > dist:
                    minDist[h][w - 1] = dist
                    st.append((h, w - 1))
        return ans

    cc.compile()
    exit(0)

from my_module import solve

N = int(input())
P = np.asarray(list(map(lambda a: int(a) - 1, input().split())), dtype=np.int32)

print(solve(N, P))
### BUGGY CODE ###

N = int(input())
li = list(map(int, input().split()))
li.sort()


S = 1
for i in range(N-1):
    S = S*( li[i+1] - li[i] )

if S == 0:
    print('NO')
else:
    print('YES')

### FIXED CODE ###

N = int(input())
li = list(map(int, input().split()))
li.sort()


S = 1
for i in range(N-1):
    if  li[i+1] == li[i]:
        S = S*0
    else:
        S = S
if S == 0:
    print('NO')
else:
    print('YES')
### BUGGY CODE ###

import math
import itertools
 
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)

ans = 0
for i in range(n-2):
    x = a[i]
    for j in range(i+1,n-1):
        y = a[j]
        if x/2 > y:
            break
        for k in range(j+1,n):
            if y+a[k] > x:
                ans += 1
            else:
                break

print(ans) 
            

### FIXED CODE ###

import bisect
 
n = int(input())
a = list(map(int,input().split()))
a.sort()

ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        index = bisect.bisect_left(a,a[i]+a[j])
        ans += index-j-1
        
print(ans)
### BUGGY CODE ###

N,A=map(int,input().split())
X=[int(a) for a in input().split()]
X.insert(0,0)
ma=sum(X)

#[x]までのy個を使ってzを作る場合の数を数え上げるdp
#dp[x][y][z]=dp[x-1][y][z]+dp[x-1][y-1][z-X[x]](zが残っている場合）
#dp[x][y][z]=dp[x-1][y][z](zが残っていない場合)
dp=[[[0 for i in range(ma+1)] for j in range(N+1)] for k in range(N+1)]
for i in range(N+1):
  dp[i][0][0]=1
for i in range(1,N+1):
  for j in range(1,N+1):
    for k in range(ma+1):
      if k < X[i]:
        dp[i][j][k]=dp[i-1][j][k]
      else:
        dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-X[i]]

#ansはN枚中j枚使用かつj枚*平均Aを作れる個数。
ans=0
for x in range(1,N+1):
  if x*A<=ma:
    ans+=dp[N][x][x*A]
print(ans)


### FIXED CODE ###

def solve(N,A,X):  
  X.append(0)
  X.sort()
  ma=sum(X)

#[x]までのy個を使ってzを作る場合の数を数え上げるdp
#dp[x][y][z]=dp[x-1][y][z]+dp[x-1][y-1][z-X[x]](zが残っている場合）
#dp[x][y][z]=dp[x-1][y][z](zが残っていない場合)
  dp=[[[0] * (ma+1) for _ in range(N+1)] for _ in range(N+1)]
  
#[x]までの0個を使って0を作る方法は1つ（dp初期化）
  for i in range(N+1):
    dp[i][0][0]=1
  for i in range(1,N+1):
    cnt=X[i]
    for j in range(1,N+1):
      for k in range(ma+1):
        if k < cnt:
          dp[i][j][k]=dp[i-1][j][k]
        else:
          dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-cnt]

#ansはN枚中j枚使用かつj枚*平均Aを作れる個数。
  ans=0
  for x in range(1,N+1):
    if x*A<=ma:
      ans+=dp[N][x][x*A]
  return ans

N,A=map(int,input().split())
X=[int(a) for a in input().split()]
ans=solve(N,A,X)
print(ans)
### BUGGY CODE ###

n,k= (int(i) for i in input().split())       #入力整数横2つ以上
a = [int(i) for i in input().split()]  
a.sort()
cnum = a[0]
ct =1
st = []
for i in range(1,n):
    if a[i] != cnum:
        cnum = a[i]
        st.append(ct)
        ct = 1
    else:ct+=1
st.append(ct)
st.sort()
total = 0
while len(st)>k:
    total+=st.pop(0)
print(total)

### FIXED CODE ###

import math
import fractions
import copy
#以下てんぷら
def j(q):
    if q==1: print("YES")
    elif q == 0:print("NO")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def printrow(a):
    for i in range(len(a)):
        print(a[i])
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


#n = ip()                                     #入力整数1つ
n,k= (int(i) for i in input().split())       #入力整数横2つ以上
a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#a=[input() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#全足しに4 3sum変数使用はsum関数使用できないので注意
a.sort()
cnum = a[0]
ct =1
st = []
for i in range(1,n):
    if a[i] != cnum:
        cnum = a[i]
        st.append(ct)
        ct = 1
    else:ct+=1
st.append(ct)
st.sort(reverse=True)
total = 0
for i in range(min(k,len(st))):
    total+=st[i]
print(n-total)
### BUGGY CODE ###

n = int(input())
s = input()
 
ans = float('inf')
 
for i in range(n):
  ans = min(ans,s[0:i].count('W')+s[i+1:n].count('E'))
print(ans)

### FIXED CODE ###

n = int(input())
s = input()

ans = float('inf')
w_left = [0]*n
e_right = [0]*n

for i in range(1,n):
  if s[i-1] == 'W':
    w_left[i] = w_left[i-1]+1
  else :
    w_left[i] = w_left[i-1]
      
for i in range(1,n):
  if s[n-i] == 'E':
    e_right[n-i-1] = e_right[n-i]+1
  else :
    e_right[n-i-1] = e_right[n-i]

for i in range(n):
    if ans > w_left[i]+e_right[i]:
        ans = w_left[i]+e_right[i]
print(ans)
### BUGGY CODE ###

from operator import mul
from functools import reduce
from collections import Counter

def cmb(n, r):
    if n < 2:
        return 0
    r = min(n-r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under

N = int(input())
A = [int(x) for x in input().split()]
C = Counter(A)
ans = {}
for a in C.keys():
    ans[a] = sum([cmb(C[i]-1, 2) if i == a else cmb(C[i], 2) for i in C.keys()])

for a in A:
    print(ans[a])

### FIXED CODE ###

from collections import Counter

N = int(input())
A = [int(x) for x in input().split()]
C = Counter(A)
ans = {}
cal = sum([b*(b-1)//2 for b in C.values()])
for a, b in C.items():
    ans[a] = cal - (b-1)
for a in A:
    print(ans[a])
### BUGGY CODE ###


def solve(n, x, a):
	costs = []
	cost_min = 0
	for k in range(n):
		if k == 0:
			costs = a.copy()
		else:
			for i in range(n):
				costs[i] = min(costs[i], a[(i-k)%n])
		cost_k = sum(costs) + k*x
		if k == 0:
			cost_min = cost_k
		else:
			cost_min = min(cost_min, cost_k)
			if cost_min != cost_k:
				break
		if cost_min < (k+1) *x:
			break
 
	return cost_min
n, x = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
print(solve(n,x,a))

### FIXED CODE ###

def solve(n, x, a):
	costs = []
	cost_min = 0
	for k in range(n):
		if k == 0:
			costs = a.copy()
		else:
			for i in range(n):
				costs[i] = min(costs[i], a[(i-k)%n])
		cost_k = sum(costs) + k*x
		if k == 0:
			cost_min = cost_k
		else:
			cost_min = min(cost_min, cost_k)
			if cost_min != cost_k:
				break
		if cost_min < (k+1) *x:
			break
 
	return cost_min
n, x = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
print(solve(n,x,a))
### BUGGY CODE ###

k, s = list(map(int, input().split()))

count = 0

for p in range(k+1):
    for q in range(k+1):
        for r in range(k+1):
            t = p + q + r
            if t == s:
                count += 1

print(count)

### FIXED CODE ###

k, s = list(map(int, input().split()))
count = 0

for p in range(k+1):
    for q in range(k+1):
        r = s-p-q
        if r>=0 and r<=k:
            count += 1

print(count)
### BUGGY CODE ###

n, m = map(int, input().split())
price = sorted(list(map(int, input().split())))

while m >= 1:
    price[-1] //= 2
    m -= 1
    price.sort()
print(sum(price))

### FIXED CODE ###

import heapq
n, m = map(int, input().split())
price = list(map(lambda x: -x, map(int, input().split())))
heapq.heapify(price)

while m >= 1:
    a = (heapq.heappop(price) + 1) // 2
    heapq.heappush(price, a)
    m -= 1
    
print(sum(price) * (-1))
### BUGGY CODE ###

a, b, k = map(int, input().split())

ans = []

for i in range(b - a + 1):
    n = a + i
    if n <= a + k - 1 or n >= b - k + 1:
        ans.append(n)

ans.sort()
for i in range(len(ans)):
    print(ans[i])


### FIXED CODE ###

a, b, k = map(int, input().split())

ans = []

for i in range(k):
    if a + i <= b and a <= b - i:
        ans.append(a + i)
        ans.append(b - i)

#ans.sort()
ans = set(ans)

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

def main():
    import sys

    input = sys.stdin.readline

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

    b = [-1]
    for x in a:
        for i, top in enumerate(b):
            if top < x:
                b[i] = x
                break
        else:
            b.append(x)

    ans = len(b)

    print(ans)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())


### FIXED CODE ###

from bisect import bisect_left
from collections import deque

n = int(input())
a = tuple(int(input()) for _ in range(n))

d = deque()

for ai in a:
    p = bisect_left(d, ai)  # aa以上の最小値のindex
    if p == 0:
        d.appendleft(ai)
    else:
        d[p - 1] = ai
ans = len(d)
print(ans)
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
# result_list = [0]*n
result_count = 0

for i in range(n):
    for j in range(i):
        if p[i] > p[j]:
            # result_list[i] = 1
            result_count += 1
            break

# print(result_list.count(0))
print(n - result_count)


### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
# result_list = [0]*n
result = 1
com_val = p[0]

for i in range(1, n):
    if com_val < p[i]:
        continue
    else:
        result += 1
        com_val = p[i]

print(result)
### BUGGY CODE ###

A, B, Q = map(int, input().split())
s = [int(input()) for _ in range(A)]
t = [int(input()) for _ in range(B)]
x = [int(input()) for _ in range(Q)]
inf = 10 ** 18

s = [-inf] + s + [inf]
t = [-inf] + t + [inf]

def binsearch_l(seq, l, r, tar):
    if r - l < 2: return l
    #
    m = l + (r - l) // 2
    # print("##", l, r, (m, seq[m]), tar)
    if seq[m] <= tar:
        return binsearch_l(seq, m, r, tar)
    else:
        return binsearch_l(seq, l, m, tar)

ans_Q = [None] * Q
i_last = j_last = 0
for idx, x_tmp in sorted(enumerate(x), key=lambda x: x[1]):
    i_l = binsearch_l(s, i_last, A + 1, x_tmp)
    j_l = binsearch_l(t, j_last, B + 1, x_tmp)
    #
    ans = inf
    for i, j in ((i_l, j_l), (i_l + 1, j_l), (i_l, j_l + 1), (i_l + 1, j_l + 1)):
        if i < 1 or A < i: continue
        if j < 1 or B < j: continue
        ans_tmp_s = abs(x_tmp - s[i]) + abs(s[i] - t[j])
        ans_tmp_t = abs(x_tmp - t[j]) + abs(s[i] - t[j])
        ans_tmp = min(ans_tmp_s, ans_tmp_t)
        # print("#", x_tmp, s[i], t[j], ans_tmp)
        if ans > ans_tmp:
            ans = ans_tmp
    #
    i_last, j_last = i_l, j_l
    ans_Q[idx] = ans

for ansi in ans_Q: print(ansi)

### FIXED CODE ###

import sys, bisect
input = sys.stdin.readline
A, B, Q = map(int, input().split())
s = [int(input()) for _ in range(A)]
t = [int(input()) for _ in range(B)]
x = [int(input()) for _ in range(Q)]
inf = 10 ** 18

s = [-inf] + s + [inf]
t = [-inf] + t + [inf]

ans_Q = [None] * Q
i_last = j_last = 0
for idx, x_tmp in sorted(enumerate(x), key=lambda x: x[1]):
    i_l = max(0, bisect.bisect_left(s, x_tmp, lo=i_last) - 1)
    j_l = max(0, bisect.bisect_left(t, x_tmp, lo=j_last) - 1)
    # print("#", x_tmp, (i_l, s[i_l]), (j_l, t[j_l]))
    #
    ans = inf
    for i, j in ((i_l, j_l), (i_l + 1, j_l), (i_l, j_l + 1), (i_l + 1, j_l + 1)):
        if i < 1 or A < i: continue
        if j < 1 or B < j: continue
        ans_tmp_s = abs(x_tmp - s[i]) + abs(s[i] - t[j])
        ans_tmp_t = abs(x_tmp - t[j]) + abs(s[i] - t[j])
        ans_tmp = min(ans_tmp_s, ans_tmp_t)
        # print("#", x_tmp, s[i], t[j], ans_tmp)
        if ans > ans_tmp:
            ans = ans_tmp
    #
    i_last, j_last = i_l, j_l
    ans_Q[idx] = ans

for ansi in ans_Q: print(ansi)