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

from collections import deque

H,W = list(map(int,input().split()))
Ch,Cw = list(map(int,input().split()))
Dh,Dw = list(map(int,input().split()))

maze = [["#"]*(W+4)]
maze.append(["#"]*(W+4))
for i in range(H):
    row = ["#","#"]
    row.extend(list(input()))
    row.append("#")
    row.append("#")
    maze.append(row)
maze.append(["#"]*(W+4))
maze.append(["#"]*(W+4))
warp = [[114514]*(W+4) for i in range(H+4)]

queue = deque()
queue.append((Ch+1,Cw+1))
warp[Ch+1][Cw+1] = 0
move_one = set(((1,0),(0,1),(-1,0),(0,-1)))
while queue:
    y,x = queue.popleft()
    for i in range(-2,3):
        for j in range(-2,3):
            if i == 0 and j == 0:
                maze[ny][nx] = "#"
                continue
            ny,nx = y+i,x+j
            if maze[ny][nx] == "#":
                continue
            if (i,j) in move_one:
                warp[ny][nx] = warp[y][x]
                queue.appendleft((ny,nx))
                maze[ny][nx] = "#"
            else:
                if warp[ny][nx] == 114514:
                    warp[ny][nx] = warp[y][x]+1
                    queue.append((ny,nx))

if warp[Dh+1][Dw+1] == 114514:
    print(-1)
else:
    print(warp[Dh+1][Dw+1])


### FIXED CODE ###

from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] == 10**6:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,k = map(int, input().split())
    xy = [list(map(int, input().split())) for _ in range(n)]
    x = sorted(xy, key=lambda a: a[0])
    y = sorted(xy, key=lambda a: a[1])

    res = 10**20
    for l in range(n):
        for r in range(l+1, n):
            for b in range(n):
                for t in range(b+1, n):
                    cnt = 0
                    for vx, vy in xy:
                        if x[l][0] <= vx <= x[r][0] and y[b][1] <= vy <= y[t][1]:
                            cnt += 1
                        if cnt >= k:
                            res = min(res, (x[r][0]-x[l][0])*(y[t][1]-y[b][1]))
                            break
    print(res)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,k = map(int, input().split())
    xy = [list(map(int, input().split())) for _ in range(n)]
    x = sorted(xy, key=lambda a: a[0])
    y = sorted(xy, key=lambda a: a[1])

    res = 10**20
    for l in range(n):
        for r in range(l+1, n):
            for b in range(n):
                for t in range(b+1, n):
                    cnt = 0
                    for vx, vy in x[l:r+1]:
                        if y[b][1] <= vy <= y[t][1]:
                            cnt += 1
                        if cnt >= k:
                            res = min(res, (x[r][0]-x[l][0])*(y[t][1]-y[b][1]))
                            break
    print(res)

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

n = int(input())
A = (map(int,list(input().split())))
tmp = 1
for i in A:
    tmp = tmp * i
    if tmp == 0:
        print(tmp)
        quit()

if tmp > 10**18:
        tmp=-1
        print(tmp)
        quit()
    
print(tmp)

### FIXED CODE ###

n = int(input())
A = (map(int,list(input().split())))
tmp = 1
for i in A:
    tmp = tmp * i
    if tmp == 0:
        print(tmp)
        quit()
    if tmp > 10**18:
        if 0 in A:
            print(0)
            quit()
        tmp=-1
        print(tmp)
        quit()
    
print(tmp)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  x, y, a, b, c = map(int, input().split())
  la = list(map(int, input().split()))
  la.sort(reverse=True)
  lb = list(map(int, input().split()))
  lb.sort(reverse=True)
  lc = list(map(int, input().split()))
  lc.sort(reverse=True)
  ca, cb, cc = 0, 0, 0,
  
  s = 0
  while True:
    if sum([ca, cb, cc]) == x+y:
      break
      
    a = la[0] if len(la) > 0 and ca < x else -1
    b = lb[0] if len(lb) > 0 and cb < y else -1
    c = lc[0] if len(lc) > 0            else -1
            
    if a >= b and a >= c:
      s += a
      del la[0]
      ca += 1
      continue
      
    if b >= a and b >= c:
      s += b
      del lb[0]
      cb += 1
      continue
      
    if c >= b and c >= a:
      s += c
      del lc[0]
      cc += 1
  print(s)

