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

def main():
    s = input().rstrip()
    s = s[::-1]
    s += "0"
    n = len(s)
    a = [int(c) for c in s]
    dp = [[float("inf")]*2 for _ in range(2)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(2):
            x = a[i] + j
            if x < 10:
                dp[(i+1)%2][0] = min(dp[(i+1)%2][0], dp[i%2][j] + x + 0)
            if 0 < x:
                dp[(i+1)%2][1] = min(dp[(i+1)%2][1], dp[i%2][j] + 10 - x)
        for j in range(2):
            dp[i%2][j] = float("inf")
    print(dp[n%2][0])

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    s = input().rstrip()
    s = "0" + s
    dp = [0, float("inf")]
    for c in s:
        x = int(c)
        dp = [min(dp[0] + x, dp[1] + (10-x)), min(dp[0] + x+1, dp[1] + (10-x) - 1)]
    print(dp[0])

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

N = int(input())
A = [int(input()) for i in range(N)]
A.sort()
count = 0
while A:
  a = A.count(A[0])
  if a%2 == 1:
    count += 1
  del A[:a]
print(count)

### FIXED CODE ###

import collections
N = int(input())
A = [int(input()) for i in range(N)]
C = list(collections.Counter(A).values())
counter = 0
for x in C:
  if x%2 == 1:
    counter += 1
print(counter)
### BUGGY CODE ###

Md,MN=1000000007,1000006
fac,ifac,a,res,inv=[1,1],[1,1],[0],0,[1,1]
for i in range(2,MN):
    inv.append(inv[Md%i]*(Md-Md/i)%Md)
    fac.append(fac[-1]*i%Md)
    ifac.append(ifac[-1]*inv[i]%Md)
def C(x,y):
    if(x<y):
        return 0
    return fac[x]*ifac[y]*ifac[x-y]
def D(x,y):
    return C(x-y+1,y)

n=int(input())
for i in range(1,n):
    if i*2-n>=0:
        a.append(D(n-3,n-i-1)*fac[i]*fac[n-i-1]%Md)
    else:
        a.append(0)
for i in range(n-1,0,-1):
    a[i]=(a[i]-a[i-1])%Md
    res=res+a[i]*i
res=res%Md
print(res)


### FIXED CODE ###

Md,MN=1000000007,1000006
fac,ifac,a,res,inv=[1,1],[1,1],[0],0,[1,1]
for i in range(2,MN):
    inv.append(inv[Md%i]*(Md-Md//i)%Md)
    fac.append(fac[-1]*i%Md)
    ifac.append(ifac[-1]*inv[i]%Md)
def C(x,y):
    if(x<y):
        return 0
    return fac[x]*ifac[y]*ifac[x-y]
def D(x,y):
    return C(x-y+1,y)

n=int(input())
for i in range(1,n):
    if i*2-n>=0:
        a.append(D(n-3,n-i-1)*fac[i]*fac[n-i-1]%Md)
    else:
        a.append(0)
for i in range(n-1,0,-1):
    a[i]=(a[i]-a[i-1])%Md
    res=res+a[i]*i
res=res%Md
print(res)
### BUGGY CODE ###

n, k = map(int, input().split())
h = [int(input()) for _ in range(n)]

h.sort()
ans = 10**9
for i in range(0, n-k+1):
   x = h[i:i+k]
   if (max(x) - min(x) < ans):
      ans = max(x) - min(x)

print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
height = [int(input()) for _ in range(n)]

height.sort()

diff = [height[i+k-1] - h for i, h in enumerate(height) if i+k-1 < len(height)]
print(min(diff))
### BUGGY CODE ###

from bisect import bisect

n = int(input())
a = sorted(map(int, input().split()))
b = sorted(map(int, input().split()))
c = sorted(map(int, input().split()))
cnt = 0

for i in range(n):
    bi = bisect(b, a[i])
    if bi >= n:
        continue
    for j in range(bi, n):
        cj = bisect(c, b[j])
        if cj >= n:
            continue
        cnt += n - cj
print(cnt)

### FIXED CODE ###

from bisect import bisect_left, bisect_right

n = int(input())
a = sorted(map(int, input().split()))
b = sorted(map(int, input().split()))
c = sorted(map(int, input().split()))
ba = [bisect_left(a, bi) for bi in b]
bc = [bisect_right(c, bi) for bi in b]
cnt = 0
for i in range(n):
    cnt += ba[i] * (n - bc[i])
print(cnt)
### BUGGY CODE ###

from collections import deque

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

    Df, Db = {}, {}
    for i in range(1, n + 1):
        Df[i] = set()
        Db[i] = set()

    for i in range(m):
        a, b = [int(e) for e in input().split()]
        Df.get(a).add(b)
        Df.get(b).add(a)

    for i in range(k):
        c, d = [int(e) for e in input().split()]
        Db.get(c).add(d)
        Db.get(d).add(c)

    Q = deque()
    C = {}
    ANS = {}
    for i in range(1, n + 1):
        if C.get(i):
            continue

        C[i] = True
        Cin = {}
        Cin[i] = True
        Q.appendleft(i)
        while len(Q) != 0:
            for f in Df.get(Q.pop()):
                if not Cin.get(f):
                    Q.appendleft(f)
                    C[f] = True
                    Cin[f] = True

        for k in Cin.keys():
            ANS[k] = len(Cin) - len(Df[k]) - len(Cin.keys() & Db[k] - Df[k]) - 1

    print(*[ANS[i] for i in range(1, n + 1)])

if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque

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

    Df, Db = {}, {}
    for i in range(1, n + 1):
        Df[i] = set()
        Db[i] = set()

    for i in range(m):
        a, b = [int(e) for e in input().split()]
        Df.get(a).add(b)
        Df.get(b).add(a)

    for i in range(k):
        c, d = [int(e) for e in input().split()]
        Db.get(c).add(d)
        Db.get(d).add(c)

    Q = deque()
    C = set()
    ANS = {}
    for i in range(1, n + 1):
        if i in C:
            continue

        C.add(i)
        Cin = set()
        Cin.add(i)
        Q.appendleft(i)
        while len(Q) != 0:
            for f in Df.get(Q.pop()) - Cin:
                Q.appendleft(f)
                C.add(f)
                Cin.add(f)

        for k in Cin:
            ANS[k] = len(Cin) - len(Df[k]) - len(Cin & Db[k] - Df[k]) - 1

    print(*[ANS[i] for i in range(1, n + 1)])

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

n = int(input())
l_s = list(map(int,input().split()))
l_s.append(0)
l_s.sort()
ans = 0
#一番長い辺を選ぶ
#print(l_s)
for i in range(3,n+1):
    for j in range(2,i):
        if l_s[i] < l_s[j] + l_s[j-1]:
            
            OK = j-1
            NG = 0
            while (OK - NG) > 1:
                mid = (OK+NG)//2
                if l_s[i] < l_s[j] + l_s[mid]:
                    OK = mid
                else:
                    NG = mid
            ans = ans + j - OK 
print(ans)



### FIXED CODE ###

n = int(input())
l_s = list(map(int,input().split()))
l_s.append(0)
l_s.sort()
ans = 0
#一番長い辺を選ぶ
#print(l_s)
for j in range(2,n):
    for i in range(j+1,n+1):
        if l_s[i] < l_s[j] + l_s[j-1]:
            
            OK = j-1
            NG = 0
            while (OK - NG) > 1:
                mid = (OK+NG)//2
                if l_s[i] < l_s[j] + l_s[mid]:
                    OK = mid
                else:
                    NG = mid
            ans = ans + j - OK 
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
def dfs(v,c):
  for i,w in enumerate(e[v]):
    e[w].discard(v)
    c*=dfs(w,k-i+~(v>0))
  return c%(10**9+7)
n,k,*t=map(int,open(0).read().split())
e=eval('set(),'*n)
for a,b in zip(t[::2],t[1::2]):
  e[a-1].add(b-1)
  e[b-1].add(a-1)
print(dfs(0,k))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def dfs(v,c):
  for i,w in enumerate(e[v]):
    e[w].discard(v)
    c=c*dfs(w,k-i+~(v>0))%(10**9+7)
  return c
n,k,*t=map(int,open(0).read().split())
e=eval('set(),'*n)
for a,b in zip(t[::2],t[1::2]):
  e[a-1].add(b-1)
  e[b-1].add(a-1)
print(dfs(0,k))
### BUGGY CODE ###

a = int(input())
sum=0
for i in range(1,a):
    sum+=i
print(sum)


### FIXED CODE ###

a = int(input())
print(a*(a-1)//2)
### BUGGY CODE ###

import math
from functools import reduce
import itertools

def gcd(*numbers):
	return reduce(math.gcd, *numbers)

limit_num = int(input())
result_list = []
for num in itertools.product(range(1, limit_num + 1), repeat=3):
	result_list.append(gcd(num))

print(sum(result_list))


### FIXED CODE ###

import math
from functools import reduce
import itertools

def gcd(*numbers):
	return reduce(math.gcd, *numbers)

limit_num = int(input())
result_list = []
for num in itertools.product(range(1, limit_num + 1), repeat=3):
	result_list.append(gcd(num))

print(sum(result_list))
### BUGGY CODE ###

from collections import defaultdict
import math




if __name__ == '__main__' :
    n = int(input())
    R = [int(input()) for i in range(n)]
    tmp = [max(R[i+1::])  - R[i] for i in range(n-1)]
    print(max(tmp))



### FIXED CODE ###

from collections import defaultdict
import math




if __name__ == '__main__' :
    n = int(input())
    R = [int(input()) for i in range(n)]
    maxv = R[1]-R[0]
    minv = min(R[0],R[1])
    for j in range(2,n):
        maxv = max(maxv,R[j]-minv)
        minv = min(minv,R[j])
    print(maxv)
### BUGGY CODE ###

n,k=map(int,input().split())
a=[int(x) for x in input().split()]
c=0
f=[99999999999]*(n)
f[0]=0
for i in range(n):
    for j in range(i+1,i+k+1):
        if j<n:
            f[j]=min(f[j],f[i]+abs(a[i]-a[j]))
print(f[n-1])

### FIXED CODE ###

n,k=map(int,input().split())
a=[int(x) for x in input().split()]
c=0
f=[99999999999]*(n)
f[0]=0
for i in range(n):
    for j in range(i+1,i+k+1):
        if j<n:
            f[j]=min(f[j],f[i]+abs(a[i]-a[j]))
print(f[n-1])
### BUGGY CODE ###

import numpy as np
N = int(input())
A = np.array([int(i) for i in input().split()])
A.sort()
for i in range(A[1], -1, -1):
    if len(A[np.where(A % i == 0)]) >= len(A)-1:
        res = i
        break

print(res)


### FIXED CODE ###

N = int(input())
A  = [int(i) for i in input().split()]

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

res = [0] * N
l = [0] * (N + 1)
r = [0] * (N + 1)

for i in range(N):
    l[i+1] = gcd(l[i], A[i])

for i in range(N, 0, -1):
    r[i-1] = gcd(r[i], A[i-1])

for i in range(N):
    res[i] = gcd(l[i], r[i+1])

print(max(res))
### BUGGY CODE ###

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

if N == K:
    print(0)

elif N<K and N<=K-N:
    print(N)

elif N<K and N>K-N:
    print(K-N)

elif N>K:

    for i in range(18):
        k = K*(10**(17-i))
        while N>=k:
            k=k+K*(10**(17-i))
        k = k-K*(10**(17-i))
    k = k+K
    if k-N<N-(k-K):
        print(k-N)
    else:
        print(N-(k-K))


### FIXED CODE ###

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

if N%K == 0:
    print(0)

elif N<K and N<=K-N:
    print(N)

elif N<K and N>K-N:
    print(K-N)

elif N>K:
    if K-(N%K)>N%K:
        print(N%K)
    else:
        print(K-(N%K))
### BUGGY CODE ###

import sys
from queue import Queue

input = sys.stdin.readline
h, w = map(int, input().split())
matrix = dict()
queue = Queue()
for i in range(h):
    cells = list(input().rstrip("\n"))
    for j, cell in enumerate(cells):
        if cell == "#":
            matrix[str(i) + "_" + str(j)] = 0
            queue.put((i, j))
        else:
            matrix[str(i) + "_" + str(j)] = -1
while not queue.empty():
    i, j = queue.get(block=False)
    for i_diff, j_diff in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
        i_current = i + i_diff
        j_current = j + j_diff
        if (
            0 <= i_current < h
            and 0 <= j_current < w
            and matrix[str(i_current) + "_" + str(j_current)] == -1
        ):
            matrix[str(i_current) + "_" + str(j_current)] = (
                matrix[str(i) + "_" + str(j)] + 1
            )
            queue.put((i_current, j_current))

max_step = max(matrix.values())
print(max_step)

### FIXED CODE ###

import sys
from collections import deque

input = sys.stdin.readline
h, w = map(int, input().rstrip("\n").split())
matrix = [[-1 for j in range(w)] for i in range(h)]
queue = deque()
for i in range(h):
    cells = list(input().rstrip("\n"))
    for j, cell in enumerate(cells):
        if cell == "#":
            matrix[i][j] = 0
            queue.append((i, j))
while queue:
    i, j = queue.popleft()
    for i_diff, j_diff in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
        i_current = i + i_diff
        j_current = j + j_diff
        if (
            0 <= i_current < h
            and 0 <= j_current < w
            and matrix[i_current][j_current] == -1
        ):
            matrix[i_current][j_current] = matrix[i][j] + 1
            queue.append((i_current, j_current))

max_step = max([max(row) for row in matrix])
print(max_step)
### BUGGY CODE ###

n,m=[int(x) for x in input().rstrip().split()]
A=[int(x) for x in input().rstrip().split()]
now=[]
for i in range(m):
  b,c=[int(x) for x in input().rstrip().split()]
  A.extend([c]*b)
A.sort(reverse=True)
print(sum(A[:n]))



### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
from bisect import bisect_left
 
 
n, m = map(int, input().split())
a = list( map(int, input().split()))
a.sort()
 
bc = [tuple(map(int,input().split())) for i in range(m)]
bc = sorted(bc, reverse=True, key=lambda x: x[1])
 
i = 0
d = []
for b, c in bc:
    d.extend([c]*b)
    if len(d) >= n:
        break
 
a=a+d
a.sort(reverse=True)
print(sum(a[:n]))

#l.sort(reverse=True)
#A=A+l[:N]
#A.sort(reverse=True)
### BUGGY CODE ###

n=int(input())
S=input()

ans=0
for x in range(1000):
  x=str(x).zfill(3)
  idx=0
  for j in range(n):
    if S[j]==x[idx]:
      idx+=1
    if idx>=3:
      ans+=1
      break
print(ans)

### FIXED CODE ###

n=int(input())
S=input()

ans=0
for i in range(10):
  for j in range(10):
    for k in range(10):
      idxi=S.find(str(i))
      if idxi==-1:
        continue
      idxj=S.find(str(j),idxi+1)
      if idxj==-1:
        continue
      idxk=S.find(str(k),idxj+1)
      if idxk==-1:
        continue
      ans+=1
print(ans)
### BUGGY CODE ###

n = int(input())

s = []

t =  set()

for i in range(n):
    k = input()
    s.append(k)
    t.add(k)

t = list(t)

a = []

for i in t:
    a.append([s.count(i),i])

a.sort(reverse = True)

maxa = a[0][0]

ans = []

for i in a:
    if i[0] == maxa:
        ans.append(i[1])
    else:
        break

ans.sort()

for i in ans:
    print(i)

### FIXED CODE ###


import collections as col

n = int(input())

s = []

for i in range(n):
    s.append(input())
    
x = col.Counter(s)

m = 0

x = x.most_common()

ans = []

for i in x:
    if i[1]<m:
        break
    else:
        ans.append(i[0])
        m = i[1]
        
ans.sort()

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

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

res = 1
for i in range(n):
  res = res * nums[i]
print(res if res <= 10**18 else -1)

### FIXED CODE ###

n = int(input())
nums = sorted(list(map(int,input().split())), reverse=True)

res = 1

if 0 in nums:
  print(0)
  exit()
  
for i in range(n):
  res = res * nums[i]
  if res <= 10**18 :
    continue
  else:
    res = -1
    break
print(res)
### BUGGY CODE ###

n, q = map(int, raw_input().split())
s = [0 for i in range(n)]
for i in range(q):
	a, v = map(int, raw_input().split())
	s[a-1] += v
	print s.index(max(s))+1, max(s)

### FIXED CODE ###

n, q = map(int, raw_input().split())
s = [0]*n
mx,mxa = 0, 0
for i in range(q):
	a,v = map(int, raw_input().split())
	s[a-1] += v
	if v > 0:
		if s[a-1] > mx:
			mx = s[a-1]
			mxa = a-1
		elif s[a-1] == mx:
			if a-1 < mxa:
				mxa = a-1
	elif v < 0:
		if a-1 == mxa:
			mx = max(s)
			mxa = s.index(mx)
	print mxa+1,mx
### BUGGY CODE ###

N, K = map(int, input().split())
*h, = map(int, input().split())
dp = [float("inf") for _ in range(N)]
dp[0] = 0
for i in range(N - 1):
	for j in range(1, min(K + 1, N - i)):
		dp[i + j] = min(dp[i + j], dp[i] + abs(h[i + j] - h[i]))
print(dp[N - 1])


### FIXED CODE ###

N, K = map(int, input().split())
*h, = map(int, input().split())
dp = [float("inf") for _ in range(N)]
dp[0] = 0
for i in range(N - 1):
	for j in range(1, min(K + 1, N - i)):
		dp[i + j] = min(dp[i + j], dp[i] + abs(h[i + j] - h[i]))
print(dp[N - 1])
### BUGGY CODE ###

import sys;input=sys.stdin.readline
N, Q = map(int, input().split())
X = []
for _ in range(N):
    s, t, x = map(int, input().split())
    X.append((2*s-2*x-1, 0, x))
    X.append((2*t-2*x-1, 1, x))

inf = 10**18
X.append((-inf, 0, inf))
X.append((inf, 1, inf))

X.sort(key=lambda x: x[0])

from heapq import *
from collections import defaultdict
#print(X[1:-1])
j = 0
ll = []
vs = set()
d = defaultdict(int)
for _ in range(Q):
    q = int(input())
    while 1:
        u, f, x = X[j]
        if u > 2*q:
            break
        if f:
            d[x] += 1
        else:
            heappush(ll, x)
        j += 1
    while 1:
        x = heappop(ll)
        if d[x] > 0:
            d[x] -= 1
            continue
        heappush(ll, x)
        if x == inf:
            print(-1)
        else:
            print(x)
        break



### FIXED CODE ###

import sys
input = sys.stdin.readline

n,Q=map(int,input().split())
b_num = 2**(n-1).bit_length()
mx = 10**9
segl=[mx]*2*b_num 

def update( k, x):
    k += b_num-1
    segl[k] = x
    while k+1:
        k = (k-1)//2
        segl[k] = min(segl[k*2+1],segl[k*2+2])
    
if __name__ == '__main__':
    xs = []
    for i in range(n):
        s,t,x=map(int,input().split())
        xs += [(s-x-0.4,True,x,i), (t-x-0.5,False,x,i)]
    for _ in range(Q):
        xs.append((int(input()),2))
    xs.sort(key=lambda x:x[0])
    for x in xs:
        if x[1]==2:
            print(segl[0] if segl[0]!= mx else -1)
            continue
        update(x[3], x[2] if x[1] else mx)
### BUGGY CODE ###

n=int(input())
a=[int(x) for x in input().rstrip().split()]
cnt=[0 for i in range(n)]
nc2=[0 for i in range(n)]
for i in a:
  cnt[i-1]+=1

for i in a:
  nc2[i-1]=((cnt[i-1])*(cnt[i-1]-1))//2
for i in a:
  print(sum(nc2)-nc2[i-1]+((cnt[i-1]-1)*(cnt[i-1]-2))//2)

### FIXED CODE ###

n=int(input())
a=[int(x) for x in input().rstrip().split()]
cnt=[0 for i in range(n)]
for i in a:
  cnt[i-1]+=1

nc2=[]
for i in cnt:
  nc2.append(((i)*(i-1))//2)

All=sum(nc2)
for i in range(n):
  now=cnt[a[i]-1]-1
  print(All-nc2[a[i]-1]+((now)*(now-1))//2)
### BUGGY CODE ###

N=int(input())
A_list=sorted(list(map(int, input().split())), reverse=True)
ans=1

if 0 in A_list:
  print(0)
  exit()
else:
  for a in A_list:
    ans*=a
  if ans>1e+18:
    ans=-1
    print(-1)
    exit()
  print(ans)







### FIXED CODE ###

N=int(input())
A_list=sorted(list(map(int, input().split())), reverse=True)
ans=1

for a in A_list:
  ans*=a
  if ans>1e+18:
    ans=-1
    break
if 0 in A_list:
  ans=0
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = [int(i) for i in input().split()]
while M > 0:
    A[A.index(max(A))] //= 2
    M -= 1
print(sum(A))

### FIXED CODE ###

from heapq import heapify, heappush, heappop
N, M = map(int, input().split())
A = [-int(i) for i in input().split()]
heapify(A)
while M > 0:
    heappush(A, heappop(A) / 2)
    M -= 1
print(-sum(int(i) for i in A))
### BUGGY CODE ###

import numpy as np
import copy

N = int(raw_input().replace("\n", ""))

a_list = []

for i in xrange(N):
    a = int(raw_input().replace("\n", ""))
    a_list.append(a)

input_list = a_list

a_array = np.asarray(a_list)
sum_diffs = []
for start_elm in input_list:
    a_list = copy.deepcopy(input_list)
    target_elm = start_elm
    
    sum_diff = 0
    while len(a_list) >= 1:
        a_list.remove(target_elm)
        if len(a_list) >= 1:
            a_array = np.abs(np.asarray(a_list) - target_elm)
            target_elm_index = np.argmax(a_array)
            target_elm = a_list[target_elm_index]
            sum_diff += a_array[target_elm_index]
        else:
            #sum_diff += np.abs(a_list[0] - target_elm)
            break
    
    sum_diffs.append(sum_diff)

print max(sum_diffs)

### FIXED CODE ###

import numpy as np
import copy

N = int(raw_input().replace("\n", ""))

a_array = np.asarray(sorted([int(raw_input().replace("\n", "")) for i in xrange(N)]))

len_array = len(a_array)

coffs = np.ones(len(a_array), dtype=bool) * 2

if len_array % 2 == 0:
    coffs = [-2] * ((len_array - 1) / 2) + [-1] + [1] + [2] * ((len_array -1) / 2)
    out = np.dot(a_array, coffs)
else:
    coffs1 = [-2] * ((len_array-3) / 2) + [-1] * 2 + [2] * ((len_array-1) / 2)
    coffs2 = [-2] * ((len_array-1) / 2) + [1] * 2 + [2] * ((len_array-3) / 2)
    out1 = np.dot(a_array, coffs1)
    out2 = np.dot(a_array, coffs2)
    out = max(out1, out2)

print out
### BUGGY CODE ###

S = str(input())
N = len(S)
ans1 = [0] * 2019
ans2 = 0

T = [0] *  (N + 1)
T[N] = 0
ans1[0] += 1

for i in range(N - 1, -1, -1):
  #print(i)
  T[i] = (T[i + 1] + 10 ** (N - i - 1) * int(S[i])) % 2019
  ans1[T[i]] += 1

for i in range(2019):
  x = ans1[i]
  ans2 += x * (x - 1) / 2
  
#print(ans1[0])
#print(T)
print(int(ans2))  



### FIXED CODE ###

S = str(input())
N = len(S)
ans1 = [0] * 2019
ans2 = 0

T = [0] *  (N + 1)
T[N] = 0
ans1[0] += 1

P = 1
for i in range(N - 1, -1, -1):
  #print(i)
  T[i] = (T[i + 1] + P * int(S[i])) % 2019
  ans1[T[i]] += 1
  P = 10 * P % 2019

for i in range(2019):
  x = ans1[i]
  ans2 += x * (x - 1) / 2
  
#print(ans1[0])
#print(T)
print(int(ans2))
### BUGGY CODE ###

N=int(input())
A=[]
for i in range(N):
    A.append(int(input()))

A=sorted(A)
s=0
cnt=0
while 1:
    if s>=N:
    	break
    else:
        for i in range(s,N-1):	
            if A[i]==A[i+1]:
                cnt+=1
                s=i+2
                break
print(N-2*cnt)

### FIXED CODE ###

N=int(input())
A=set()
for i in range(N):
    x=int(input())
    if x in A:
        A.remove(x)
    else:
        A.add(x)

print(len(A))
### BUGGY CODE ###

n, w = map(int, input().split())
highests = []
for i in range(n+1):
    highests.append([0]*(w+1))
for i in range(1,n+1):
    weight, value = map(int, input().split())
    for j in range(w+1):
        if j < weight:
            highests[i][j] = highests[i-1][j]
        else:
            highests[i][j] = max([highests[i-1][j-weight] + value, highests[i-1][j]])
print(highests[n][w])

### FIXED CODE ###

n,w = map(int, input().split())
high = [0] * (w + 1)
for i in range(n):
    weight, value = map(int, input().split())
    if weight <= w:
        renewal = high[:weight]
        renewal += [max([j+value, k]) for j,k in zip(high[:w-weight+1], high[weight:])]
        high = renewal
print(high[w])
### BUGGY CODE ###

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import bisect
mod=998244353
n=int(input())
d=[]
N=1<<(n.bit_length())
t=[-1 for i in range(2*N-1)]

def ud(i,x):
  i+=N-1
  t[i]=x
  while i:
    i=(i-1)//2
    if t[i*2+1]>t[i*2+2]:t[i]=t[i*2+1]
    else:t[i]=t[i*2+2]
     

def qr(a,b):
    a+=N-1
    b+=N-1
    L = -1
    R = -1
    while a < b:
      if a&1==0:
         if L<t[a]:L = t[a]
      if b&1==0:
         b-=1
         if R<t[b]:R = t[b]
      
      a>>=1
      b>>=1
      
         
    return max(L, R)
 
for i in range(n):
  d.append([int(i) for i in input().split()])
d.sort()
dx=[]
dd=[]
for i,j in d:
  dx.append(i)
  dd.append(j)
for i in range(n)[::-1]:
 tx=dx[i]+dd[i]
 j=bisect.bisect_left(dx,tx)
 tt=qr(i,j)
 if j-1>tt:ud(i,j-1)
 else:ud(i,tt)
dp=[0 for i in range(n+1)]
dp[-1]=1
for i in range(n)[::-1]:
  dp[i]+=dp[i+1]
  dp[i]%=mod
  dp[i]+=dp[t[i+N-1]+1]
  dp[i]%=mod
print(dp[0])

### FIXED CODE ###

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import bisect
mod=998244353
n=int(input())
d=[]
N=1<<(n.bit_length())
t=[-1 for i in range(2*N-1)]

def ud(i,x):
  i+=N-1
  t[i]=x
  while i:
    i=(i-1)>>1
    if t[i*2+1]>t[i*2+2]:t[i]=t[i*2+1]
    else:t[i]=t[i*2+2]
     

def qr(a,b):
    a+=N-1
    b+=N-1
    L = -1
    R = -1
    while a < b:
      if a&1==0:
         if L<t[a]:L = t[a]
      if b&1==0:
         b-=1
         if R<t[b]:R = t[b]
      
      a>>=1
      b>>=1
      
         
    return max(L, R)
 
for i in range(n):
  d.append([int(i) for i in input().split()])
d.sort()
dx=[]
dd=[]
for i,j in d:
  dx.append(i)
  dd.append(j)
for i in range(n)[::-1]:
 tx=dx[i]+dd[i]
 j=bisect.bisect_left(dx,tx)
 tt=qr(i,j)
 if j-1>tt:ud(i,j-1)
 else:ud(i,tt)
dp=[0 for i in range(n+1)]
dp[-1]=1
for i in range(n)[::-1]:
  dp[i]+=dp[i+1]
  dp[i]%=mod
  dp[i]+=dp[t[i+N-1]+1]
  dp[i]%=mod
print(dp[0])