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

# Input Part
N,K = map(int,input().split())
A = [int(input()) for _ in range(N)]

Amax = max(A)
# 初期化
n = 1
while n < Amax:
    n *= 2
#print(n)
# セグメント木を持つグローバル配列
# すべての値をINT_MAXに 
INF = 0
dat = [INF] * (2*n-1)

#k番目の値(0-indexed)をaに変更
def update(k,a):
    # 葉の節点
    k += n - 1
    dat[k] = a
    # 登りながら更新
    while k > 0:
        k = int((k - 1) / 2)
        dat[k] = max(dat[k * 2 + 1], dat[k * 2 + 2])

# [a,b]の最小値を求める
# 後ろのほうの引数は、計算の簡単のための引数。
# kは節点の番号、1, rはその節点が[1, r)に対応づいていることを表す。
# したがって、外からはquery(a, b, 0, 0, n)として呼ぶ。
def query(a,b,k,l,r):
    # [a,b]と[1, r)が交差しなければ、INT_MAX
    if a==b:
        return dat[n+a-1]
    
    if r <= a or b <= l:
        return INF
    # [a, b]が[1, r]を完全に含んでいれば、この節点の値 
    if a <= l and r <= b:
        return dat[k]
    # そうでなければ、2つの子の最小値
    else:
        vl = query(a,b,k * 2 + 1,l, int((l + r) / 2))
        vr = query(a,b, k * 2 + 2, int((l + r) / 2), r)
    
    return max(vl,vr)

def main():
    for i in range(N):
        tmin = max(0,A[i]-K)
        tmax = min(Amax,A[i]+K)+1
        update(A[i],query(tmin,tmax,0,0,n)+1)
        #print(dat)
    print(dat[0])
main()


### FIXED CODE ###

# Input Part
N,K = map(int,input().split())
A = [int(input()) for _ in range(N)]

Amax = 3*10**5

# N: 処理する区間の長さ
N0 = 2**(Amax-1).bit_length()
INF = 0
data = [INF]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])
# 区間[l, r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])

        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

def main():
    for i in range(N):
        tmin = max(0,A[i]-K)
        tmax = min(Amax,A[i]+K)+1
        update(A[i],query(tmin,tmax)+1)
        #print(data)
    print(data[0])
main()
### BUGGY CODE ###

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

L = [0] * N
for i in range(N):
    L[i] = (p[i] + 1) * p[i] / (2 * p[i])

x = 0
for i in range(N - K + 1):
    x = max(x, sum(L[i:i+K]))

print(x)

### FIXED CODE ###

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

L = [0] * N
for i in range(N):
    L[i] = (p[i] + 1) * p[i] / (2 * p[i])

L2 = [0] * (N + 1)
for i in range(N):
    L2[i+1] = L2[i] + L[i]

x = 0
for i in range(N - K + 1):
    x = max(x, L2[i+K] - L2[i])

print(x)
### BUGGY CODE ###



def solve():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    color_list = [-1]
    min_A = min(color_list)
    for a in A:
        if min_A < a:
            for i in range(len(color_list)):
                tag = color_list[i]
                if tag < a:
                    color_list[i] = a
                    if tag == min_A:
                        min_A = min(color_list)
                    break
        else:
            color_list.append(a)
            min_A = a
    # print(color_list)
    print(len(color_list))


if __name__ == '__main__':
    solve()


### FIXED CODE ###

"""
提出 #6475942 を参考に作成
"""

import bisect


def solve():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    color_list = [A[-1]]
    for a in reversed(A[:-1]):
        # a より大きい数の中で一番小さい数の場所を取得する
        c = bisect.bisect_left(color_list, a + 1)
        if c == len(color_list):
            color_list.append(a)
        else:
            color_list[c] = a
    print(len(color_list))


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

import sys
import fractions
input = sys.stdin.readline
A, B = (int(i) for i in input().split())