if __name__=='__main__':
  main()



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-


def main():
  x, y, na, nb, nc = map(int, input().split())
  la = list(map(int, input().split()))
  la.sort(reverse=True)
  lb = list(map(int, input().split()))
  lb.sort(reverse=True)
  lc = list(map(int, input().split()))
  lc.sort(reverse=True)
  ca, cb, cc = 0, 0, 0
  
  lx = la[:x] + lb[:y] + lc
  lx.sort(reverse=True)
  print(sum(lx[:x+y]))

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

import sys
import collections
from collections import Counter
# from collections import deque
# from collections import defaultdict
import itertools
# from itertools import accumulate
# from itertools import permutations
# from itertools import combinations
# from itertools import takewhile
from itertools import compress
# import functools
# from functools import reduce
import math
# from math import gcd
# from math import inf
# from math import ceil
# from math import floor
# from math import log10
# from math import log2
# from math import log
from math import factorial

# import re

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

S = set()
for i in range(N):
    for j in range(i, N):
        b = A[i:j + 1]
        S.add(sum(b))

S = sorted(list(S))

ans = 0
for i in range(40, -1, -1):
    A = [s & (1 << i) for s in S]
    newS = list(compress(S, A))
    if len(newS) >= K:
        ans += (1 << i)
        S = newS

print(ans)


### FIXED CODE ###

import sys

N,K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

C = []

for i in range(0,N-1):
    for j in range(i, N):
        if j==i:
            C.append(A[i])
        else:
            C.append(C[-1] + A[j])

D = C
ans = 0
for i in range(40,-1,-1):
    yes = []
    no = []
    for l in D:
        if l & (1 << i):
            yes.append(l)
        else:
            no.append(l)

    if len(yes) >= K:
        ans += 1 << i
        D = yes

print(ans)

sys.exit(0)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect,copy
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**7)
inf = float('inf')
mod = 10**9+7
ans = inf ;count = 0 ;pro = 1

h,w=map(int,input().split())
A=[list(map(int,input().split())) for i in range(h)]
B=[list(map(int,input().split())) for i in range(h)]
a=[set() for j in range(w)]
dp=[copy.deepcopy(a) for i in range(h)]
# for di in dp:
#     print(*dp)
# dp[0][0]=set()
dp[0][0].add(abs(A[0][0]-B[0][0]))
# print(dp)
# for di in dp:
#     print(*dp)
for i in range(h):
    for j in range(w):
        # dp[i][j]=set()
        d=abs(A[i][j]-B[i][j])
        if i-1>=0:
            for si in dp[i-1][j]:
                dp[i][j].add(si+d)
                dp[i][j].add(abs(si-d))
        # print(dp[i][j])
        if j-1>=0:
            for si in dp[i][j-1]:
                dp[i][j].add(si+d)
                dp[i][j].add(abs(si-d))
        # print(dp[i][j])
ans=min(dp[h-1][w-1])
print(ans)
# for di in dp:
#     print(di)



### FIXED CODE ###

#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect,copy
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**7)
inf = float('inf')
mod = 10**9+7
ans = inf ;count = 0 ;pro = 1

h,w=map(int,input().split())
A=[tuple(map(int,input().split())) for i in range(h)]
B=[tuple(map(int,input().split())) for i in range(h)]
# a=[set() for j in range(w)]
K=160*80
dp = [[0]*w for i in range(h)]
dp[0][0]=1<<K
for i in range(h):
    for j in range(w):
        d=abs(A[i][j]-B[i][j])
        if i-1>=0:
            dp[i][j] |= dp[i-1][j]
        if j-1>=0:
            dp[i][j] |= dp[i][j-1]
        dp[i][j] = (dp[i][j]<<d) | (dp[i][j]>>d)


ans = K
for i in range(2*K):
    if dp[h-1][w-1]  & (1 << i)>0:
        ans = min(ans,abs(K-i))
print(ans)
# for di in dp:
#     print(di)
### BUGGY CODE ###

import heapq

h = []
N, M = [int(i) for i in input().split()]
count = dict()
for i in input().split():
    if not count.get(i):
        count[i] = 0
    count[i] += 1
