Harryxun/stf_run huggingface dataset:
def bonus(i, l):
  if i in l:
    return 0
  else:
    return (len(l)+1)*(len(l)+1) - len(l)*len(l)

l = raw_input().split()
n = []
variety =[]
count = 0
for x in range(int(l[0])):
  n.append(map(lambda x: int(x),raw_input().split()))

for y in range(int(l[1])):
  max_saf = 0
  num = 0
  for i, x in enumerate(n):
    if max_saf < x[1] + bonus(x[0], variety):
      max_saf = x[1] + bonus(x[0], variety)
      num = i
    
  count = count + max_saf
  print(n[num])
  print(variety)
  print(max_saf)
  if not n[num][0] in variety:
  	variety.append(n[num][0])
  del n[num]
    
    
print (count)

### FIXED CODE ###

l = raw_input().split()

l = map(lambda x: int(x), l)
l.sort()

print l[0] * l[1] / 2
AtCoder Beginner Contest 146
 日本語 
 sawakee (Guest) 
コンテスト時間: 2019-11-24(日) 21:00 ~ 2019-11-24(日) 22:40 (100分)AtCoderホームへ戻る
 トップ
 問題
 質問
 提出
 提出結果
 順位表
 バーチャル順位表
 コードテスト
 解説
D - Coloring Edges on Tree / 
実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 
400
 点

問題文
N
 頂点の木 
G
 が与えられます。 頂点には 
1
 から 
N
 までの番号がついており、
i
 本目の辺は頂点 
a
i
 と頂点 
b
i
 を結んでいます。

G
 の辺を何色かで塗り分けることを考えます。 このとき、各頂点について、その頂点を端点に持つ辺の色がすべて相異なるようにしたいです。

上記の条件を満たす塗り分けの中で、使用する色の数が最小であるようなものを 
1
 つ構築してください。

制約
2
≤
N
≤
10
5
1
≤
a
i
<
b
i
≤
N
入力はすべて整数
与えられるグラフは木である
入力
入力は以下の形式で標準入力から与えられる。

N

a
1
 
b
1

a
2
 
b
2

⋮

a
N
−
1
 
b
N
−
1

出力
出力は 
N
 行からなる。

1
 行目に使用する色の数 
K
 を出力せよ。

i
+
1
 行目 
(
1
≤
i
≤
N
−
1
)
 に 
i
 番目の辺の色を表す整数 
c
i
 を出力せよ。ここで 
1
≤
c
i
≤
K
 でなければならない。

問題文中の条件を満たし、使用する色の数が最小であるような塗り分けが複数存在するときは、そのうちのどれを出力しても構わない。

入力例 1 
Copy
3
1 2
2 3
出力例 1 
Copy
2
1
2
入力例 2 
Copy
8
1 2
2 3
2 4
2 5
4 7
5 6
6 8
出力例 2 
Copy
4
1
2
3
4
1
1
2
入力例 3 
Copy
6
1 2
1 3
1 4
1 5
1 6
出力例 3 
Copy
5
1
2
3
4
5
言語
ソースコード
1
​
※ 512 KiB まで
※ ソースコードは「Main.拡張子」で保存されます




FacebookTwitterHatena共有
ルール 用語集
利用規約 プライバシーポリシー 個人情報保護方針 企業情報 よくある質問 お問い合わせ 資料請求
Copyright Since 2012 ©AtCoder Inc. All rights reserved.
 ページトップ

### FIXED CODE ###

from queue import deque

n=int(input())
ab = [list(map(int,input().split()))for i in range(n-1)]
g = [[]for i in range(n)]
for i,j in ab:
    g[i-1].append(j-1)
ans = {}
banColor = [-1]*n

q = deque([])
q.append(0)
ma = 0

while q:
    nord = q.popleft()
    offset = 0
    for idx,value in enumerate(g[nord]):
        if idx ==banColor[nord]:
            offset += 1
        ans[(nord,value)]= idx + offset
        banColor[value] = idx+offset
        q.append(value)
        ma = max(ma,idx+offset+1)