gcd = fractions.gcd(A, B)
temp = gcd
count = 1
for i in range(2, gcd//2+1):
    if temp%i == 0:
        cnt = 0
        while temp%i ==0:
            cnt +=1
            temp //= i
        count +=1
if temp != 1:
    count +=1

print(count)


### FIXED CODE ###

import sys
input = sys.stdin.readline
A, B = (int(i) for i in input().split())

cd = [1]
factors = {}
temp = A
for i in range(2, int(-(-A**0.5//1))+1):
    if temp%i==0:
        cnt = 0
        while temp%i==0:
            #print(temp)
            cnt+=1
            temp //= i
        factors[i] = 1
if temp!=1:
    factors[temp] = 1
#print(factors)
temp = B
for i in range(2, int(-(-B**0.5//1))+1):
    if temp%i==0:
        cnt = 0
        while temp%i==0:
            cnt+=1
            temp //= i
        #print(i)
        if i in factors:
            factors[i] = 2
        else:
            pass
if temp!=1:
    if temp in factors:
        factors[temp] = 2
#print(factors)
count = 1
for k, v in factors.items():
    if v==2:
        count+=1

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

x,y,z,n = map(int, input().split())
a = sorted(list(map(int, input().split())),reverse = True)
b = sorted(list(map(int, input().split())),reverse = True)
c = sorted(list(map(int, input().split())),reverse = True)
d = []
for i,i1 in enumerate(a):
  for j,j1 in enumerate(b):
    for k,k1 in enumerate(c):
      if (i+1) * (j+1) * (k+1) <= n:
        d.append(i1 + j1 + k1)
d.sort(reverse = True)
for i in d[:n]:
  print(i)

### FIXED CODE ###

x,y,z,n = map(int, input().split())
a = sorted(list(map(int, input().split())),reverse = True)
b = sorted(list(map(int, input().split())),reverse = True)
c = sorted(list(map(int, input().split())),reverse = True)
d = []
for i,i1 in enumerate(a):
  for j,j1 in enumerate(b):
    if (i+1)*(j+1) <= n:
      for k,k1 in enumerate(c):
        if (i+1) * (j+1) * (k+1) <= n:
          d.append(i1 + j1 + k1)
        else:
          break
    else:
      break
d.sort(reverse = True)
for i in d[:n]:
  print(i)
### BUGGY CODE ###

import sys
import heapq
from collections import deque

# sys.setrecursionlimit(100001)
INF = sys.maxsize


# ===CODE===
def main():
    n = input()

    l = len(n)
    ans = 0
    for i in range(l):
        for j in range(i+3, l+1):
            s = n[i:j]
            if int(s)%2019==0:
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    s = input()

    cnt = [0 for _ in range(2019)]
    cnt[0] += 1
    dec = 1
    num = 0
    for i in reversed(s):
        num += int(i) * dec
        num %= 2019
        dec *= 10
        dec %= 2019
        cnt[num] += 1

    ans = 0
    for c in cnt:
        ans += c * (c - 1) // 2

    print(ans)


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

import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
town = [[] for _ in range(N)]
for i in range(Q):
    place, year = map(int, input().split())
    tmp = [0,0]
    tmp[0] = year
    tmp[1] = i
    town[place-1].append(tmp)
 
# print(town)
 
ans = []
 
for item in town:
    index = town.index(item)
    # print(item)
    item.sort()
    index += 1
    index = str(index)
    while len(index) < 6:
        index = '0' + index
    for i in range(len(item)):
        num = i + 1
        num = str(num)
        while len(num) < 6:
            num = '0' + num
        xxx = index + num
        tmp = []
        tmp.append(item[i][1])
        tmp.append(xxx)
        ans.append(tmp)
 
ans.sort()
for item in ans:
    print(item[1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
town = [[] for _ in range(N)]
for i in range(Q):
    place, year = map(int, input().split())
    town[place-1].append([year,i])

# print(town)

ans = []
k = 0
for item in town:
    index = k
    # index = town.index(item)
    # print(item)
    item.sort()
    index = str(index+1)
    while len(index) < 6:
        index = '0' + index
    for i in range(len(item)):
        num = str(i+1)
        while len(num) < 6:
            num = '0' + num
        xxx = index + num
        ans.append([item[i][1],xxx])
    k += 1

ans.sort()
for item in ans:
    print(item[1])
### BUGGY CODE ###

n = int(input())
sl = input()
# sl = [s[i] for i in range(len(s))]

ans = 0
for i in range(1, n+1):
    for j in range(i, n+1):
        for k in range(j, n+1):
            if sl[i-1] != sl[j-1] and sl[j-1] != sl[k-1] and sl[k-1] != sl[i-1]:
                if j-i != k-j:
                    ans += 1

print(ans)

### FIXED CODE ###

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

r = []
g = []
b = []
for i in range(len(s)):
    t = s[i]
    if t == 'R':
        r.append(i+1)
    elif t == 'G':
        g.append(i+1)
    else:
        b.append(i+1)

ans = len(r) * len(g) * len(b)

for i in range(1, int((n-1)/2)+1):
    for j in range(n-i-i, 0, -1):
        if s[j-1] != s[j+i-1] and s[j+i-1] != s[j+i+i-1] and s[j+i+i-1] != s[j-1]:
            ans -= 1

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

import numpy as np
import statistics
H,W,M = map(int, input().split())
S = np.array([list([int(s) for s in input().split()]) for i in range(M)]) - 1
Hlist = S[:,0]
Wlist = S[:,1]
Hunique,Hcount = np.unique(Hlist, return_counts=True)
Wunique,Wcount = np.unique(Wlist, return_counts=True)
Hmode = np.array(list(Hunique[Hcount == max(Hcount)]))
Wmode = np.array(list(Wunique[Wcount == max(Wcount)]))
judge = -1
for h in Hmode:
  for w in Wmode:
    c = True
    for m in range(M):
      if (S[m,0] == h and S[m,1] == w):
        c = False
    if c:
      judge = 0
print(max(Hcount) + max(Wcount) + judge)

### FIXED CODE ###

def calc():
  H,W,M = map(int, input().split())
  s = []
  hcount = [0]*H
  wcount = [0]*W
  for m in range(M):
    h,w = map(int, input().split())
    h = h - 1
    w = w - 1
    hcount[h] = hcount[h] + 1
    wcount[w] = wcount[w] + 1
    s.append((h,w))
  hmax = max(hcount)
  wmax = max(wcount)
  hmode = [h for h, x in enumerate(hcount) if x == hmax]
  wmode = [w for w, y in enumerate(wcount) if y == wmax]
  s = tuple(s)
  S = set(s)
  for h in hmode:
    for w in wmode:
      if ((h,w) not in S):
        return hmax + wmax
  return hmax + wmax - 1
  
if __name__ == '__main__':
    print(calc())
### BUGGY CODE ###

from itertools import combinations

s = input()
n = len(s)
ap = list(range(1, n))

set_s = set()


def check(k):
    if k == 1:
        return True

    rtn = False
    for v in combinations(ap, k - 1):
        can = True
        x_past = 0
        w_past = ""

        for x in v:
            w = s[x_past:x]
            if w == w_past:
                can = False
                break
            x_past = x
            w_past = w
        w_last = s[v[-1] :]
        if w == w_last:
            can = False

        if can is True:
            rtn = True
            break

    return rtn


low = 1
high = n
while low <= high:
    mid = (low + high) // 2
    if check(mid):
        low = mid + 1
    else:
        high = mid - 1

print(min(high, low))


### FIXED CODE ###

s = input()

count = 0
j = 0
past_str = ""

for i in range(len(s)):
    now_str = s[j : i + 1]
    if now_str != past_str:
        count += 1
        j = i + 1
        past_str = now_str

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

n=int(input())
s=input()
ans=[0]*n
for i in range(n):
	for j in range(i):
		if s[j]=='W': ans[i]+=1
	for k in range(i,n):
		if s[k]=='E': ans[i]+=1
print(min(ans))

### FIXED CODE ###

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

num_w=0
num_e=s[1:].count('E')
ans=num_e
for i in range(n):
	if i == 0:
		continue
	if s[i]=='E':
		num_e-=1
	if s[i-1]=='W':
		num_w+=1
	ans=min(ans, num_w+num_e)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC113 C

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,m = LI()
lst = [[] for _ in range(n)]
py = [LI() for _ in range(m)]
for i in range(m):
    p,y = py[i]
    lst[p-1].append(y)
for i in lst:
    i.sort()
for i in range(m):
    p,y = py[i]
    s1 = '00000' + str(p)
    s2 = '00000' + str(lst[p-1].index(y)+1)
    ans = s1[-6:] + s2[-6:]
    print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
#ABC113 C

from operator import itemgetter
n,m = map(int,input().split())
py = [list(map(int,input().split())) for _ in range(m)]
for i in range(m):
    py[i].append(i)
py.sort(key = itemgetter(1))
py.sort(key = itemgetter(0))

x = py[0][0]
c = 0
for i in range(m):
    if x != py[i][0]:
        c = 1
        x = py[i][0]
    else:
        c += 1
    py[i].append(c)
py.sort(key = itemgetter(2))
for i in range(m):
    front = '00000'+str(py[i][0])
    back = '00000'+str(py[i][3])
    print(front[-6:]+back[-6:])
### BUGGY CODE ###

import copy
import sys
input = sys.stdin.readline

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

    ans = {}
    for i in lis:
        if i in ans:
            ans[i] += 1
        else:
            ans[i] = 1

    for j in range(n):
        ans_t = copy.copy(ans)
        ans_t[lis[j]] -= 1
        su = 0
        for k in ans_t.values():
            su += (k - 1) * k // 2
        print(su)
if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import Counter
import sys
input = sys.stdin.buffer.readline

def main():
    n = int(input())
    lis = list(map(int,input().split()))
    d = Counter(lis)
    su = 0
    for e in d:
        su += (d[e] - 1) * d[e] // 2

    for e in lis:
        if d[e] <= 1:
            print(su)
        else:
            k = d[e]
            res = su - k*(k-1)//2 + (k-1)*(k-2)//2
            print(res)

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

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

AB = range(A,B+1)

tail = len(AB)
for i in range(tail):
    if i < K or tail - K <= i:
        print(AB[i])



### FIXED CODE ###

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

AB = range(A,B+1)
tail = len(AB)
AB_L = set(AB[0:min(K,tail)])
AB_R = set(AB[max(0,tail-K):tail])
AB_SL = sorted(AB_L | AB_R)

for ab in AB_SL:
    print(ab)
### BUGGY CODE ###

#Python

N= input()
#print N
a = map(int, raw_input().split())
#print a


b=[]
for i in range(N):
	if i%2==0:
		b.append(a[i])
	elif i%2==1:
		b.insert(0,a[i])
	#print b

#print b

if N%2==1:
	b.reverse()

for j in range(N):
	print b[j],

### FIXED CODE ###

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

l=[ i for i in range(n)]
l_gusu=l[0::2]
l_kisu=l[1::2]

ans=[]
for i in reversed(list(l_gusu)):
	#print i,a[i]
	ans.append(a[i])

for i in l_kisu:
	ans.append(a[i])


ans_str=""
if n%2==0:
	for i in reversed(list(ans)):
		ans_str+=(str(i)+" ")
	print ans_str.strip()
else:
	for i in ans:
		ans_str+=(str(i)+" ")
	print ans_str.strip()
### BUGGY CODE ###

N = int(input())
S = input()
 
ans = len(S) - 1
left = 0 # リーダーより左
right = 0 # リーダーより右

for i in range(len(S)):
    if i > 0:   
        left = S[0:i].count("W")
    right = S[i + 1 :].count("E")
    ans = min(ans, left + right)
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
 
left = 0
right = S[1:].count("E")
ans = left + right

for i in range(1, N):
    if S[i - 1] == "W":
        left += 1
    if S[i] == "E":
        right -= 1 
    ans = min(ans, left + right)
print(ans)
### BUGGY CODE ###

S=[c for c in input()]
ans=S[:]
Q=int(input())
for i in range(Q):
    t=[a for a in input().split()]
    if t[0]=="1":
        ans=ans[::-1]
    else:
        if t[1]=="1":
            ans.insert(0,t[2])
        else:
            ans.append(t[2])
print("".join(ans))            
    

### FIXED CODE ###

from collections import deque
S=deque([c for c in input()])
Q=int(input())
flg=True
for i in range(Q):
    l=[a for a in input().split()]
    if l[0]=="1": 
        flg=not flg
    else:
        if l[1]=="1":
            if flg:
                S.appendleft(l[2])
            else:
                S.append(l[2])
        else:
            if flg:
                S.append(l[2])
            else:
                S.appendleft(l[2])
print("".join(S) if flg else "".join(list(reversed(S))))
### BUGGY CODE ###

S = input()
 
N = len(S)
 
cnt = 0
alr = []
for i in range(N-3):
    if i in alr:
        continue
    else:
        cnt_i = 1
        for j in range(i+3,N):
            S_int = int(S[i:(j+1)])
            if S_int % 2019 == 0:
                cnt += cnt_i
                cnt_i += 1
                alr.append(j+1)
print(cnt)

### FIXED CODE ###

S = input()
 
N = len(S)

mod = 2019
d = [0 for i in range(2019)]
d[0] = 1
t = 1
rem = 0

for i in reversed(S):
    rem += int(i) * t
    rem %= mod
    t *= 10
    t %= mod
    d[rem] += 1

print(int(sum([i * (i-1) / 2 for i in d])))
### BUGGY CODE ###

import time
start = time.time()
n = int(input())
a = [list(map(int,input().split())) for _ in range(n)]
s = [0 for i in range(n)] #それぞれ何試合目か
ans = 0
need = n*(n-1)//2
while need:
    c = [0 for i in range(n)] #今日試合をするかどうか
    ans += 1
    for first in range(n):
        if c[first] == 0 and s[first] < n-1:
            second = a[first][s[first]]-1 # firstが対戦したい相手
            second_num = s[second] # #secondの対戦番号
            if c[second] == 0 and a[second][second_num]-1 == first:
                c[first] = 1
                c[second] = 1
                s[first] += 1
                s[second] += 1
                need -= 1
    if sum(c) == 0:
        print(-1)
        exit()
    now = time.time()-start
    if now > 1.88:
        print(n*(n-1)//2)
        exit()
print(ans)

### FIXED CODE ###

import time
start = time.time()
n = int(input())
a = [list(map(int,input().split())) for _ in range(n)]
s = [0 for i in range(n)] #それぞれ何試合目か
ans = 0
need = n*(n-1)//2
while need:
    c = [0 for i in range(n)] #今日試合をするかどうか
    ans += 1
    for first in range(n):
        if c[first] == 0 and s[first] < n-1:
            second = a[first][s[first]]-1 # firstが対戦したい相手
            second_num = s[second] # #secondの対戦番号
            if c[second] == 0 and a[second][second_num]-1 == first:
                c[first] = 1
                c[second] = 1
                s[first] += 1
                s[second] += 1
                need -= 1
    if sum(c) == 0:
        print(-1)
        exit()
    now = time.time()-start
    if now > 1.8:
        print(n*(n-1)//2)
        exit()
print(ans)
### BUGGY CODE ###

#import sys
#input = sys.stdin.readline
M = 10**9+7
n = int(input())
l = list(map(int,input().split()))
o = [0]*61
z = [0]*61
for i in l:
    a = bin(i)[2:]
    j = 0
    while(j < len(a)):
        if a[j] == "1":
            o[len(a)-j-1] = o[len(a)-j-1]+1

        j = j+1

cnt = 0
b = 1
for j in range(len(o)):
    cnt = (cnt+(o[j]*(n-o[j])*b)%M)%M
    b = b*2

print(cnt)

### FIXED CODE ###

def readinput():
    n=int(input())
    l=list(map(int,input().split()))
    return n,l

def main(n,a):
    MOD=10**9+7
    hist=[0]*61
    bs=[]
    for i in range(n):
        # s=list(reversed(bin(a[i])[2:]))
        # for j in range(len(s)):
        #     if s[j]=='1':
        #         hist[j]+=1
        # bs.append(s)

        s=bin(a[i])[2:]
        for j in range(len(s)):
            if s[j]=='1':
                hist[len(s)-j-1]+=1
        # j=0
        # ai=a[i]
        # while ai>0:
        #     if ai&1==1:
        #         hist[j]+=1
        #     ai = ai >> 1
        #     j+=1


    #print(bs)
    #print(hist)
    #print(hist)
    sum=0
    # for i in range(n-1):
    #     s=bs[i]
    #     b=1
    #     for j in range(len(s)):
    #         if s[j]=='0':
    #             sum=(sum+hist[j]*b)%MOD
    #         else:
    #             sum=(sum+( n-i-hist[j] )*b)%MOD
    #             hist[j]-=1
    #         b*=2
    #     for j in range(len(s),61):
    #         sum=(sum+hist[j]*b)%MOD
    #         b*=2
    b=1
    for j in range(61):
        sum=(sum+( hist[j]*(n-hist[j])*b )%MOD )%MOD
        b*=2

    return sum

if __name__=='__main__':
    n,l=readinput()
    ans=main(n,l)
    print(ans)
### BUGGY CODE ###

from copy import deepcopy

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

all_score = sum(V)
memo = {}

def dfs(queue, hand, depth):
    # print(queue, hand, depth)
    if depth == K:
        score = all_score - sum(queue)
        memo[queue] = score
        # print('return', queue, score)
        return score
    if queue in memo and memo[queue] is not None:
        # print('memo')
        return memo[queue]

    memo[queue] = None

    max_score = all_score - sum(queue)
    if len(queue) > 0:
        # A
        A_queue = queue[1:]
        if A_queue not in memo:
            A_hand = deepcopy(hand)
            A_hand.append(queue[0])
            score = dfs(A_queue, A_hand, depth + 1)
            if score > max_score:
                max_score = score
        # B
        B_queue = queue[:-1]
        if B_queue not in memo:
            B_hand = deepcopy(hand)
            B_hand.append(queue[-1])
            score = dfs(B_queue, B_hand, depth + 1)
            if score > max_score:
                max_score = score

    for i in range(len(hand)):
        # C
        C_queue = (hand[i],) + queue
        if C_queue not in memo:
            C_hand = deepcopy(hand)
            C_hand = C_hand[:i] + C_hand[i+1:]
            score = dfs(C_queue, C_hand, depth + 1)
            if score > max_score:
                max_score = score

        # D
        D_queue = queue + (hand[i],)
        if D_queue not in memo:
            D_hand = deepcopy(hand)
            D_hand = D_hand[:i] + D_hand[i + 1:]
            score = dfs(D_queue, D_hand, depth + 1)
            if score > max_score:
                max_score = score

    memo[queue] = max_score
    # print(queue, max_score)
    return max_score

ans = dfs(V, [], 0)
print('0' if ans < 0 else ans)

### FIXED CODE ###

from copy import deepcopy

N, K = map(int, input().split())
V = tuple(map(int, input().split()))
max_score = -1000000000
for i in range(K+1):
    for j in range(K - i + 1):
        if i + j > N:
            continue
        # 左からi個取る
        hand = list(V[:i])
        # 右からj個取る
        hand.extend(V[N-j:])
        # 最大(K - i - j)個戻せる
        # print(i, j, hand)
        score = sum(hand)
        counter = 0
        for h in sorted(hand):
            counter += 1
            if K - i - j - counter < 0:
                break
            if h < 0:
                score -= h
        if max_score < score:
            max_score = score
print(max_score)
### BUGGY CODE ###

import math
n,m=[int(i) for i in input().split()]
if(abs(n-m)>1):
    print(0)
    exit()
    
def is_even(n):
    if(n%2==0):
        return True
    else:
        return False

if(is_even(n) and is_even(m)):
    print(math.factorial(n)*math.factorial(m)*2)
    exit()
elif(is_even(n) and not is_even(m)):
    print(math.factorial(n)*math.factorial(m))
    exit()
elif(not is_even(n) and is_even(m)):
    print(math.factorial(m)*math.factorial(n))
    exit()
elif(not is_even(n) and not is_even(m)):
    print(math.factorial(m)*math.factorial(n)*2)
    exit()

### FIXED CODE ###

import math
n,m=[int(i) for i in input().split()]
if(abs(n-m)>1):
    print(0)
    exit()

def is_even(n):
    if(n%2==0):
        return True
    else:
        return False
if(is_even(n) and is_even(m) or not is_even(n) and not is_even(m)):
    print(math.factorial(n)*math.factorial(m)*2%(10**9+7))
    exit()
else:
    print(math.factorial(n)*math.factorial(m)%(10**9+7))
    exit()
# if(is_even(n) and is_even(m)):
#     print(math.factorial(n)*math.factorial(m)*2)
#     exit()
# elif(is_even(n) and not is_even(m)):
#     print(math.factorial(n)*math.factorial(m))
#     exit()
# elif(not is_even(n) and is_even(m)):
#     print(math.factorial(m)*math.factorial(n))
#     exit()
# elif(not is_even(n) and not is_even(m)):
#     print(math.factorial(m)*math.factorial(n)*2)
#     exit()
### BUGGY CODE ###

a, b, x = map(int, input().split())
ans = 0
for i in range(a, b+1):
    if i%x ==0:
        ans +=1

print(ans)

### FIXED CODE ###

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

if a % x == 0:
    print(-(a//x)+(b//x)+1)
else:
    print(-(a//x)+(b//x))