for k, v in count.items():
    heapq.heappush(h, (int(k), v))

for _ in range(M):
    B, C = [int(i) for i in input().split()]
    while B > 0:
        if h[0][0] >= C:
            break
        m = heapq.heappop(h)
        if m[1] > B:
            heapq.heappush(h, (C, B))
            heapq.heappush(h, (m[0], m[1] - B))
        else:
            heapq.heappush(h, (C, m[1]))
        B -= m[1]
print(sum([i[0] * i[1] for i in h]))



### FIXED CODE ###

import heapq

h = []
h2 = []
N, M = [int(i) for i in input().split()]
count = dict()
count2 = dict()
for i in input().split():
    if not count.get(i):
        count[i] = 0
    count[i] += 1
for k, v in count.items():
    heapq.heappush(h, (int(k), v))

for _ in range(M):
    B, C = [int(i) for i in input().split()]
    if not count2.get(C):
        count2[C] = 0
    count2[C] += B
for k, v in count2.items():
    heapq.heappush(h2, (-k, v))
while len(h2) > 0:
    C, B = heapq.heappop(h2)
    C = -C
    while B > 0:
        if h[0][0] >= C:
            break
        m = h[0][0]
        mc = h[0][1]
        if mc > B:
            heapq.heappush(h, (C, B))
            h[0] = (m, mc - B)
        else:
            heapq.heappop(h)
            heapq.heappush(h, (C, mc))
        B -= mc
print(sum([i[0] * i[1] for i in h]))
### BUGGY CODE ###

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

from itertools import product
import numpy as np
ans = [0] * (2**(h-1))
ans_index = 0

for horizontal_condition in product((True,False),repeat=h-1):
    count = np.zeros(h)
    divide = sum(horizontal_condition)
    trans_matrix = np.zeros((h,h))
    trans_matrix[0,0] = 1
    down = 0
    right = 0
    
    for i in horizontal_condition:
        if i:
            down += 1
        right += 1
        trans_matrix[down,right] = 1
        
    for vertical_divide in range(w):
        tmparr = np.array([int(i[vertical_divide]) for i in arr])
        addarr = np.dot(trans_matrix,tmparr)
        if max(count+addarr) > k:
            count = addarr
            divide += 1
        else:
            count += addarr
            
    ans[ans_index] = divide
    ans_index += 1
    
print(min(ans))

### FIXED CODE ###

h,w,k = list(map(int,input().split()))
arr = [[int(i) for i in input()] for _ in range(h)]

from itertools import product
ans = 2000

for idx,cond in enumerate(product((True,False),repeat=h-1)):
    div = sum(cond)
    spl = [arr[0][:]]
    for i in range(h-1):
        if cond[i]:
            spl.append(arr[i+1][:])
        else:
            spl[-1] = [spl[-1][j] + arr[i+1][j] for j in range(w)]
    num = len(spl)
    cnt = [0]*num
    
    for v in range(w):
        tmp = [spl[i][v] for i in range(num)]
        if max(tmp) > k:
            break
        if max([cnt[i] + tmp[i] for i in range(num)]) > k:
            div += 1
            cnt = tmp[:]
        else:
            cnt  = [cnt[i] + tmp[i] for i in range(num)]
    else:    
        ans = min(ans,div)
            
print(ans)
### BUGGY CODE ###

import math
n=int(input())
klist=[]
MOD=10**9+7
ans=1
n=math.factorial(n)
for i in range(2,n+1):
    kaisu=0
    while n%i==0:
        n=n//i
        kaisu+=1
    if kaisu!=0:
        klist.append(kaisu%MOD)
for i in range(len(klist)):
    ans*=((klist[i]+1)%MOD)
ans=ans%MOD
print(ans)

### FIXED CODE ###

n=int(input())
klist=[]
MOD=10**9+7
ans=1
kaijo=list(range(n+1))
for i in range(2,n+1):
    kaisu=0
    for j in range(1,n+1):
        while kaijo[j]%i==0:
            kaijo[j]=kaijo[j]//i
            kaisu+=1
    if kaisu!=0:
        klist.append(kaisu%MOD)