print(ma)
for i,j in ab:
    print(ans[(i-1,j-1)]+1)
W = input()
lett = list(W)
numlist = []
for i in lett:
    num = lett.count(i)
    numlist += [num]
jud = []
for i in numlist:
    if i%2 == 0:
        jud += ['Yes']
    else:
        jud += ['No']

anslist = [x for x in set(jud) if jud.count(x) > 1]

ans = anslist[0]

print(ans)

### FIXED CODE ###

mojiretsu = input()
lett = list(mojiretsu)
numlist = []
for i in lett:
    num = lett.count(i)
    numlist += [num]
jud = []
for i in numlist:
    if i%2 == 0:
        jud += ['Yes']
    else:
        jud += ['No']

anslist = [x for x in set(jud) if jud.count(x) > 1]
anslisT = [x for x in jud if jud.count(x) == 1]

if anslist == ['Yes']:
    print('Yes')
elif anslisT == ['Yes']:
    print('Yes')
else:
    print('No')
X = int(input())
for i1 in range(1000000):
  if i1 * 100 <= X:
    for i2 in range(1000000):
      if i1 * 100 + i2 * 101 <= X:
        for i3 in range(1000000):
          if i1 * 100 + i2 * 101 + i3 * 102 <= X:
            for i4 in range(1000000):
              if i1 * 100 + i2 * 101 + i3 * 102 + i4 * 103 <= X:
                for i5 in range(1000000):
                  if i1 * 100 + i2 * 101 + i3 * 102 + i4 * 103 + i5 * 104 <= X
                    for i6 in range(1000000):
                      if 100 * i1 + 101 * i2 + 102 * i3 + 103 * i4 + 104 * i5 + 105 * i6 == X:
                        print("1")
                      else:
                        print("0")
  


### FIXED CODE ###

X = int(input())
a = X // 100
r = X % 100
if r <= 5 * a:
  print("1")
else:
  print("0")
N = int(input()
V = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]
        
print(
  sum(
    max(v - c, 0) for v, c in zip(V,C)
  )
)

### FIXED CODE ###

N = int(input())
V = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]
            
print(
  sum(
    max(v - c, 0) for v, c in zip(V,C)
  )
)
S = input()

nums = []
for s in S:
    nums.append(int(s))

count = 0
i = 0
while i < len(nums)-1:
    if nums[i] != nums[i+1]:
        nums.pop(i+1)
        nums.pop(i)
        count += 1
        i -= 1
        continue
    i += 1

print(count*2)


### FIXED CODE ###

S = input()

nums = []
for s in S:
    nums.append(int(s))

count = 0
i = 0
while i < len(nums)-1:
    if nums[i] != nums[i+1]:
        nums.pop(i+1)
        nums.pop(i)
        count += 1
        if i != 0:
            i -= 1
        continue
    i += 1

print(count*2)
import sys

sys.setrecursionlimit(100000)

class Solver(object):
    def __init__(self,N:int,W:int,values:list,weights:list):
        self.N = N   ## MAX number of item
        self.values = values  ## list of item value
        self.weights = weights ## list of item weight
        self.dp = [[None for _ in range(W+1)] for _ in range(N+1)] ## memorize the result

    ## i番目以降から重さがj以下になるように選ぶ時に価値が最大になるようにする。
    def solve(self,i:int,j:int) -> int:
        if self.dp[i][j] != None:
            return self.dp[i][j]
        if i == self.N:
            res = 0
        if j < self.weights[i]:
            res = self.solve(i+1,j)
        else:
            res = max(self.solve(i+1,j),self.solve(i+1,j-self.weights[i])+self.values[i])
        self.dp[i][j] = res
        return res

def main():
    N,W = [int(i) for i in input().split()]
    items = [[int(i) for i in input().split()] for _ in range(N)]
    weights = [item[0] for item in items]
    values = [item[1] for item in items]
    solver = Solver(N,W,values,weights)
    ans = solver.solve(0,W)
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

