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

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

def ncr(n, r, p):
    num = den = 1
    for i in range(r):
        num = (num * (n - i)) % p
        den = (den * (i + 1)) % p
    return (num * pow(den, p - 2, p)) % p
p=10**9+7

ans = 0
comb = 0
for i in a:
    if mx == i:
        continue
    tmp = ncr(mx, i, p)
    if comb <= tmp:
        ans = i 
        comb = tmp
print(mx, ans, sep=" ")

### FIXED CODE ###

import bisect
n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
m = max(a)
half_idx = bisect.bisect_left(a, m//2)

def ncr(n, r, p):
    num = den = 1
    for i in range(r):
        num = (num * (n - i)) % p
        den = (den * (i + 1)) % p
    return (num * pow(den, p - 2, p)) % p
p=10**9+7 

if n == 2:
    print(a[1], a[0])
    exit()

if 1 <= half_idx < n-1:
    if min(a[half_idx-1], m-(a[half_idx-1])) >= max(min(a[half_idx], m-(a[half_idx])), min(a[half_idx+1], m-(a[half_idx+1]))):
        print(m, a[half_idx-1])
    elif min(a[half_idx], m-(a[half_idx])) >= max(min(a[half_idx-1], m-(a[half_idx-1])), min(a[half_idx+1], m-(a[half_idx+1]))):
        print(m, a[half_idx])
    elif min(a[half_idx+1], m-(a[half_idx+1])) >= max(min(a[half_idx], m-(a[half_idx])), min(a[half_idx-1], m-(a[half_idx-1]))):
        print(m, a[half_idx+1])
elif half_idx == 0:
    if min(a[half_idx], m-(a[half_idx])) >= min(a[half_idx+1], m-(a[half_idx+1])):
        print(m, a[half_idx])
    elif min(a[half_idx+1], m-(a[half_idx+1])) >= min(a[half_idx], m-(a[half_idx])):
        print(m, a[half_idx+1])
elif half_idx == n-1:
    if min(a[half_idx], m-(a[half_idx])) >= min(a[half_idx-1], m-(a[half_idx-1])):
        print(m, a[half_idx])
    elif min(a[half_idx-1], m-(a[half_idx-1])) >= min(a[half_idx], m-(a[half_idx])):
        print(m, a[half_idx-1])
### BUGGY CODE ###

# AOJ 0259: All Numbers Lead to 6174
# Python3 2018.6.25 bal4u

while True:
	n = input()
	if n == "0000": break
	if len(set(n)) == 1:
		print("NA")
		continue
	ans = 0
	while n != "6174":
		ans += 1
		l = sorted(n)
		s = l[::-1]
		n = str(int(''.join(s))-int(''.join(l)))
	print(ans)



### FIXED CODE ###

# AOJ 0259: All Numbers Lead to 6174
# Python3 2018.6.25 bal4u

while True:
	n = input()
	if int(n) == 0: break
	if len(set(n)) == 1:
		print("NA")
		continue
	ans = 0
	while n != "6174":
		ans += 1
		l = ''.join(sorted(n))
		s = l[::-1]
		n = str(int(s)-int(l)).zfill(4)
	print(ans)
### BUGGY CODE ###

def LI(): return [int(x) for x in input().split(" ")]
def LS(): return [str(x) for x in input().split(" ")]
def ItoS(L): return [str(x) for x in L]
def StoI(L): return [int(c) for c in L]


def solve():
    n, t = LI()
    T = LI()
    sentou = [0 for _ in range(T[-1] + t + 1)]

    for ele_T in T:
        sentou[ele_T] += 1
        sentou[ele_T + t] -= 1

    for i in range(1, len(sentou)):
        sentou[i] += sentou[i - 1]

    print(n * t - (sum(sentou) - (sentou.count(1) + len(sentou) - sentou.count(1) - sentou.count(0))))

solve()

### FIXED CODE ###

def LI(): return [int(x) for x in input().split(" ")]
def LS(): return [str(x) for x in input().split(" ")]
def ItoS(L): return [str(x) for x in L]
def StoI(L): return [int(c) for c in L]


def solve():
    n, t = LI()
    T = LI()

    ans = 0
    for i in range(len(T) - 1):
        ans += min(t, T[i + 1] - T[i])

    print(ans + t)


solve()
### BUGGY CODE ###

import sys
from collections import deque
from pprint import pprint

def solve(n, m, a, ops):
    a = sorted(a)
    ops = sorted(ops, reverse=True)
    # pprint(a)
    # pprint(ops)
    start = 0
    for ope, count in ops:
        for i, a_i in enumerate(a[start:]):
            if a_i < ope and count > 0:
                # print a_i, '=>', ope
                count -= 1
                a[start+i] = ope
            else:
                break
        start += i

    print sum(a)

if __name__ == '__main__':

    ops = []
    n, m = map(int, sys.stdin.readline().strip().split(" "))
    a = map(int, sys.stdin.readline().strip().split(" "))
    for _ in range(m):
        b, c = map(int, sys.stdin.readline().strip().split(" "))
        ops.append((c, b))

    solve(n, m, a, ops)

### FIXED CODE ###

import sys
from pprint import pprint

def solve(n, m, a, ops):
    a.sort()
    ops.sort(reverse=True)
    # pprint(a)
    # pprint(ops)
    start = 0
    for ope, count in ops:
        i = 0
        for a_i in xrange(start, start+count):
            if a_i >= n:
                break
            if a[a_i] < ope and count > 0:
                count -= 1
                # print a_i, '=>', ope, ' count:', count
                a[a_i] = ope
                i += 1
            else:
                break
        start += i

    print sum(a)

if __name__ == '__main__':

    ops = []
    n, m = map(int, sys.stdin.readline().strip().split(" "))
    a = map(int, sys.stdin.readline().strip().split(" "))
    for _ in range(m):
        b, c = map(int, sys.stdin.readline().strip().split(" "))
        ops.append((c, b))

    solve(n, m, a, ops)
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(m):
  b,c=map(int,input().split())
  a.extend([c]*b)
a.sort(reverse=True)
print(sum(a[:n]))


### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
d=[]
ans=0
for i in range(n):
  d.append([a[i],1])
for i in range(m):
  b,c=map(int,input().split())
  d.append([c,b])
d.sort(reverse=True)
for i in range(n+m):
  if n==0:
    break
  ans+=d[i][0]*min(n,d[i][1])
  n-=min(n,d[i][1])
print(ans)
### BUGGY CODE ###

import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

# extended gcd and modinv
# x = y*(x/y) + x%y
#   ->  g = ax+by = a(y*(x/y) + x%y) + by
#         = (a*(x/y) + b)*y + a*(x%y)
#
# while  g=ax+by, b==0  ->  g=x, a=1

def exgcd(x,y):
    if y == 0:
        return (x,1,0)
    else:
        g,b,a = exgcd(y, x%y)
        return (g, a, b-(x//y)*a)

# return y s.t. x*y mod p == 1
def modinv(x,p):
    g,a,b = exgcd(x,p)  # ax+bp = g, g=1 if mutually prime
    return a%p

# combinatorial(n,k) mod r
def comb(p,q,r):
    if q==0 or q==p:
        return 1
    if q > p-q:
        q = p-q
    num = p
    den = q
    for i in range(1,q):
        num = (num * (p-i))%r
        den = (den * (q-i))%r
    xden = modinv(den,r)
    return (num*xden)%r

def rpow(x,e,r):
    p = 1
    while e>0:
        if e%2 == 1:
            p = (p*x)%r
        x *= x
        e //= 2
    return p

R = 1000003
facts = [1] * R
for i in range(2,R):
    facts[i] = (facts[i-1]*i)%R
ddprint(facts[:33])

qq = inn()
for q in range(qq):
    x,d,n = inm()
    if d==0:
        print(rpow(x,n,R))
        continue
    xd = modinv(d,R)
    y = (x * xd) % R
    ddprint("x {} d {} n {} xd {} y {}".format(x,d,n,xd,y))
    if y+n-1 >= R:
        print(0)
    else:
        z = rpow(d,n,R) * facts[y+n-1] * modinv(facts[y-1],R)
        print(z%R)


### FIXED CODE ###

printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

# extended gcd and modinv
# x = y*(x/y) + x%y
#   ->  g = ax+by = a(y*(x/y) + x%y) + by
#         = (a*(x/y) + b)*y + a*(x%y)
#
# while  g=ax+by, b==0  ->  g=x, a=1

def exgcd(x,y):
    if y == 0:
        return (x,1,0)
    else:
        g,b,a = exgcd(y, x%y)
        return (g, a, b-(x//y)*a)

# return y s.t. x*y mod p == 1
def modinv(x,p):
    return pow(x,p-2,p)


def modinv2(x,p):
    g,a,b = exgcd(x,p)  # ax+bp = g, g=1 if mutually prime
    return a%p


R = 1000003
facts = [1] * R
for i in range(2,R):
    facts[i] = (facts[i-1]*i)%R

qq = inn()
for q in range(qq):
    x,d,n = inm()
    if d==0:
        print(pow(x,n,R))
        continue
    xd = modinv(d,R)
    y = (x * xd) % R
    if y+n-1 >= R:
        print(0)
    else:
        z = pow(d,n,R) * facts[y+n-1] * modinv(facts[y-1],R)
        print(z%R)
### BUGGY CODE ###

# youtubeバージョン
import sys
from heapq import *
from bisect import *

input = sys.stdin.readline

def f(n, q):
    xst = []
    for i in range(n):
        s, t, x = map(int, input().split())
        xst.append([x, s - x, t - x])
    xst.sort()

    ds = []
    dis=[]
    ans = [-1] * q
    for i in range(q):
        d = int(input())
        heappush(ds,d)
        heappush(dis, [d, i])


    for x, s, t in xst:
        i=bisect_left(ds,s)
        nd=len(ds)
        while i<nd:
            if ds[i]<t:
                ai=dis[i][1]
                ans[ai]=x
                del ds[i]
                del dis[i]
                nd-=1
            else:
                break

    print(*ans,sep="\n")


n, q = map(int, input().split())
f(n, q)


### FIXED CODE ###

import sys
from bisect import *

input = sys.stdin.readline

def f(n, q):
    xst = []
    for i in range(n):
        s, t, x = map(int, input().split())
        xst.append([x, s - x, t - x])
    xst.sort()

    ds = []
    for i in range(q):
        d = int(input())
        ds.append(d)

    ans = [-1] * q
    jump = [-1] * q

    for x, s, t in xst:
        i = bisect_left(ds, s)
        fi = bisect_left(ds, t)
        while i < fi:
            if jump[i] != -1:
                i = jump[i]
            else:
                ans[i] = x
                jump[i] = fi
                i += 1

    print(*ans, sep="\n")

n, q = map(int, input().split())
f(n, q)
### BUGGY CODE ###

n = int(input())
c = input()
cnt = 0

while c.count('WR')>=1:
  w = c.index('W')
  r = c[::-1].index('RW')+1
  r *= -1
  cl = list(c)
  cl[w] = 'R'
  cl[r] = 'W'
  c = ''.join(cl)
  cnt += 1

wr = min(c.count('W'),c.count('R'))
cnt = min(cnt,wr)
print(cnt)

### FIXED CODE ###

n = int(input())
c = input()
print(c[:c.count('R')].count('W'))
### BUGGY CODE ###

def read_input():
    n = int(input())

    ratios = []
    for i in range(n):
        t, a = map(int, input().split())
        ratios.append((t, a))

    return n, ratios


def get_votes(ex_votes, ratio):
    def check_votes(a, b):
        return a[0] <= b[0] and a[1] <= b[1]

    base = 1
    while True:
        test_votes = (ratio[0]*base, ratio[1]*base)
        if check_votes(ex_votes, test_votes):
            return test_votes
        else:
            base += 1

def submit():
    n, ratios = read_input()

    votes = (1, 1)
    for ratio in ratios:
        votes = get_votes(votes, ratio)

    print(sum(votes))


if __name__ == '__main__':
    submit()

### FIXED CODE ###

import math


def read_input():
    n = int(input())

    ratios = []
    for i in range(n):
        t, a = map(int, input().split())
        ratios.append((t, a))

    return n, ratios


def get_votes(ex_votes, ratio):
    def check_votes(a, b):
        return a[0] <= b[0] and a[1] <= b[1]

    def div_ceil(a, b):
        if a % b == 0:
            return a //b
        else:
            return a // b + 1

    base = div_ceil(sum(ex_votes), (ratio[0] + ratio[1]))
    base = int(base)
    while True:
        test_votes = (ratio[0] * base, ratio[1] * base)
        if check_votes(ex_votes, test_votes):
            return test_votes
        else:
            diff_votes = (test_votes[0] - ex_votes[0], test_votes[1] - ex_votes[1])
            if diff_votes[0]/ratio[0] < diff_votes[1]/ratio[1]:
                base += div_ceil(-diff_votes[0], ratio[0])
            else:
                base += div_ceil(-diff_votes[1], ratio[1])
            base = int(base)


def submit():
    n, ratios = read_input()

    votes = ratios[0]
    for ratio in ratios[1:]:
        votes = get_votes(votes, ratio)

    print(sum(votes))


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

N=raw_input()
LN=raw_input().split()

n = int(N)
ln = [int(i) for i in LN]

c = [[x, y, z] for x in range(n) for y in range(n) for z in range(n) if x > y and y > z]

r = []
for i in c:
    x, y, z = i
    a = ln[x]
    b = ln[y]
    c = ln[z]
    if not a < b + c:
        continue
    if not b < c + a:
        continue
    if not c < a + b:
        continue
    r.append(i)

print len(r)

### FIXED CODE ###

import bisect

N=int(raw_input())
LN=map(int, raw_input().split())

LN.sort()

r = 0
for i in xrange(N-1, 1, -1):
    a = LN[i]
    for j in xrange(i-1, 0, -1):
        b = LN[j]
        if a > 2*b:
            break
        idx = bisect.bisect_left(LN, a-b+1)
        if idx < j:
            r += j - idx

print r
### BUGGY CODE ###

#!/usr/bin/python

import sys

p=[0]*10000;mp=[];inf=65536;v=[0]*1000;t=[0]*1000
 
 
ans=100000

 
n,m,r=map(int,sys.stdin.readline().split(" "))

s=sys.stdin.readline().replace("\n","")

p=map(int,s.split(" "))


def dsss(x,now):
	global ans
	if x==r+1:
		ans=min(ans,now)
		return 
	else :
		for i in range(r):
			if v[p[i]]==0 :
				v[p[i]]=1
				t[x]=p[i]
				if x==1:
					dsss(x+1,now)
				else :
					dsss(x+1,now+mp[p[i]-1][t[x-1]-1])
				v[p[i]]=0
	return 
 
 
for i in range(n+5):
	mp.append(range(n+5))
 
 
for i in range(n+5):
    for j in range(n+5):
        if(i!=j):
            mp[i][j]=inf
 
for i in range(m):
	a,b,c=map(lambda x: int(x),sys.stdin.readline().split(" ",3))
	a-=1;b-=1;
	mp[a][b]=min(mp[a][b],c)
	mp[b][a]=min(mp[b][a],c)
 
for i in range(n):
	for j in range(n):
		for k in range(n):
			mp[j][k]=min(mp[j][k],mp[j][i]+mp[i][k])


dsss(1,0)
 
print ans


### FIXED CODE ###

#!/usr/bin/python

import sys

p=[0]*10000;mp=[];inf=65530060;v=[0]*1000;t=[0]*1000
 
 
ans=100000000

 
n,m,r=map(int,sys.stdin.readline().split(" "))



s=sys.stdin.readline().replace("\n","")

p=map(int,s.split(" "))


def dsss(x,now):
	global ans,v,p,t,mp
	if x==r+1:
		ans=min(ans,now)
		return 
	else :
		for i in range(r):
			if v[p[i]]==0 :
				v[p[i]]=1
				t[x]=p[i]
				if x==1:
					dsss(x+1,now)
				else :
					dsss(x+1,now+mp[p[i]-1][t[x-1]-1])
				v[p[i]]=0
	return 
 
 
for i in range(n+5):
	mp.append(range(n+5))
 
 
for i in range(n+5):
    for j in range(n+5):
            mp[i][j]=inf


for i in range(m):
	a,b,c=map(lambda x: int(x),sys.stdin.readline().split(" ",3))
	a-=1;b-=1;
	mp[a][b]=min(mp[a][b],c)
	mp[b][a]=min(mp[b][a],c)


for i in xrange(n):
	for j in xrange(n):
		for k in xrange(n):
			if mp[j][i]+mp[i][k]<mp[j][k]:
			    mp[j][k]=mp[j][i]+mp[i][k]

dsss(1,0)
 
print ans
### BUGGY CODE ###

import sys, itertools
s = sys.stdin.readline().strip()
l = n1 = len(s)
while True:
    n = l
    skip = False
    _s = ""
    for i, j in itertools.zip_longest(s[:], s[1:]):
        if skip:
            skip = False
            continue
        if i == j or j == None:
            _s += i
        else:
            skip = True
    s = _s
    l = len(s)
    if l == 0 or n == l:
        break
print(n1 - len(s))

### FIXED CODE ###

s = input()
print(min(s.count('0'), s.count('1'))*2)
### BUGGY CODE ###

n,m = (int(i) for i in input().split()) 
a = [int(i) for i in input().split()] 
e = [[int(i) for i in input().split()] for i in range(m)]

for i, l in enumerate(e):
  for j in range(l[0]):
    a.append(l[1])
a.sort(reverse=True)
retval = 0
for i in range(n):
  retval += a[i]
print(retval)

### FIXED CODE ###

n,m = (int(i) for i in input().split()) 
a = [int(i) for i in input().split()] 
e = [[int(i) for i in input().split()] for i in range(m)]

a.sort()
e.sort(key=lambda x: x[1], reverse=True)
c = 0
arr = []
for i, el in enumerate(e):
  for j in range(el[0]):
    #print(c,n)
    if (c < n):
        arr.append(el[1])
        c += 1
    else:
        break
  if (c >= n):
    break
retval = 0
#print(arr)
for i in range(c):
  if (a[i] < arr[i]):
    a[i] = arr[i]
    #print(a[i],arr[i])
  else:
    break
  #print(a)
print(sum(a))
### BUGGY CODE ###

import math
from functools import reduce
def gcd(*number):
    return reduce(math.gcd, number)
n = int(input())
sum = 0
for i in range(1, n+1):
    for j in range(1, n+1):
        for k in range(1, n+1):
            sum += gcd(i, j, k)
print(sum)

### FIXED CODE ###

from math import gcd
n = int(input())
sum = 0
for i in range(1, n+1):
    for j in range(1, n+1):
        for k in range(1, n+1):
            sum += gcd(gcd(i, j), k)
print(sum)
### BUGGY CODE ###

import sys

stdin = sys.stdin

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

def main():
    n = ni()
    l = sorted(na(), reverse=True)

    cnt = 0
    for i in range(n):
        for j in range(i + 1, n):
            # k = n - i - j
            # a = l[i]
            # b = l[j]
            # c = l[k]
            # if a < b + c and b < a + c and c < a + b:
            #     cnt += C(n - i, 2)
            #     print(a, b, c)
            for k in range(j + 1, n):
                a = l[i]
                b = l[j]
                c = l[k]
                if a < b + c and b < a + c and c < a + b:
                    # print(a, b, c)
                    cnt += 1
                else:
                    break
    print(cnt)

main()

### FIXED CODE ###

import sys

stdin = sys.stdin

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

from bisect import bisect_left

def main():
    n = ni()
    l = sorted(na())
    
    ans = 0
    for i in range(n):
        for j in range(i+1, n):
            t = l[i] + l[j]
            ind = bisect_left(l, t)
            ans += max(0, ind - j - 1)
    print(ans)

main()
### BUGGY CODE ###

n,x,y=map(int,input().split())
ans=[0]*(n-1)
for i in range(1,n):
    for j in range(i+1,n+1):
        length=min(abs(i-j),abs(x-i)+1+abs(y-j),abs(y-i)+1+abs(x-j))
        ans[length-1]+=1
for i in range(n-1):
    print(ans[i])


### FIXED CODE ###

n,x,y=map(int,input().split())
ans=[0]*(n-1)
ans[0]=n-1
for i in range(1,n-1):
    for j in range(i+2,n+1):
        length=min(abs(i-j),abs(x-i)+1+abs(y-j),abs(y-i)+1+abs(x-j))
        ans[length-1]+=1
for i in range(n-1):
    print(ans[i])
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
ans=0
for i in range(n-k+1):
    tmp=sum(p[i:i+k])
    if tmp>ans:
        ans=tmp
print((ans+k)/2)

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))

tmp=sum(p[:k])
ans=tmp
for i in range(n-k):
    tmp=tmp-p[i]+p[i+k]
    if tmp>ans:
        ans=tmp
print((ans+k)/2)
### BUGGY CODE ###

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

D = collections.Counter(A)
for i in range(N):
  D[A[i]]-=1
  s=0
  for j in D:
    s+=D[j]*(D[j]-1)//2
  print(s)
  D[A[i]]+=1


### FIXED CODE ###

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

D = collections.Counter(A)
s=0
for i in D:
  s+=D[i]*(D[i]-1)//2
  
for i in range(N):
  print(s-(D[A[i]]-1))
### BUGGY CODE ###

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

n = 1
for i in range(q):
  query = list(map(str, input().split()))
  if query[0] == "1":
    n *= -1
  else:
    f = int(query[1])
    c = query[2]
    if f * n == 1 or f * n == -2:
      s = c + s
    else:
      s = s + c

if n == -1:
  s = s[::-1]
  
print(s)

### FIXED CODE ###

from collections import deque

S = list(input())
Q = int(input())

S = deque(S)
rev = 1
for _ in range(Q):
    query = input()
    if len(query) == 1:
        rev *= -1
    else:
        T, F, C = query.split()
        if rev == 1:
            if F == "1":
                S.appendleft(C)
            else:
                S.append(C)
        else:
            if F == "1":
                S.append(C)
            else:
                S.appendleft(C)

if rev == -1:
    S = reversed(S)

print("".join(S))
### BUGGY CODE ###

K = int(input())

a = 0
ans = -1

for i in range(K):
    a += 7 * 10**i
    if a % K == 0:
        ans = i+1
        break

print(ans)

### FIXED CODE ###

k = int(input())
if k==1 or k==7:
  print(1)
elif k%2==0:
  print(-1)
else:
  cnt = 1
  pre = 7
  while(True):
    surp = (pre*10+7)%k
    cnt += 1
    if surp==0:
      break
    if cnt>1000000:
      cnt = -1
      break
    pre = surp
  print(cnt)
### BUGGY CODE ###

import bisect

n, m = map(int, input().split())
*a, = map(int, input().split())

a = sorted(a)

for i in range(m):
    a[n-1] = a[n-1] // 2
    temp = a.pop()
    bisect.insort_left(a, temp)
print(sum(a))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
*a, = map(int, input().split())

ans = []
for i in range(n):
    heapq.heappush(ans, -a[i])

for i in range(m):
    temp = -heapq.heappop(ans)
    heapq.heappush(ans, -(temp//2))

print(-sum(ans))
### BUGGY CODE ###

import fractions
n, m = map(int, input().split())
l = []
r = []
for i in range(m):
    x, y = map(int, input().split())
    l.append(x)
    r.append(y)
ans = 0
for i in range(1,n+1):
    if max(l) <= i and i <= min(r):
        ans += 1
print(ans) 

### FIXED CODE ###

import fractions
n, m = map(int, input().split())
l = []
r = []
for i in range(m):
    x, y = map(int, input().split())
    l.append(x)
    r.append(y)
ans = 0
M = max(l)
m = min(r)
for i in range(1,n+1):
    if M <= i and i <= m:
        ans += 1
print(ans)
### BUGGY CODE ###

import sys

tree={}
np = -1

home=0
tree[home]=[None, None, None]

def search(p, x):
    while p != None:
        tmp = tree[p][0]
        if tmp == x: return True
        if x < tmp:
            p = tree[p][1]
        else:
            p = tree[p][2]
    return False

def node(x):
    global np
    np += 1
    tree[np] = [x, None, None]
    return np

def insert(p, x):
    if p == None or np == -1: return node(x)
    tmp = tree[p][0]
    if x== tmp: return p
    elif x<tmp:
        tree[p][1]=insert(tree[p][1],x)
    else:
        tree[p][2]=insert(tree[p][2],x)
    return p

def preorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return [tree[p][0]] + preorder(p1) + preorder(p2)

def inorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return inorder(p1) + [tree[p][0]] +inorder(p2)

n = int(input())
i = 0
while i<n:
    s = raw_input()
    if s[0]=='i':
        insert(0,int(s[7:]))
    elif s[0]=='p':
        print ' ' + ' '.join(map(str, inorder(home)))
        print ' ' + ' '.join(map(str, preorder(home)))
    i += 1

### FIXED CODE ###

import sys

tree={}
np = -1

home=0
tree[home]=[None, None, None]

def search(p, x):
    while p != None:
        tmp = tree[p]
        if tmp[0] == x: return True
        if x < tmp[0]:
            p = tmp[1]
        else:
            p = tmp[2]
    return False

def node(x):
    global np
    np += 1
    tree[np] = [x, None, None]
    return np

def insert(p, x):
    if p == None or np == -1: return node(x)
    tmp = tree[p]
    if x== tmp[0]: return p
    elif x<tmp[0]:
        tree[p][1]=insert(tmp[1],x)
    else:
        tree[p][2]=insert(tmp[2],x)
    return p

def preorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return [tree[p][0]] + preorder(p1) + preorder(p2)

def inorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return inorder(p1) + [tree[p][0]] +inorder(p2)

n = int(input())
i = 0
while i<n:
    s = raw_input()
    if s[0]=='i':
        insert(0,int(s[7:]))
    elif s[0]=='p':
        print ' ' + ' '.join(map(str, inorder(home)))
        print ' ' + ' '.join(map(str, preorder(home)))
    i += 1