for i in range(len(klist)):
    ans*=((klist[i]+1)%MOD)
ans=ans%MOD
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

INF = 10 ** 10

n = int(input())
# 貰うDPだと0へのアクセスが、配るDPだとn+1へのアクセスが必要になる
h = [INF] + list(map(int, input().split())) + [INF]
dp = [INF] + [INF] * n + [INF]
dp[1] = 0

def chmin(dp_table, index, value):
    if dp_table[index] > value:
        dp_table[index] = value

# 貰うDP(dp[i-1], dp[i-2]が計算済み)
#for i in range(2, n+1):
#    chmin(dp, i, dp[i-1] + abs(h[i] - h[i-1]))
#    chmin(dp, i, dp[i-2] + abs(h[i] - h[i-2]))

# 配るDB(dp[i]が計算済み)
#for i in range(1, (n-1)+1):
#    chmin(dp, i+1, dp[i] + abs(h[i] - h[i+1]))
#    chmin(dp, i+2, dp[i] + abs(h[i] - h[i+2]))
#
#print(dp[n])

# 再帰(DFS) (メモ化なし)
def dfs(i):
    if i == 0:
        return INF
    if i == 1:
        return 0

    ans = INF
    prev_cost = dfs(i-1)
    if ans > prev_cost + abs(h[i] - h[i-1]):
        ans = prev_cost + abs(h[i] - h[i-1])
    prev_cost = dfs(i-2)
    if ans > prev_cost + abs(h[i] - h[i-2]):
        ans = prev_cost + abs(h[i] - h[i-2])

    return ans

print(dfs(n))


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

INF = 10 ** 10

n = int(input())
h = [0] + list(map(int, input().split()))
dp = [INF] + [INF] * n
dp[1] = 0

def chmin(dp_table, index, value):
    if dp_table[index] > value:
        dp_table[index] = value

for i in range(2, n+1):
    chmin(dp, i, dp[i-1] + abs(h[i] - h[i-1]))
    chmin(dp, i, dp[i-2] + abs(h[i] - h[i-2]))

print(dp[n])
### BUGGY CODE ###

n = int(input())
lis = list(map(int,input().split()))
lis2 = [True]*n
lis.sort()
m = max(lis)
ans = 0
for i in range(n):
    if lis2[i]:
        if i < n-1:
            # print(i)
            if lis[i] != lis[i+1]:
                ans += 1
        else:
            ans += 1
        for j in range(i+1,n):
            if lis2[j]:
                if lis[j]%lis[i] == 0:
                    lis2[j] = False

print(ans)

### FIXED CODE ###

# MAX = int(1e6)+2


n = int(input())
lis = list(map(int,input().split()))
lis.sort()
MAX = lis[-1]
lis2 = [0]*(MAX+1)
# lis.sort()
# m = max(lis)
ans = 0

for num in lis:
    for i in range(num, MAX+1, num):
            lis2[i] += 1

for j in set(lis):
    if lis2[j] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
f = [[a, -1] for a in A]
lim = 1<<N
for i in range(N):
    bit = 1<<i
    j = 0
    while j < lim:
        j |= bit
        a, b = f[j]
        c, d = f[j^bit]
        if a < c:
            f[j][0] = c
            f[j][1] = d if d>a else a
        elif b < c:
            f[j][1] = c
        j += 1
ans = sum(f[1])
Ans = [ans]
for a, b in f[2:]:
    ans = max(ans, a+b)
    Ans.append(ans)
print("\n".join(map(str, Ans)))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
f = [[a] for a in A]
for i in range(N):
    for j in range(1<<N):
        if j & 1<<i:
            f[j] = sorted(f[j]+f[j^1<<i], reverse=True)[:2]
Ans = [sum(f[1])]
for a, b in f[2:]:
    Ans.append(max(Ans[-1], a+b))
print("\n".join(map(str, Ans)))
### BUGGY CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()
a = li()
a.sort()

s = sum(a)

q = ii()

from bisect import bisect_left, bisect_right
def bisect_find(a, x):
    i = bisect_left(a, x)
    if i == len(a):
        return -1
    elif a[i] != x:
        return -1
    return i

def bisect_r_find(a, x):
    i = bisect_right(a, x)
    # if i == len(a):
    #     return -1
    return i