class Solver():
    def __init__(self, N, W, items):
        self.N = N
        self.W = W
        self.items = items

    def solve(self):
        dp = [[0 for _ in range(self.W+1)] for _ in range(self.N+1)]
        for i in range(self.N):
            for w in range(self.W+1):
                if w - self.items[i][0] >= 0:
                    dp[i+1][w] = max(dp[i+1][w], dp[i][w - self.items[i][0]] + self.items[i][1])

                dp[i + 1][w] = max(dp[i + 1][w], dp[i][w])
        return dp[self.N][self.W]


def main():
    N, W = [int(i) for i in input().split()]
    items = [[int(i) for i in input().split()] for _ in range(N)]
    solver = Solver(N, W, items)
    print(solver.solve())


if __name__ == "__main__":
    main()
N = int(input())


A = list(map(int,input().split()))
ok = [0]*pow(10,5)
Q = int(input())

li = [list(map(int,input().split())) for i in range(Q)]

f):
    ok[A[i]]+=1
memo1=0
memo2=0

S = sum(A)
for i in range(Q):

    S+=ok[li[i][0]]*(li[i][1]-li[i][0])
    print(S)
    a = ok[li[i][0]]
    ok[li[i][1]]+=a
    ok[li[i][0]]=0
    
    if max(ok)==N:
        memo1=i
        memo2=ok.index(N)
        break



for i in range(memo1+1,Q):
    if li[i][0]==memo2:
        print(N*li[i][1])
        memo2=li[i][1]
    else:
        print(memo2*N)

### FIXED CODE ###

N = int(input())


A = list(map(int,input().split()))
ok = [0]*pow(10,6)
Q = int(input())

li = [list(map(int,input().split())) for i in range(Q)]

for i in range(N):
    ok[A[i]]+=1
memo1=0
memo2=0

S = sum(A)
for i in range(Q):

    S+=ok[li[i][0]]*(li[i][1]-li[i][0])
    print(S)
    a = ok[li[i][0]]
    ok[li[i][1]]+=a
    ok[li[i][0]]=0
if 1<=A<=100 and 1<=B<=100:
  print(A*B)

### FIXED CODE ###

str=input()
arr=str.split(' ')
A=int(arr[0])
B=int(arr[1])
if 1<=A<=100 and 1<=A<=100:
  print(A*B)
N,K = map(int,input().split())
tmp = K/N
q = 1
p = 2 ** 100
while p/q >2:
    qp = q*2
    if qp > tmp:
        p = qp
    else:
        q = qp
for i in range(N,0,-1):
    ans = i*q
    if ans < K:
        q*=2
    res+= float(1)/q
print(res/N)

### FIXED CODE ###

n,k = map(int, input().split())
s = 0
for i in range(1000):
    if 2**i <= k < 2**(i+1):
        s = i+1
        break
t = 0
for i in range(n):
    if s == 0 and k<=n:
        t+=1
        
    elif k<=(i+1) *2**s and k> (i+1) *2**(s-1):
        t+=1/(2**s)
    else:
        s-=1
        t+=1/(2**s)
print(t/n)
import math

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

ans = -1

