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

import numpy as np

n = int(input())
arr = np.array([int(input()) for _ in range(n)])

a_max = arr.max()

idx = np.where(arr == a_max)[0]

not_arr = arr[arr != a_max]

if len(not_arr) != 0:
    b_max = not_arr.max()

if len(idx) > 1:
    for i in range(n):
        print(a_max)
else:
    for i in range(n):
        if i in idx:
            print(b_max)
        else:
            print(a_max)


### FIXED CODE ###

import numpy as np

n = int(input())
arr = np.array([int(input()) for _ in range(n)])

a_max = arr.max()

idx = np.where(arr == a_max)[0]

if len(idx) > 1:
    for i in range(n):
        print(a_max)

    exit()

not_arr = arr[arr != a_max]

b_max = not_arr.max()

t = idx[0]
for i in range(n):
    if i == t:
        print(b_max)
    else:
        print(a_max)
### BUGGY CODE ###

from heapq import heapify, heappush, heappop
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
events = []
for iR in range(N):
    S, T, X = map(int, input().split())
    events.append((S-X, 0, X, iR))
    events.append((T-X, 1, -X, iR))
events.sort()

iE = 0
isActives = [False] * N
anss = []
PQ = []
for _ in range(Q):
    D = int(input())
    while iE < 2*N and events[iE][0] <= D:
        tm, ST, x, iR = events[iE]
        if ST == 0:
            isActives[iR] = True
            heappush(PQ, (x, iR))
        else:
            isActives[iR] = False
        iE += 1

    xMin = -1
    while PQ:
        x, iR = heappop(PQ)
        if isActives[iR]:
            xMin = x
            heappush(PQ, (x, iR))
            break
    anss.append(xMin)

print('\n'.join(map(str, anss)))


### FIXED CODE ###

from heapq import heapify, heappush, heappop
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
events = []
for iR in range(N):
    S, T, X = map(int, input().split())
    events.append((S-X, T-X, X))
events.sort()

iE = 0
anss = []
PQ = []
for _ in range(Q):
    D = int(input())
    while iE < N and events[iE][0] <= D:
        tmSt, tmEn, x = events[iE]
        heappush(PQ, (x, tmEn))
        iE += 1

    xMin = -1
    while PQ:
        x, tmEn = heappop(PQ)
        if tmEn > D:
            xMin = x
            heappush(PQ, (x, tmEn))
            break
    anss.append(xMin)

print('\n'.join(map(str, anss)))
### BUGGY CODE ###

n = int(input())
s = ["".join(sorted(input())) for i in range(n)]
s = sorted(s)
cnt = 0
for i in range(len(s)):
    for j in s[i + 1:]:
        if s[i] == j:
            cnt += 1
        else:
            break
print(cnt)


### FIXED CODE ###

from collections import Counter

total = 0
n = int(input())
word_list = ["".join(sorted(input())) for _ in range(n)]
count_words = dict(Counter(word_list))
for item in count_words:
    ans = 0
    tmp = count_words[item] - 1
    ans = 1/2 * tmp * (tmp + 1)
    total += ans
print(int(total))
### BUGGY CODE ###

from fractions import gcd
from functools import lru_cache

M = 10 ** 9 + 7

@lru_cache(maxsize=None)
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

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

lcm_ = A[0]
for a in A[1:]:
    lcm_ = lcm_ * a // gcd(lcm_, a)

ans = 0
for a in A:
    m = modinv(a, 10 ** 9 + 7)
    ans = (ans + lcm_ * m) % M

print(ans)

### FIXED CODE ###

from fractions import gcd

M = 10 ** 9 + 7

def xgcd(a, b):
    x0, x1 = 1, 0
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
    return x0 % M

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

lcm_ = A[0]
for a in A[1:]:
    lcm_ = lcm_ * a // gcd(lcm_, a)

ans = 0
for a in A:
    m = xgcd(a, M)
    ans = ans + lcm_ * m

print(ans % M)
### BUGGY CODE ###

import math
n, m = map(int, input().split())
a = list(float(x) for x in input().split())
a.sort(reverse=True)
for i in range(m):
    a[0] = a[0]/2
    for j in range(n-1):
        if a[j] < a[j+1]:
            a[j], a[j+1] = a[j+1], a[j]
        else:
            break
ans = 0
for i in range(n):
    ans += math.floor(a[i])