for i in range(q):
    b,c = mi()


    # 左を探す
    l = bisect_find(a,b)
    # 右を探す
    if l != -1:
        r = bisect_r_find(a,b)
        # 個数をカウント
        count = r-l
        # 前回の合計との差を求める
        s = s + (c-b)*count

        # 配列を上書き
        a[l:r] = [c]*count
        a.sort()
    # print('-------------ans----------------',s)
    print(s)



    

### FIXED CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()
a = li()
q = ii()

s = sum(a)

m = [0] * (10**5 + 1)
for i in range(n):
    m[a[i]] += 1

for i in range(q):
    b,c = mi()

    if m[b] == 0:
        print(s)
    else:
        count = m[b]

        s = s + (c-b)*count
        print(s)

        m[c] += count
        m[b] = 0
### BUGGY CODE ###

# D - AtCoder Express 2

import numpy as np

N, M, Q = map(int, input().split())
L, R, = [], []
p, q = np.array([],np.int64), np.array([],np.int64)
for _ in range(M):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
for _ in range(Q):
    tmp_p, tmp_q = map(int, input().split())
    p = np.append(p, [tmp_p])
    q = np.append(q, [tmp_q])
    
train = np.zeros((N+1, N+1))
np.add.at(train, (L,R), 1)

np.cumsum(train, axis = 0, out = train)
np.cumsum(train, axis = 1, out = train)
    
ans = train[q,q] - train[p-1,q] - train[q,p-1] + train[p-1,p-1]
for i in range(Q):
    print(int(ans[i]))

### FIXED CODE ###

# D - AtCoder Express 2

import numpy as np

N, M, Q = map(int, input().split())
LR = np.zeros((N+1, N+1))

for _ in range(M):
    l, r = map(int, input().split())
    LR[l,r] += 1

np.cumsum(LR, axis = 0, out = LR)
np.cumsum(LR, axis = 1, out = LR)
    
for _ in range(Q):
    p, q = map(int, input().split())
    print(int(LR[q,q] - LR[p-1,q] - LR[q,p-1] + LR[p-1,p-1]))
### BUGGY CODE ###