def f(b, n):
  if n < b:
    return n
  else:
    return f(b, n//b) + n % b
    
  

if n == s:
  ans = n+1
  
else:
  rootn = int(math.sqrt(n))
  for b in range(2, rootn):
    if s == f(b, n):
      ans = b
      break
  else:
    for p in range(1, rootn):
      b = (n-s)//p + 1
      if s == p*b + n%b:
        ans = b
        break

print(ans)

### FIXED CODE ###

import math

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

ans = []

def f(b, n):
  if n < b:
    return n
  else:
    return f(b, n//b) + n % b

if n == s:
  ans.append(n+1) 
  
elif n < s:
  ans.append(-1)
  
else:
  rootn = int(math.sqrt(n))
  for b in range(2, rootn+2):
    if s == f(b, n):
      ans.append(b)
      break
      
  for p in range(1, rootn):
    b = (n-s)//p + 1
    if s == p + n%b:
      ans.append(b)
      
if not ans:
  ans.append(-1)

print(min(ans))
s=list(input())
divide=["dream","erase","eraser","dreamer"]
def dfs(n):
        if n==len(s):
                return True
        for i in divide:
                if n+len(i)<=len(s):
                        if "".join(s[n:n+len(i)])==i:
                                if dfs(n+len(i)):
                                        return True

        return False
print("YES") if dfs(0) else print("NO")


### FIXED CODE ###

s=input().replace("eraser",",").replace("erase",",").replace("dreamer",",").replace("dream",",").replace(",","")
print("YES" if s=="" else "NO")
N,M = map(int,input().split())
A = sorted(map(int, input().split()))
ans = N-sum(A)
if = N-sum(A) >= 0:
  print(ans)
else:
  print('-1')

### FIXED CODE ###

N,M = map(int,input().split())
A = sorted(map(int, input().split()))
ans = N-sum(A)
if N-sum(A) >= 0:
  print(ans)
else:
  print('-1')
n = input()
s = list(input())

A_index = [i for i, x in enumerate(s) if x == 'A']

count = 0
for j in A_index :
  if s[j+1] == 'B' :
    if s[j+2] == 'C' :
      count += 1

print(count)


### FIXED CODE ###

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

A_index = [i for i, x in enumerate(s) if x == 'A']

count = 0
for j in A_index :
  if j != n-1 :
    if s[j+1] == 'B' :
      if j != n-2 :
        if s[j+2] == 'C' :
          count += 1

print(count)
n = int(input())
s = input()
     
if s[:n/2] == s[n/2:]:
	print("Yes")
else:
	print("No")

### FIXED CODE ###

n = int(input())
s = input()
     
if s[:n//2] == s[n//2:]:
	print("Yes")
else:
	print("No")
x, y = map(int, input().split())

count = 0
if y % 2 == 0:
	count = x * (y // 2)
elif y == 1
	count = 1
else:
	count = x * ((y + 1) // 2) - (x // 2)

print(count)

### FIXED CODE ###

x, y = map(int, input().split())

count = 0
if y == 1 or x == 1:
	count = 1
elif y % 2 == 0:
	count = x * (y // 2)
else:
	count = x * ((y + 1) // 2) - (x // 2)

print(count)
n=int(input())
st=str(n)

sm = 0
for i in st:
  sm+=int(i)
if n%sm==0:
  print("Yes")
else
  print("No")

### FIXED CODE ###

n=int(input())
st=str(n)

sm = 0
for i in st:
  sm+=int(i)
if n%sm==0:
  print("Yes")
else:
  print("No")
S = input()
Temp = ''

def Tcmp(T, moji):
	T += moji
	
	if (S == T):
		return 1
	if len(T) > len(S):
		return 0
	
	if (moji == "dream"):
		return max(Tcmp(T,""),Tcmp(T,"er"))
	elif(moji == "eras"):
		return max(Tcmp(T,"e"),Tcmp(T,"er"))
	else:
		return max(Tcmp(T,"dream"),Tcmp(T,"eras"))

if(Tcmp(Temp,"")):
	print("YES")
else:
	print("NO")

### FIXED CODE ###

#ABC 049 C
S = input()
T = ''
S = S[::-1]
words = ["dream","dreamer","erase","eraser"]
rev_words = [w[::-1] for w in words]

flag = False
i=0
while(1):
	for w in rev_words:
		s = S[i:i+len(w)]
		if s == w:
			flag = True
			T += w
			i += len(w)
			break
	if T == S:
		ans = "YES"
		break
	if flag == False:
		ans = 'NO'
		break
	flag = False

print(ans)
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    X = list(map(int, input().split()))

    for i in range(n):
        if X[i] >= 0:
            ori = i
            X.insert(i, 0)
            break
    else:
        ori = n - 1

    res = f_inf
    start = max(0, ori - k)
    end = min(n - k + 1, ori + 1)
    for j in range(start, end):
        left = abs(X[j]) * 2 + abs(X[j + k])
        right = abs(X[j]) + abs(X[j + k]) * 2
        res = min(res, min(left, right))
    print(res)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

n, k = map(int, input().split())
x = list(map(int, input().split()))

if x[0] >= 0:
    print(x[k - 1])
    exit()
elif x[n - 1] < 0:
    print(abs(x[n - k]))
    exit()
else:
    for i in range(n):
        if x[i] >= 0:
            ori = i
            break

f_inf = float("inf")
res = f_inf
for i in range(max(ori - k, 0), min(ori + k, n) - k + 1):
    time = min(abs(x[i + k - 1] - x[i]) + abs(x[i + k - 1]), abs(x[i]) + abs(x[i + k - 1] - x[i]))
    res = min(res, time)

print(res)
from math import sqrt
def p(n):
    l = list(range(2,n+1))
    p = 2
    i = 0
    p = l[i]
    while p < sqrt(n):
        pl = len(l)
        l = list(filter(lambda n: n%p != 0 or n == p,l))
        i += 1
        p = l[i]
    return len(l)

from sys import stdin
for i in stdin:
    print(p(int(i)))

### FIXED CODE ###

from math import sqrt,floor
from sys import stdin

def cntPrime(n):
    mx = sqrt(n)
    if n % 2 == 0:
      l = [0, 1] + [1, 0] * (int(n/2) - 1)
    else:
      l = [0, 1] + [1, 0] * (int(n/2) - 1) + [1]
    c = 3
    while c < mx:
        for k in range(c*2, n+1, c):
            l[k-1] = 0
        c = l[(c+1):].index(1) + c +2
        while c % 2 == 0:
            c = l[(c+1):].index(1) + c +2
    return l
t = cntPrime(1000000)
for n in stdin:
    n = int(n)
    print(sum(t[:n]))
n=input()
 a=map(int,raw_input().split())
 a=reverse
 print a

### FIXED CODE ###

n=input()
a=map(int,raw_input().split())
a.reverse()

for i in a:
    print i,
input()
ans = 1
n = int(1e18)
a = list(map(int, input().strip().split()))
for i in a:
    ans *= i
    if ans > n:
        ans = -1
        break
if 0 in ans: ans = 0
print(ans)


### FIXED CODE ###

input()
ans = 1
n = int(1e18)
a = list(map(int, input().strip().split()))
for i in a:
    ans *= i
    if ans > n:
        ans = -1
        break
if 0 in a: ans = 0
print(ans)
import math
def main():
    with open('in.csv', 'r') as r:
        args = list(r.readlines())
    N = int(args[0])
    use = math.ceil(N/1000)
    print(1000*use - N)
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import math
def main():
    N = int(input().rstrip())
    use = math.ceil(N/1000)
    print(1000*use - N)
    
if __name__ == "__main__":
    main()
from collections import deque
import sys
sys.setrecursionlimit(20000000)

N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
routes = [[] for _ in range(N)]

for i in range(len(ab)):
    routes[ab[i][0]-1].append([ab[i][1]-1, i])
    routes[ab[i][1]-1].append([ab[i][0]-1, i])

route_color = [-10e+10 for _ in range(len(ab))]

route_num = [0]*N
max_route = 0
for i in range(N):
    num = len(routes[i])
    route_num[i] = num
    if max_route < num:
        max_route = num

seen = [False for _ in range(N)]

def function(num):
    seen[num] = True
    colors = set(range(max_route))
    for route in routes[num]:
        if route_color[route[1]] != -10e+10:
            colors.remove(route_color[route[1]])
        else:
            route_color[route[1]] = colors.pop()
        if seen[route[0]] == False:
            function(route[0])
    return
        
function(0)
print(max_route)
for color in route_color:
    print(color+1)

### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(20000000)

N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
routes = [[] for _ in range(N)]

for i in range(len(ab)):
    routes[ab[i][0]-1].append([ab[i][1]-1, i])
    routes[ab[i][1]-1].append([ab[i][0]-1, i])

route_color = [-10e+10 for _ in range(len(ab))]

route_num = [0]*N
max_route = 0
for i in range(N):
    num = len(routes[i])
    route_num[i] = num
    if max_route < num:
        max_route = num

seen = [False for _ in range(N)]

def function(num,pre_color):
    color_num = -1
    for route in routes[num]:
        color_num += 1
        if color_num == pre_color:
            color_num+=1
        if route_color[route[1]] != -10e+10:
            color_num-=1
            pass
        else:
            route_color[route[1]] = color_num
            
        if seen[route[0]] == False:
            seen[route[0]] = True
            function(route[0],route_color[route[1]])
    return

function(0,-1)
print(max_route)
for color in route_color:
    print(color+1)
N,M =map(int,input().split())
if M>0:
    a = [0]*M
    for i in range(M):
        a[i] = int(input())

ans = int(1)

A = [0]*(M+1)
A[0]=N
if M!=0:
    A[0] = a[0] - 1
    A[M] = N - a[M-1]-1
    for i in range(M-1):
        A[i+1] = a[i+1] - a[i]- 2
        if A[i+1]==-1:
            ans = 0


SA =[0]*N
SA[0] = int(1)
SA[1] = int(1)
if N>2:
    for i in range(N - 2):
        SA[i + 2] = SA[i + 1] + SA[i]
        SA[i + 2] = SA[i + 2] % 1000000007

for i in range(M+1):
    if A[i]>=0:
        ans *= SA[A[i]]
        ans = ans%1000000007


print(ans)



### FIXED CODE ###

def examC():
    N, M = LI()
    A = [I() for _ in range(M)]
    A.append(N+1)
    fib = [1]*(N+2)
    for i in range(1,N):
        fib[i+2] = fib[i+1] + fib[i]
    fib[0] = 0
#    print(fib)
    ans = fib[A[0]]%mod
    for i in range(M):
        ans *= fib[A[i+1]-A[i]-1]
        ans %=mod
    print(ans)
    return

def examD():
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examC()
8 3

### FIXED CODE ###

t,x = [int(i) for i in input().split()]
print(t/x)
import math
x,y = map(int,input().split())
print(math.gcd(x, y))

### FIXED CODE ###

import fractions
x,y = map(int,input().split())
print(x*y//fractions.gcd(x,y))
n,m = map(int(input().spit()))
L = []
R = []

for i in range(m):
	l,r = map(int(input().spit()))
	L.append(l)
	R.append(r)

ans = min(R) - max(L) + 1

if ans >0:
	print(ans)
else:
	print(0)

### FIXED CODE ###

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

p=[]
q=[]

for i in range(m):
    l,r=map(int,input().split())
    p.append(l)
    q.append(r)

p1=max(p)
q1=min(q)

if q1>=p1:
    print(q1-p1+1)
else:
    print(0)
from statistics import mean
import math
N = int(input())
*A, = map(int, input().split())
B = [A[i]-i for i in range(N)]
bm = math.median(B)
K = [x - bm for x in B]
KZ = [abs(x) for x in K]
Z = sum(KZ)
for i in range(200):
    C = [abs(x-i+100) for x in K]
    Z = min([sum(C),Z])
print(int(Z))

### FIXED CODE ###

from statistics import median
import math
N = int(input())
*A, = map(int, input().split())
B = [A[i]-i for i in range(N)]
b = median(B)
bm = math.floor(b)
K = [x - bm for x in B]
KZ = [abs(x) for x in K]
Z = sum(KZ)
for i in range(20):
    C = [abs(x-i+10) for x in K]
    Z = min([sum(C),Z])
print(int(Z))
N,K=map(int,input().split())

class SegTree:
    """ segment tree with point modification and range product. """
    # # https://yukicoder.me/submissions/452850
    def __init__(self, N, data_f = min, data_unit=1<<30):
        self.N = N
        self.data_f = data_f
        self.data_unit = data_unit
        self.data = [self.data_unit] * (N + N)

    def build(self, raw_data):
        data = self.data
        f = self.data_f
        N = self.N
        data[N:] = raw_data[:]
        for i in range(N - 1, 0, -1):
            data[i] = f(data[i << 1], data[i << 1 | 1])

    def set_val(self, i, x):
        data = self.data
        f = self.data_f
        i += self.N
        data[i] = x
        while i > 1:
            data[i >> 1] = f(data[i], data[i ^ 1])
            i >>= 1

    def fold(self, L, R):
        """ compute for [L, R) """
        vL = vR = self.data_unit
        data = self.data
        f = self.data_f
        L += self.N
        R += self.N
        while L < R:
            if L & 1:
                vL = f(vL, data[L])
                L += 1
            if R & 1:
                R -= 1
                vR = f(data[R], vR)
            L >>= 1
            R >>= 1
        return f(vL, vR)
      
seg = SegTree(N,max,0)
seg.build([0]*N)
*A,=[int(input()) for _ in range(N)]
for i in range(N):
  a = A[i]
  tmp = seg.fold(max(0,a-K),min(N,a+K+1))
  seg.set_val(a,tmp+1)

print(seg.fold(0,N))

### FIXED CODE ###

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

class SegTree:
    """ segment tree with point modification and range product. """
    # # https://yukicoder.me/submissions/452850
    def __init__(self, N, data_f = min, data_unit=1<<30):
        self.N = N
        self.data_f = data_f
        self.data_unit = data_unit
        self.data = [self.data_unit] * (N + N)

    def build(self, raw_data):
        data = self.data
        f = self.data_f
        N = self.N
        data[N:] = raw_data[:]
        for i in range(N - 1, 0, -1):
            data[i] = f(data[i << 1], data[i << 1 | 1])

    def set_val(self, i, x):
        data = self.data
        f = self.data_f
        i += self.N
        data[i] = x
        while i > 1:
            data[i >> 1] = f(data[i], data[i ^ 1])
            i >>= 1

    def fold(self, L, R):
        """ compute for [L, R) """
        vL = vR = self.data_unit
        data = self.data
        f = self.data_f
        L += self.N
        R += self.N
        while L < R:
            if L & 1:
                vL = f(vL, data[L])
                L += 1
            if R & 1:
                R -= 1
                vR = f(data[R], vR)
            L >>= 1
            R >>= 1
        return f(vL, vR)

A=[int(input()) for _ in range(N)]
seg = SegTree(300005,max,0)
seg.build([0]*300005)
for i in range(N):
  a = A[i]
  tmp = seg.fold(max(0,a-K),min(300005,a+K+1))
  seg.set_val(a,tmp+1)

print(seg.fold(0,300005))
a, b = map(int, input().split())

ans = [1]

def cf(x1,x2):
    cf=[]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf
 
cflist = cf(a,b)
 
import fractions
import itertools
 
for i in cflist:
        ans.append(i)
        for j in itertools.combinations(ans, 2):
                if 1 == fractions.gcd(j[0],j[1]):
            		pass
                else:
                        ans.pop()
                        break
 
print(len(ans))

### FIXED CODE ###

def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(n)
  return table

a, b = map(int, input().split())
import fractions
print(len(set(prime_decomposition(fractions.gcd(a,b))))+1)
def main():
    i = list(map(int, input().split()))
    n = i[0]

    if not (1 <= n and n <= 10**5):
        return

    num = 0
    for j in range(n):
        if(len(n) % 2 != 0):
            num += 1

    print(num)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    i = list(map(int, input().split()))
    n = i[0]

    if not (1 <= n and n <= 10**5):
        return

    num = 0
    for j in range(n):
        if(len(str(j+1)) % 2 != 0):
            num += 1

    print(num)

if __name__ == "__main__":
    main()
a,b,x=map(int,input().split())
print(b//x - (a-1)//x)

### FIXED CODE ###

a,b,s=input().split()
print(list(a)[0]+list(b)[0]+list(s)[0])
(a, b) = map(int, input().split())

bb = int(b * 100)
abb = a * bb
ans = abb // 100
print(ans)

### FIXED CODE ###

words = input().split()
a = int(words[0])
b = float(words[1])
bb = round(b * 100)
abb = a * bb
ans = abb // 100
print(ans)
N=int(input)

print(sum(i for i in range(1,N+1) if i%3==0 or  i%5==0))

### FIXED CODE ###

N=int(input())

print(sum(i for i in range(1,N+1) if i%3 and  i%5))