print(ans)

### FIXED CODE ###

import math
n, m = map(int, input().split())
a = list(float(x) for x in input().split())
a.sort(reverse=True)
while m > 0:
    for i in range(n):
        if a[i] >= a[0]:
            a[i] = a[i] / 2
            m -= 1
            if m == 0:
                break
        else:
            a.sort(reverse=True)
            break
ans = 0
for i in range(n):
    ans += int(math.floor(a[i]))
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
import numpy as np
for i in range(n):
    print(int(np.median(a[0:i] + a[i+1:])))

### FIXED CODE ###

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

b = sorted(a)
m1 = b[n // 2]
m2 = b[n // 2 - 1]

for num in a:
    if(num < m1):
        print(m1)
    else:
        print(m2)
### BUGGY CODE ###

def m(list1,n): 
    mul=1
    for i in range(n): 
         mul=mul*list1[i] 
    return mul 
      
n=int(input())
arr=list(map(int,input().split()))
if m(arr,n)>pow(10,18):
    print(-1)
else:
    print(m(arr,n)) 
 


### FIXED CODE ###

n=int(input())
arr=list(map(int,input().split()))
ans=int(1)
temp=int(0)
for i in range(n):
  if(ans>(10**18)):
    ans=-1
  if(ans!=-1):
  	ans*=arr[i]
  if(arr[i]==0):
    temp=int(1)
if(ans>(10**18)):
  ans=-1
if(temp==1):
  ans=0
print(int(ans))
### BUGGY CODE ###

N = int(input())
S = []
for i in range(N):
    x = input()
    if x not in S:
        S.append(x)
print(len(S))

### FIXED CODE ###

import collections

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

print(len(collections.Counter(S)))
### BUGGY CODE ###

n=int(input())
s=[int(input()) for i in range(n)]
l=[]
for x in s:
    l=set([x])^set(l)
print(len(l))

### FIXED CODE ###

import collections
n=int(input())
s=[int(input()) for i in range(n)]
p=collections.Counter(s)
c=0
for x in p.values():
    if x%2==1:c+=1
print(c)
### BUGGY CODE ###

S = str(input())
N = len(S)
H = [1] * N
list1 = [H]

def roop(s,h,n):
  h_new = [0]*n
  if s[1] == "L":
    h_new[0] = h[1]
  if s[n-2] == "R":
    h_new[n-1] = h[n-2]
  for i in range(1,n-1):
    l, r = 0, 0
    if s[i-1] == "R":
      r = 1
    if s[i+1] == "L":
      l = 1
    h_new[i] = h[i-1]*r+ h[i+1]*l 
  return h_new
H = roop(S,H,N)

while H not in list1:
  list1.append(H)
  H = roop(S,H,N)
  
num = list1.index(H)
if (num-1) % 2 == 0:
  H = list1[-1]
  
for i in range(N):
  print(H[i], end = " ")


### FIXED CODE ###

S = str(input())
N = len(S)

con = []
border = []
for i in range(N - 1):
  if S[i] == "L" and S[i + 1] == "R":
    border.append(i)
  elif S[i] == "R" and S[i + 1] == "L":
    con.append(i)
  
border.append(N - 1)  

#print(border, con)    

ans = [0] * N
now = -1
for i in range(len(con)):
  #con[i] と con[i] + 1 に
  #now - border[i] の数があつまる。
  pp = border[i] - now
  if pp % 2 == 0:
    ans[con[i]] += pp / 2
    ans[con[i] + 1] += pp / 2
  else:
    if (con[i] - now) % 2 == 0:
      ans[con[i]] += (pp - 1) / 2
      ans[con[i] + 1] += (pp + 1) / 2     
    else:
      ans[con[i]] += (pp + 1) / 2
      ans[con[i] + 1] += (pp - 1) / 2       
  now = border[i]
  #print(pp, ans)  
  
  
for i in range(N):
  print(int(ans[i]), end = " ")
### BUGGY CODE ###

S = input()

begginingLength = len(S)

while "01" in S:
    S = S.replace("01","")

while "10" in S:
    S = S.replace("10","")

endLength = len(S)

ans = begginingLength - endLength
print(ans)


### FIXED CODE ###

S = input()

ones = S.count("1")
zeros = S.count("0")

ans = min(ones,zeros)*2
print(ans)
### BUGGY CODE ###

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

if (k == 1):
    print(2)
    exit()

if (b <= (a + 1)):
    print(k + 1)
    exit()
else:
    bis = 1
    mon = 0
    for i in range(k):
        if(1 <= mon):
            mon -= 1
            bis += b
        elif(a <= bis and i != (k-1)):
            bis -= a
            mon += 1
        else:
            bis += 1
    print(bis)

### FIXED CODE ###

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

if (k == 1):
    print(2)
    exit()

if (b <= (a + 1)):
    print(k + 1)
    exit()
else:
    tmp1 = k - (a - 1)
    sabun = b - a

    if (tmp1 % 2 == 0):
        bis = int((tmp1 / 2 - 1)) * int(sabun) + b
    else:
        zouka = int((tmp1 // 2 - 1)) * int(sabun)
        bis = zouka + b + 1

    print(bis)
### BUGGY CODE ###

N=int(input())
alist=list(map(int, input().split()))
alist.sort()
for i in range(1,N+1):
    ans=alist.count(i)
    print(ans)
    alist=alist[ans:]


### FIXED CODE ###

N=int(input())
alist=list(map(int, input().split()))
anslist=[0]*N
for a in alist:
    anslist[a-1]+=1
for ans in anslist:
    print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    
    L = [A.pop(0)]
    ma = L[0]
    for a in A:
        if ma >= a:
            ma = a
            L.append(ma)
            continue
        for i, l in enumerate(L):
            if l < a:
                L[i] = a
                if l == ma:
                    ma = min(L)
                break
        else:
            L.append(a)
    return len(L)


def main():
    N = read_int()
    A = [read_int() for _ in range(N)]
    print(slv(N, A))

    # N = 10**5
    # A = [random.randint(1, 10**9) for _ in range(N//2)]
    # A.sort()
    # A.reverse()
    # A += [random.randint(1, 10**9) for _ in range(N//2)]
    # print(slv(N, A))


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


# @mt
def slv(N, A):
    
    L = [-A.pop(0)]
    ma = L[0]
    for a in A:
        if ma <= -a:
            ma = -a
            L.append(ma)
            continue
        i = bisect.bisect_right(L, -a)
        L[i] = -a
        ma = L[-1]
    return len(L)



def main():
    N = read_int()
    A = [read_int() for _ in range(N)]
    print(slv(N, A))


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

S = input()
N=len(S)
M = [0 for _ in range(2019)]
# 0は予め右端に一個あるとする
M[0]+=1
for i,s in enumerate(S):
    new = int(S[i:])%2019
    M[new] += 1
count = 0
for m in M:
    count += int(m*(m-1)/2)
print(count)


### FIXED CODE ###

S = input()
N=len(S)
M = [0 for _ in range(2019)]
# 0は予め右端に一個あるとする
M[0]+=1
old = 0
for i in range(N):
    new_s = int(S[N-1-i])*pow(10,i,2019)
    new = (new_s + old) % 2019
    M[new] += 1
    old = new
count = 0
for m in M:
    count += int(m*(m-1)/2)
print(count)
### BUGGY CODE ###

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

same = N / 2

d.sort()

distribution = [0] * d[len(d) - 1]
total = 0
for di in d:
    num = d.count(di)
    distribution[di - 1] = num

total = 0
totals = [0] * d[len(d) - 1]
num = 0
for i in range(len(distribution)):
    total += distribution[i]
    totals[i] = total

    if totals[i] == same:
        num += 1
    elif num >= 1:
        break

print(num)


### FIXED CODE ###

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

same = N / 2

# d.sort()

# distribution = [0] * d[len(d) - 1]
# total = 0
# for di in d:
#     num = d.count(di)
#     distribution[di - 1] = num

table = {}
for di in d:
    table[di] = 1 if table.get(di) is None else table.get(di) + 1
table = sorted(table.items())

total = 0
start = 0
end = 0
for difficulty, num in table:
    total += num

    if start == 0 and total == same:
        start = difficulty
    elif start != 0:
        end = difficulty
        break

# print(table, start, end)

answer = end - start
print(answer)
### BUGGY CODE ###

a,b = map(int,input().split())
minv = min(a,b)
maxv = max(a,b)
kouyaku = []
ans = []
#公約数を求める
for i in range(1,(minv//2)+1):
    if a%i==0  and b%i==0:
        kouyaku.append(i)
#print(*kouyaku)
#互いに素になる数字を探す
i = 0
j = 1
kouyaku = kouyaku[1:]
while len(kouyaku)>i:
    while len(kouyaku)>j:
        if kouyaku[j]%kouyaku[i]==0:
            #print(kouyaku[j])
            kouyaku.remove(kouyaku[j])
            j -=1
        j +=1
    i += 1
    j = i+1
print(len(kouyaku)+1)

### FIXED CODE ###

def prime(n):
    res =set()
    while n% 2==0:
        res.add(2)
        n //= 2
    i  = 3
    while i*i <= n:
        if n % i==0:
            res.add(i)
            n //= i
        else:
            i += 2
    if n != 1:
        res.add(n)
    return res
a,b = map(int,input().split())
a = prime(a)
b = prime(b)
print(len(a&b)+1)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
L_over = []
L_short = []
for i in range(n):
    c = A[i] - B[i]
    if c > 0:
        L_over.append(c)
    elif c < 0:
        L_short.append(-c)
L_over.sort(reverse=True)
if sum(L_over) < sum(L_short):
    print(-1)
else:
    cnt = len(L_short)
    p = 0
    for i in range(len(L_over)):
        if p >= sum(L_short):
            break
        p += L_over[i]
        cnt += 1
    print(cnt)


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
over = []
short = 0
cnt = 0
for i in range(n):
    c = A[i] - B[i]
    if c > 0:
        over.append(c)
    elif c < 0:
        short -= c
        cnt += 1
if sum(over) < short:
    print(-1)
else:
    over.sort(reverse=True)
    s = 0
    i = 0
    while s < short:
        s += over[i]
        i += 1
    cnt += i
    print(cnt)
### BUGGY CODE ###

#bitでタコ殴りにする
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length()
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
    def lower_bound(self, x):
        """ 累積和がx以上になる最小のindexと、その直前までの累積和 """
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1, sum_

m=998244353    
N,K=map(int,input().split())
bit = Bit(N)
bit.add(1,1)#初期値　はじめは１
period = []
for _ in range(K):#動ける区間の記憶
    l,r=map(int,input().split())
    period.append((l,r))
for i in range(2,N+1):#2からNまで見ていく。もらうDP
    for l,r in period:
        rx = max(0,i-l)
        lx = max(0,i-r-1)
        if rx==0:
            tmp_r = 0
        else:
            tmp_r = bit.sum(rx)
        if lx == 0:
            tmp_l = 0
        else:
            tmp_l = bit.sum(lx)
        bit.add(i,(tmp_r-tmp_l)%m)
ans = (bit.sum(N)-bit.sum(N-1))%m
print(ans)





### FIXED CODE ###

N,K = map(int,input().split())
DP = [0]*(N+1)
DPsum=[0]*(N+1)
DP[1]=1
DPsum[1]=1
lr = []
m=998244353
for _ in range(K):
    l,r = map(int,input().split())
    lr.append([l,r])

for i in range(2,N+1):
    for l,r in lr:
        lx = i - r - 1
        rx = i - l
        lx = max(0,lx)
        rx = max(0,rx)
        DP[i]+= DPsum[rx]-DPsum[lx]
    DPsum[i]=(DPsum[i-1]+DP[i])%m
print(DP[N]%m)
### BUGGY CODE ###

N,start = [int(x) for x in input().split()]
_x = [int(y) for y in input().split()]
x = sorted(_x)
dis = [0 for z in range(N-1)]
z = [0 for z in range(N)]
ans = 1
if N == 1:
    print(abs(x[0]-start))
else:
    for i in range(N-1):
        dis[i] = x[i+1] - x[i]
    for i in range(N):
        z[i] = abs(x[i]-start)
    D = min(dis)
    ans = 1
    for d in reversed(range(2,D+1)):
        count = 0
        for j in range(N):
            if z[j] % d == 0:
                count += 1
            else:
                break
        if count == N:
            ans = d
            break
    print(ans)


### FIXED CODE ###

import math
N,start = [int(x) for x in input().split()]
_x = [int(y) for y in input().split()]
x = [0 for y in range(N)]
for i in range(N):
    x[i] = abs(_x[i] - start)
g = x[0]
for i in range(N):
    g = math.gcd(g,x[i])
print(g)
ans = 1
### BUGGY CODE ###

import functools

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
    b = a[i]
    a.remove(b)
    c = functools.reduce(gcd, a)
    if ans < c:
        ans = c
    a.insert(i,b)
print(ans)

### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

n = int(input())
a = list(map(int, input().split()))
a.sort()
if n == 2:
    print(max(a))
else:
    a1 = gcd(a[0],a[1])
    a2 = gcd(a[1],a[2])
    a3 = gcd(a[2],a[0])
    m = max(a1,a2,a3)
    judge = 0
    for i in range(m):
        if judge == 1:
            break
        cnt = 0
        for j in range(n):
            if a[j] % (m-i) != 0:
                cnt += 1
            if cnt > 1:
                break
            if j == n-1 and cnt <= 1:
                print(m-i)
                judge = 1
### BUGGY CODE ###

S=input()
S=list(S)
dp=[]
for _ in range(len(S)):
    dp.append([0]*13)
if S[0]=='?':
    for i in range(10):
        dp[0][(i*10**(len(S)-1))%13]=1
else:
    dp[0][(int(S[0])*10**(len(S)-1))%13]=1
for j in range(0,len(S)-1):
    for k in range(13):
        if S[j+1]=='?':
            L=[]
            for l in range(10):
                l=(l*10**(len(S)-j-2)%13)
                L.append(dp[j][k-l])
            dp[j+1][k]+=sum(L)%(7+10**9)
        else:
            dp[j+1][k]=dp[j][k-(int(S[j+1]))*10**(len(S)-j-2)%13]
print((dp[len(S)-1][5])%(7+10**9))

### FIXED CODE ###

def main():
    MOD = 7 + 10**9
    S = tuple(input())
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] += 1
    s=[1]
    for n in range(1,N):
        s.append((s[n-1]*10)%13)
    for i in range(N):
        for k in range(13):
            if S[-(i+1)] != '?':
                dp[i+1][(k+int(S[-(i+1)])*s[i])%13] += dp[i][k] 
                dp[i+1][(k+int(S[-(i+1)])*s[i])%13] %= MOD
            else:
                for l in range(10):
                    dp[i+1][(k+l*s[i])%13] += dp[i][k]
                    dp[i+1][(k+l*s[i])%13] %= MOD
    print(dp[-1][5])

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

import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    

def main():
    N, K = MI()
    L = [LI() for i in range(K)]
    D = [0] * N
    D[0] = 1
    D[1] = -1
    num = 0
    for index in range(N):
        num += D[index]
        for l, r in L:
            if index + r + 1 <= N-1:
                D[index+l] += num
                D[index+r+1] -= num
            elif index+l <= N-1:
                D[index+l] += num
                
    print(num % 998244353)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    

def main():
    N, K = MI()
    L = [LI() for i in range(K)]
    D = [0] * N
    D[0] = 1
    D[1] = -1
    num = 0
    mod = 998244353
    for index in range(N):
        num += D[index] % mod
        for l, r in L:
            if index + r + 1 <= N-1:
                D[index+l] += num
                D[index+r+1] -= num
            elif index+l <= N-1:
                D[index+l] += num
                
    print(num % mod)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N = int(input())
num = [1 for _ in range(N + 1)]
for i in range(2, N + 1):
    cnt = 1
    while cnt * i <= N:
        num[cnt * i] += 1
        cnt += 1
ans = 0
for i in range(1, N + 1):
    ans += num[i] * i
print(ans)


### FIXED CODE ###

N = int(input())
ans = 0
for i in range(1, N + 1):
    largest = N // i * i
    ans += ((largest + i) * (N // i)) // 2
print(ans)
### BUGGY CODE ###

def ct(num):
    primel=[2]
    for i in range(num):
        n=i+1
        if i==0 or i==1:continue 
        for e in primel:
            if n%e==0:break
        else:primel.append(n)
    return len(primel)        
    
while True:
    try:raw=[int(i) for i in input().split(" ")]
    except:break
    a=raw[0]
    print(str(ct(a)))

### FIXED CODE ###


import math

m=999999
s=int(math.sqrt(m)+1)
li=[0]*m
li[0]=1
for i in range(1,s):
    if li[i]==0:
        li[i*2+1::i+1]=[1 for e in range(len(li[i*2+1::i+1]))]
while True:
    try:n=int(input())
    except:break
    print(len([i for i in li[:n:] if i==0]))