from fractions import gcd
mod=10**9+7
def pow_r(x, n):
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r(x ** 2%mod, n // 2)%mod
    else:  # standard case ② n is odd
        return x * pow_r(x ** 2%mod, (n - 1) // 2)%mod
h,w,t=map(int,input().split())
groups=gcd(h,t)*gcd(w,t)
unit=(h//gcd(h,t),w//gcd(w,t))
cnt=(2**(unit[0])+2**(unit[1])-3)%mod
unitd=gcd(unit[0],unit[1])
cnt+=pow_r(2,unitd)%mod
print(pow_r(cnt,groups))


### FIXED CODE ###

from fractions import gcd
mod=10**9+7
def pow_r(x, n):
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r(x ** 2%mod, n // 2)%mod
    else:  # standard case ② n is odd
        return x * pow_r(x ** 2%mod, (n - 1) // 2)%mod
h,w,t=map(int,input().split())
groups=gcd(h,t)*gcd(w,t)
unit=(h//gcd(h,t),w//gcd(w,t))
cnt=(2**(unit[0])+2**(unit[1])-3)%mod
unitd=gcd(unit[0],unit[1])
cnt+=pow_r(2,unitd)%mod
print(pow_r(cnt,groups))
### BUGGY CODE ###

import sys
def Ii():return int(sys.stdin.buffer.read())
def Mi():return map(int,sys.stdin.buffer.readline().split())
def Li():return list(map(int,sys.stdin.buffer.readline().split()))

n,k = Mi()
a = Li()
b = [1]
b.append(a[0])
flag = False
for i in range(n):
  if len(b) > k:
    print(b[k])
    exit(0)
  for j in range(len(b)):
    if b[j] == a[b[-1]-1]:
      flag = True
      break
  if flag: 
    break
    
  b.append(a[b[-1]-1])

roop = len(b)-j
roopk = (k-j)%roop
print(b[roopk+j])

### FIXED CODE ###

import sys
def Ii():return int(sys.stdin.buffer.read())
def Mi():return map(int,sys.stdin.buffer.readline().split())
def Li():return list(map(int,sys.stdin.buffer.readline().split()))

n,k = Mi()
a = Li()
b = [1]
b.append(a[0])
flag = False
for i in range(n):b.append(a[b[-1]-1])
if len(b) > k:
  print(b[k])
  exit(0)
for j in range(len(b)):
  if b[j] == a[b[-1]-1]:
    break
    
roop = len(b)-j
roopk = (k-j)%roop
print(b[roopk+j])
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))

count = 0
for i in range(N):
  flag = 1
  for j in range(i+1):
    if P[i] > P[j]:
      flag = 0
      break
  if flag == 1:
    count+=1

print(count)


### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))

count = 1
if N == 1:
  print(count)
else:
  min = P[0]
  if P[1] <= P[0]:
    count+=1
    min = P[1]

  for i in range(2,N):
    if P[i] <= min:
      count+=1
      min = P[i]
  print(count)
### BUGGY CODE ###

from bisect import bisect_left
from heapq import heappush, heappop

N = int(input())
XD = [[int(i) for i in input().split()] for _ in range(N)]

mod = 998244353

XD.sort()

class SegTree:
  def __init__(self, n, v, f) :
    i = 1
    while i < n : 
      i <<= 1
    self.n = i
    self.v = v
    self.f = f
    self.tree = [v] * (i << 1)

  def update(self, i, x) :
    i += self.n - 1
    self.tree[i] = x
    while i > 0 :
      i = (i - 1) // 2
      self.tree[i] = self.f(self.tree[i * 2 + 1], self.tree[i * 2 + 2])

  # [l, r)
  def query(self, l, r) :
    l = l + self.n
    r = r + self.n
    s = self.v
    while l < r :
      if r & 1 :
        r -= 1
        s = self.f(s, self.tree[r - 1])
      if l & 1 :
        s = self.f(s, self.tree[l - 1])
        l += 1
      l >>= 1
      r >>= 1
    return s

INF = 1 << 60
ST = SegTree(N, -INF, max)

xs = [x for x, _ in XD]
dest = [0] * N
for i in range(N - 1, -1, -1) :
  x, d = XD[i]
  j = bisect_left(xs, x + d) - 1
  if i == j :
    dest[i] = x + d
  else :
    dest[i] = ST.query(i, j + 1)
  ST.update(i, dest[i])

ret = 1
q = []
for i, (x, d) in enumerate(XD) :
  while q and q[0][0] <= x :
    ret += heappop(q)[1]
    ret %= mod
  heappush(q, (dest[i], ret))

while q :
  ret += heappop(q)[1]
  ret %= mod

print(ret % mod)

### FIXED CODE ###

from bisect import bisect_left
import sys
input = sys.stdin.readline

N = int(input())
XD = [[int(i) for i in input().split()] for _ in range(N)]

mod = 998244353

XD.sort()

class SegTree:
  def __init__(self, n, v, f) :
    i = 1
    while i < n : 
      i <<= 1
    self.n = i
    self.v = v
    self.f = f
    self.tree = [v] * (i << 1)

  def update(self, i, x) :
    i += self.n - 1
    self.tree[i] = x
    while i > 0 :
      i = (i - 1) // 2
      self.tree[i] = self.f(self.tree[i * 2 + 1], self.tree[i * 2 + 2])

  # [l, r)
  def query(self, l, r) :
    l = l + self.n
    r = r + self.n
    s = self.v
    while l < r :
      if r & 1 :
        r -= 1
        s = self.f(s, self.tree[r - 1])
      if l & 1 :
        s = self.f(s, self.tree[l - 1])
        l += 1
      l >>= 1
      r >>= 1
    return s

INF = 1 << 60
ST = SegTree(N, -INF, max)

xs = [x for x, _ in XD]
for i in range(N - 1, -1, -1) :
  x, d = XD[i]
  j = bisect_left(xs, x + d)
  ST.update(i, max(i, ST.query(i, j)))

dp = [0] * (N + 1)
dp[N] = 1

for i in range(N) :
  dp[i] += dp[i - 1]
  dp[i] %= mod
  j = ST.query(i, i + 1)
  dp[j] += dp[i - 1]
  dp[j] %= mod

print(dp[N-1])