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

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

a.sort()

import collections
c = collections.Counter(a)

d=[]
for ck,cv in c.items():
    if cv>=2:
       d.append(ck) 
dset=set(d)
    
aa=[]

icnt=0
while True:
    aa.append(a[0])
    a2=[]
    for i in range(1,len(a)):
        if a[i]%a[0]!=0:
            a2.append(a[i])
    a=a2.copy()
#    print(aa,a)     
    if len(a2)==0:
        break
    icnt+=1
#    if icnt>10:break

aaset=set(aa)
aaset=aaset-dset    
print(len(aaset))


### FIXED CODE ###

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

a.sort()
amax=max(a)
dp=[True]*(amax+1)

import collections
c = collections.Counter(a)

d=[]
for ck,cv in c.items():
    if cv>=2:
       d.append(ck) 
dset=set(d)
    
aa=set()
for ai in a:
    if dp[ai]:
        aa.add(ai)
        for aj in range(ai*2,amax+1,ai):
            dp[aj]=False

aa=aa-dset    
print(len(aa))
### BUGGY CODE ###

import fractions
n=int(input())
mod=1000000007
sum=0
s=[int(n) for n in input().split()]
ans=1
for i in s:
    ans*=i//fractions.gcd(ans,i)
for i in s:
    sum=(sum+ans//i)%mod
print(sum)


### FIXED CODE ###

n=int(input())
a=[int(j) for j in input().split()]
t=1
mod=10**9+7
from fractions import*
for i in a:
    t*=i//gcd(t,i)
print(sum(t//i for i in a)%mod)
### BUGGY CODE ###

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

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

buffer = sys.stdin.buffer
H,W = map(int,buffer.readline().split())
C = np.frombuffer(buffer.read(),dtype='S1').reshape(H,-1)[:,:W].T

equal = np.empty((H,H,W-1),dtype=np.bool)
for n in range(W-1):
    equal[:,:,n] = (C[n][:,None] == C[n+1][None,:])
dp_1 = np.zeros((H+H+1,H+H+1,W-1),dtype=np.int64)
L = np.arange(1,H+1)
R = np.arange(1,H+1)
dp_1[R[None,:]-L[:,None]+H,R[None,:]+L[:,None],:] = equal
np.cumsum(dp_1,out=dp_1,axis=1)

INF = 10**18
# R-L+H -> min cost
dp = np.full((H+H+1,W-1),INF,dtype=np.int64)
dp[H] = 0
for n in range(1,H+H+1):
    # n個目を置く
    prev = dp
    dp = np.full((H+H+1,W-1),INF,dtype=np.int64)
    dp[1:,:] = np.minimum(dp[1:,:],prev[:-1,:])
    dp[:-1,:] = np.minimum(dp[:-1,:],prev[1:,:])
    dp += dp_1[:,n,:]

answer = dp[H].sum()
print(answer)

### FIXED CODE ###

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

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

buffer = sys.stdin.buffer
H,W = map(int,buffer.readline().split())
C = np.frombuffer(buffer.read(),dtype='S1').reshape(H,-1)[:,:W].T

dp_1 = np.zeros((W-1,H+H+1,H+1),dtype=np.int64)
for r in range(H):
    dp_1[:,r+2:r+H+2,r+1] = (C[:-1] == C[1:,r][:,None])

INF = 10**18
# R-L+H -> min cost
dp = np.full((W-1,H+1),INF,dtype=np.int64)
dp[:,0] = 0
for n in range(1,H+H+1):
    if n >= 2:
        dp_1[:,n,1:] += dp_1[:,n-2,:-1]
    # n個目を置く
    prev = dp
    dp = np.full((W-1,H+1),INF,dtype=np.int64)
    dp[:,1:] = np.minimum(dp[:,1:],prev[:,:-1])
    dp[:,:] = np.minimum(dp[:,:],prev[:,:])
    dp += dp_1[:,n,:]
answer = dp[:,H].sum()
print(answer)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

count = 0
for i in range(N):
    for j in range(N):
        if a[i] >= b[j]:
            continue
        for k in range(N):
            if b[j] < c[k]:
                count += 1
print(count)


### FIXED CODE ###

from bisect import bisect_left, bisect_right # 2文探索法モジュール
N = int(input())
a = sorted(list(map(int, input().split()))) # ソートしておく
b = list(map(int, input().split()))
c = sorted(list(map(int, input().split()))) # ソートしておく

count = 0
for b_item in b:
    i = bisect_left(a, b_item) # リストaのb_itemより小さい要素の数
    j = N - bisect_right(c, b_item) # リストcのb_itemより大きい要素の数
    count += (i * j)
print(count)
### BUGGY CODE ###

import sys
n = int(input())
ls = [int(input()) for _ in range(n)]
if 2 not in ls:
    print(-1)
    sys.exit()
i = 1
k = 0
di = []
for j in range(n):
    i = ls[i-1]
    if i in di:
        print(-1)
        break
    di.append(i)
    k += 1
    if i == 2:
        print(k)
        break

### FIXED CODE ###

import sys
n = int(input())
ls = [int(input()) for _ in range(n)]
if 2 not in ls:
    print(-1)
    sys.exit()
i = 1
k = 0
for j in range(n):
    i = ls[i-1]
    k += 1
    if i == 2:
        print(k)
        sys.exit()
print(-1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
k = [0] * n
cnt = 0
for i in range(n):
    for j in range(i):
        if i == j:
            continue
        if k[i] == 0 and a[i] % a[j] == 0:
            cnt += 1
            k[i] = 1
        if k[j] == 0 and a[j] % a[i] == 0:
            cnt += 1
            k[j] = 1
print(n - cnt)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a = [int(x) for x in input().split()]
maxval = 10 ** 6
factor_cnt = [0] * (maxval+1)
factor_cnt[0] = 2
for i in range(n):
    if factor_cnt[a[i]] > 1:
        continue
    for k in range(a[i], maxval+1, a[i]):
        factor_cnt[k] += 1

result = sum(factor_cnt[v] <= 1 for v in a)
print(result)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
result = 1
checker =False
for j in a:
  if j > 1000000000000000000:
    result = -1
    checker =True
if 0 in a:
  result = 0
  checker=True
while checker==False:
  for i in range(len(a)):
    result *= a[i]
  checker = True
    

if result <= 1000000000000000000:
  print(result)
else:
  print(-1)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
result = 1
for i in range(len(a)):
  result = result*a[i]
  if result == 0:
    break
  elif result > 1000000000000000000:
    break

if result <= 1000000000000000000:
  print(result)
else:
  print(-1)
### BUGGY CODE ###

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

ans = 0
import itertools
for i in itertools.combinations(a_list, 2):
    ans += i[0] * i[1]
print(ans % (10**9 + 7))

### FIXED CODE ###

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

s_2 = 0
for i in a_list:
    s_2 += i**2

ans = (sum(a_list)**2 - s_2)//2  

ans = ans%(10**9+7)
print(ans)
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N, K = MAP()
h = LIST()

dp = [INF]*(N)

dp[0] = 0

for i in range(1, min(K, len(h))):
	dp[i] = min([dp[j]+abs(h[i]-h[j]) for j in range(i)]) 

for i in range(K, N):
	dp[i] = min([dp[i-j]+abs(h[i]-h[i-j]) for j in range(1, K+1)])
	
#print(dp)
print(dp[N-1])

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N, K = MAP()
h = LIST()

dp = [INF]*(N)

dp[0] = 0

for i in range(1, min(K, len(h))):
	dp[i] = min([dp[j]+abs(h[i]-h[j]) for j in range(i)]) 

for i in range(K, N):
	dp[i] = min([dp[i-j]+abs(h[i]-h[i-j]) for j in range(1, K+1)])
	
#print(dp)
print(dp[N-1])
### BUGGY CODE ###

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

p = [v - (i + 1) for i, v in enumerate(A)]

res = sum(map(abs, [i - statistics.median(p) for i in p]))
print(int(res))

### FIXED CODE ###

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

p = sorted([v - (i + 1) for i, v in enumerate(A)])

if len(p) >= 3:
    res = min(sum(map(abs, [i - p[N//2] for i in p])), sum(map(abs, [i - p[N//2-1] for i in p])), sum(map(abs, [i - p[N//2+1] for i in p])))
elif len(p) >= 2:
    res = min(sum(map(abs, [i - p[0] for i in p])), sum(map(abs, [i - p[1] for i in p])))
else:
    res = 0
print(int(res))
### BUGGY CODE ###


S = str(input())
Q = int(input())
query=[]

for line in range(Q):
	query.append(list(input().split()))

for i in range(Q):
	q=query[i]
	if int(q[0])==1:
		S=S[::-1]
	else:
		if int(q[1])==1:
			S=q[2]+S
		else:
			S=S+q[2]
print(S)




### FIXED CODE ###


S = str(input())
Q = int(input())
query=[]
a=""
b=""
# for line in range(Q):
# 	query.append(list(input().split()))
t=True

for i in range(Q):
	q=list(input().split())
	if int(q[0])==1:
		t= not t
	else:
		if int(q[1])==1:
			if t:
				a=q[2]+a
			else:
				b=b+q[2]

		else:
			if t:
				b=b+q[2]
			else:
				a=q[2]+a

if t:
	print(a+S+b)
else:
	print(b[::-1]+S[::-1]+a[::-1])
### BUGGY CODE ###

def solve():
    from sys import stdin
    f_i = stdin
    
    H, W = map(int, f_i.readline().split())
    A = tuple(tuple(map(int, f_i.readline().split())) for i in range(H))
    B = tuple(tuple(map(int, f_i.readline().split())) for i in range(H))
    
    dp1 = [dict() for i in range(W)]
    dp1[0][0] = True
    for A_i, B_i in zip(A, B):
        dp2 = [dict() for i in range(W)]
        diff = A_i[0] - B_i[0]
        for pre_bias in dp1[0]:
            dp2[0][abs(pre_bias + diff)] = True
            dp2[0][abs(pre_bias - diff)] = True
        for j, t in enumerate(zip(A_i[1:], B_i[1:]), start=1):
            A_ij, B_ij = t
            diff = A_ij - B_ij
            for pre_bias in dp1[j]:
                dp2[j][abs(pre_bias + diff)] = True
                dp2[j][abs(pre_bias - diff)] = True
            for pre_bias in dp2[j-1]:
                dp2[j][abs(pre_bias + diff)] = True
                dp2[j][abs(pre_bias - diff)] = True
        dp1 = dp2
    
    print(min(dp2[-1]))

solve()

### FIXED CODE ###

def solve():
    from sys import stdin
    f_i = stdin
    
    H, W = map(int, f_i.readline().split())
    A = tuple(tuple(map(int, f_i.readline().split())) for i in range(H))
    B = tuple(tuple(map(int, f_i.readline().split())) for i in range(H))
    
    dp1 = [0] * W
    bit_width = 80 * (H + W - 2)
    dp1[0] = 1 << (bit_width)
    for A_i, B_i in zip(A, B):
        dp2 = [0] * W
        
        diff = abs(A_i[0] - B_i[0])
        dp2[0] = (dp1[0] << diff) | (dp1[0] >> diff)
        
        for j, t in enumerate(zip(A_i[1:], B_i[1:]), start=1):
            A_ij, B_ij = t
            diff = abs(A_ij - B_ij)
            b = dp1[j] | dp2[j-1]
            dp2[j] = (b << diff) | (b >> diff)
        
        dp1 = dp2
    
    b = bin(dp2[-1])
    b = b[-bit_width-1:]
    print(b.index('1'))
 
solve()
### BUGGY CODE ###


def keisan(a):
    a.sort(reverse = True)
    ans = 0
    for i in range(0,n,2):
        if a.count(a[i]) >= 4:
            ans = a[i]*a[i]
            break
        elif a.count(a[i]) >=2:
            if a.count(a[i]) ==3:
                i+=1
            for j in range(i+a.count(a[i]),n,2):
                if a.count(a[j]) >=2:
                    ans = a[i]*a[j]
                    break
            break
    print(ans)

n = int(input())
in_ = [int(i) for i in input().split()]
keisan(in_)

### FIXED CODE ###

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

a.sort(reverse = True)
ans = 0
b = a.copy()
b = list(set(b))
b.sort(reverse = True)
c = [0]*len(b)
j = 0
c[j] = 1
for i in range(1,n):
    if a[i-1] == a[i]:
        c[j] +=1
    else:
        j+=1
        c[j] +=1
for i in range(len(b)):
    if c[i] >= 4:    
        
        ans = b[i]*b[i]
        break
    elif c[i] >= 2:
        for j in range(i+1,len(b)):
            if c[j] >= 2:
                ans = b[i]*b[j]
                break
        break
print(ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(2*10**9)

def main():
    N = int(input())
    A = sorted(input().split(" "))
    ans = [0]*N
    for i in range(N):
        tmp = A[i]
        if (i == N-1):
            A[i] = A[N-2]
        else :
            A[i] = A[N-1]
        ans.append(recursive_gcd(N,A))
        A[i] = tmp
    print(max(ans))


def recursive_gcd(n,array):
    if (n <= 2):
        return gcd_euclid(int(array[0]),int(array[1]))
    else:
        return gcd_euclid(recursive_gcd(n-1,array),int(array[n-1]))

# http://d.hatena.ne.jp/sh-2/20100320/1269039543 から引用
def gcd_euclid(u, v) :
  while (0 != v) :
    r = u % v
    u = v
    v = r
  return u
#引用ここまで

if __name__ == "__main__":
    main()

### FIXED CODE ###

from fractions import gcd as m_gcd

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


def gcd(a, b):
    if a == 0 or b == 0:
        return max(a, b)
    return m_gcd(a, b)


l = [0] * (n + 2)
r = [0] * (n + 2)
ans = [0] * n

for i in range(1, n+1):
    l[i] = gcd(l[i - 1], a[i - 1])
    r[n - i + 1] = gcd(r[n - i + 2], a[n - i])

for i in range(1, n + 1):
    ans[i-1] = gcd(l[i-1], r[i+1])

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

s = list(input())
q = int(input())

rev = 0

for i in range(q):
    t = list(input().split())
    if t == ['1']:
        rev += 1
        continue
    if t[1] == '1':
        if rev % 2 == 0:
            s = [t[2]] + s
        else:
            s.append(t[2])

    else:
        if rev % 2 == 0:
            s.append(t[2])
        else:
            s = [t[2]] + s
if rev % 2 != 0:
    s.reverse()

print(''.join(s))


### FIXED CODE ###

from collections import deque
s = list(input())
q = int(input())

s = deque(s)
rev = 0

for i in range(q):
    t = list(input().split())
    if len(t) == 1:
        rev += 1
        continue
    if t[1] == '1':
        if rev % 2 == 0:
            s.appendleft(t[2])
        else:
            s.append(t[2])
    else:
        if rev % 2 == 0:
            s.append(t[2])
        else:
            s.appendleft(t[2])
if rev % 2 != 0:
    s.reverse()

print(''.join(s))
### BUGGY CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul *= 10

print(dp[len(S)][5])


### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13

print(dp[len(S)][5])
### BUGGY CODE ###

n,m = map(int, input().split() )
c = []


for i in range(1,m+1) :

    if m//i in c :
      break

    else :
      if m%i==0 :
         c.append(i)
         c.append(m//i)

c.sort()
c.reverse()

for j in range(len(c)) :

   if c[j] <= m//n :
      print(c[j])
      break

### FIXED CODE ###

n,m = map(int, input().split() )
c = []


for i in range(1,int(m**0.5)+1) :

   if m%i==0 :
      c.append(i)
      c.append(m//i)

c.sort()
c.reverse()

for j in range(len(c)) :

   if c[j] <= m//n :
      print(c[j])
      break
### BUGGY CODE ###

# EduDPB - Frog 2
n, k = list(map(int, input().rstrip().split()))
lst = list(map(int, input().rstrip().split()))
ans = [0] + [float("inf")] * (n - 1)
for i in range(n):
    for j in range(1, k + 1):
        if i + j >= n:
            break
        ans[i + j] = min(ans[i + j], ans[i] + abs(lst[i] - lst[i + j]))
print(ans[-1])

### FIXED CODE ###

# EduDPB - Frog 2
import sys
input = sys.stdin.readline

n, k = list(map(int, input().rstrip().split()))
lst = list(map(int, input().rstrip().split()))
ans = [0] + [float("inf")] * (n - 1)
for i in range(n):
    for j in range(1, k + 1):
        if i + j >= n:
            break
        ans[i + j] = min(ans[i + j], ans[i] + abs(lst[i] - lst[i + j]))
print(ans[-1])
### BUGGY CODE ###

#a,b=map(int,input().split())
import numpy as np
 
s=input()
n=len(s)
wayA=np.array([0,0,0,0],dtype=np.int32)
wayB=np.array([0,0,0,0],dtype=np.int32)
wayC=np.array([0,0,0,0],dtype=np.int32)
hatena=0
MOD=1000000007
for c in s:
	if c=="A":
		wayA[0]=wayA[0]+1
	if c=="B":
		wayB+=wayA;
	if c=='C':
		wayC=wayC+wayB
	if c=='?':
		wayC[1]=wayC[1]+wayB[0]
		wayC[2]=wayC[2]+wayB[1]
		wayC[3]=wayC[3]+wayB[2]
		wayB[1]=wayB[1]+wayA[0]
		wayB[2]=wayB[2]+wayA[1]
		wayA[1]=wayA[1]+1
		hatena=hatena+1
	for z in range(0,4):
		wayA[z]=wayA[z]%MOD
		wayB[z]=wayB[z]%MOD
		wayC[z]=wayC[z]%MOD
ans=0
for i in range(0,4):
	p3=1
	if wayC[i]<=0:
		continue
	for k in range(0,hatena-i):
		p3=p3*3
		p3=p3%MOD
	ans=ans+p3*wayC[i]
	ans=ans%MOD
print(ans)

### FIXED CODE ###

#a,b=map(int,input().split())
import numpy as np

s=input()
n=len(s)
wayA=np.array([0,0,0,0],dtype=np.int64)
wayB=np.array([0,0,0,0],dtype=np.int64)
wayC=np.array([0,0,0,0],dtype=np.int64)
hatena=0
MOD=1000000007
for c in s:
	if c=="A":
		wayA[0]=wayA[0]+1
	if c=="B":
		wayB+=wayA;
	if c=='C':
		wayC=wayC+wayB
	if c=='?':
		wayC[1]=wayC[1]+wayB[0]
		wayC[2]=wayC[2]+wayB[1]
		wayC[3]=wayC[3]+wayB[2]
		wayB[1]=wayB[1]+wayA[0]
		wayB[2]=wayB[2]+wayA[1]
		wayA[1]=wayA[1]+1
		hatena=hatena+1
	for z in range(0,4):
		wayA[z]=wayA[z]%MOD
		wayB[z]=wayB[z]%MOD
		wayC[z]=wayC[z]%MOD
ans=0
for i in range(0,4):
	p3=1
	if wayC[i]<=0:
		continue
	for k in range(0,hatena-i):
		p3=p3*3
		p3=p3%MOD
	ans=ans+p3*wayC[i]
	ans=ans%MOD
print(int(ans))
### BUGGY CODE ###

from collections import deque
def hate(x,y):
    cur_hate = 0
    cur_q = deque()
    next_q = deque()
    cur_q.append((x,y))
    already = set()
    while True:
        while cur_q:
            x,y = cur_q.popleft()
            for i in range(4):
                next_x = x+dx[i]
                next_y = y+dy[i]
                if not (next_x,next_y) in already:
                    if grid[next_y][next_x] == "o":
                        if cur_hate == 0:
                            for x,y in already:
                                grid[y][x] = "o"
                        return cur_hate
                    if grid[next_y][next_x] == "#":
                        next_q.append((next_x,next_y))
                    else:
                        cur_q.append((next_x,next_y))
                    already.add((x,y))
        cur_hate += 1
        cur_q = next_q
        next_q = deque()
n = int(input())
grid = []
grid.append(["o"]*(n+2))
for i in range(n):
    grid.append(["o"]+["#"]*n+["o"])
grid.append(["o"]*(n+2))
dx = [0,1,0,-1]
dy = [1,0,-1,0]
ans = 0
p = list(map(int,input().split()))
for i in range(n**2):
    pos = p[i]
    x = (pos-1)%n+1
    y = (pos-1)//n+1
    h = hate(x,y)
    ans += h
    if h == 0:
        grid[y][x] = "o"
    else:
        grid[y][x] = "."
print(ans)


### FIXED CODE ###

import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i4,i4[:])',cache=True)
def main(n,p):
    ans = 0
    w = n+2
    grid = np.ones((w,w),np.int32)
    dis = np.zeros((w,w),np.int32)
    for i in range(1,n+1):
        for j in range(1,n+1):
            dis[i][j] = min(i,n-i+1,j,n-j+1)-1
    grid = grid.ravel()
    dis = dis.ravel()
    stack = np.empty_like(grid)
    for pos in p:
        pos -= 1
        x = pos % n + 1
        y = pos // n + 1
        v = y*w+x
        ans += dis[v]
        grid[v] = 0
        k = min(dis[v-1],dis[v+1],dis[v+w],dis[v-w])
        cur = 0
        stack[0] = v
        while cur >= 0:
            v = stack[cur]
            cur -= 1
            for dx in (-1,1,w,-w):
                next_v = v + dx
                k = dis[v]+grid[v]
                if dis[next_v] > k:
                    dis[next_v] = k
                    cur += 1
                    stack[cur] = next_v
    return ans

n = int(readline())
p = np.array(readline().split(),np.int32)
print(main(n,p))
### BUGGY CODE ###

def solve():
    MOD = 998244353

    N, S = map(int, input().split())
    As = list(map(int, input().split()))

    dp0, dp1, dp2 = [0]*(S+1), [0]*(S+1), [0]*(S+1)
    dp0[0] = 1
    for A in As:
        for sm in reversed(range(S+1)):
            dp2[sm] += dp1[sm] + dp0[sm]
            if sm-A >= 0:
                dp2[sm] += dp1[sm-A] + dp0[sm-A]
            dp2[sm] %= MOD
            dp1[sm] += dp0[sm]
            if sm-A >= 0:
                dp1[sm] += dp1[sm-A] + dp0[sm-A]
            dp1[sm] %= MOD

    print(dp2[S])


solve()


### FIXED CODE ###

def solve():
    MOD = 998244353

    N, S = map(int, input().split())
    As = list(map(int, input().split()))

    dp = [[0]*(3) for _ in range(S+1)]
    dp[0][0] = 1
    for A in As:
        for sm in reversed(range(S+1)):
            dp[sm][2] += dp[sm][1] + dp[sm][0]
            if sm-A >= 0:
                dp[sm][2] += dp[sm-A][1] + dp[sm-A][0]
            dp[sm][2] %= MOD
            dp[sm][1] += dp[sm][0]
            if sm-A >= 0:
                dp[sm][1] += dp[sm-A][1] + dp[sm-A][0]
            dp[sm][1] %= MOD

    print(dp[S][2])


solve()
### BUGGY CODE ###

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

K = int(input())
ans = 0

for a in range(1, K+1):
  for b in range(1, K+1):
    for c in range(1, K+1):
      ans += gcd(a, b, c)
print(ans)

  
  

### FIXED CODE ###

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

K = int(input())
ans = 0

for a in range(1, K+1):
  for b in range(1, K+1):
    for c in range(1, K+1):
      ans += gcd(a, b, c)
print(ans)
### BUGGY CODE ###

from collections import defaultdict
S = input()

d = defaultdict(int)
d[0] = 1

for i in range(1, len(S)+1):
    t = int(S[-i:])
    d[t % 2019] += 1

ans = 0
for v in d.values():
    ans += v*(v-1)//2
print(ans)


### FIXED CODE ###

import collections
S = input()[::-1]

d = 1
M = []
for s in S:
    M.append(int(s)*d % 2019)
    d *= 10
    d %= 2019

S = [0]
for m in M:
    S.append((S[-1]+m) % 2019)

C = collections.Counter(S)

ans = 0
for v in C.values():
    ans += v*(v-1)//2
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
ans = [0 for _ in range(n)]
for i in range(m):
    l,r = map(int,input().split())
    l-=1;r-=1
    for j in range(l,r+1):
        ans[j] += 1
print(ans.count(m))

### FIXED CODE ###

n,m = map(int,input().split())
mn = 0
mx = 10**5
for i in range(m):
    l,r = map(int,input().split())
    if mn < l:
        mn = l
    if mx > r:
        mx = r
if mn <= mx:
    print(mx-mn+1)
else:
    print(0)