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

from functools import lru_cache

def main(S):
    con = 10**9 + 7

    @lru_cache(maxsize=1024)
    def get_c(iii):
        return [mm13[iii][j] for j in l10]

    l10 = list(range(10))
    l13 = list(range(13))
    m13 = {i: {j: (i + j) % 13 for j in l13} for i in l13}
    mm13 = {i: {j: (i * j) % 13 for j in range(11)} for i in range(1000)}
    c = []
    iii = 1
    for i in range(len(S)):
        s = S[len(S) - i - 1]
        if s != "?":
            c.append([mm13[iii][int(s)]])
        else:
            c.append(get_c(iii))
        iii = mm13[iii][10]

    _tdp = {i: 0 for i in l13}
    it = iter(c)
    pdp = {i: 1 for i in next(it)}
    d = 1
    for v in it:
        tdp = _tdp.copy()
        for r in v:
            for _r, _v in pdp.items():
                tdp[m13[_r][r]] += _v
        if d == 0:
            for i in l13:
                tdp[i] = tdp[i] % con
        d = (d + 1) % 50
        pdp = tdp

    ans = pdp.get(5, 0)
    print(ans % con)

if __name__ == "__main__":
    S = input()
    main(S)

### FIXED CODE ###

S = input()
con = 10**9 + 7

T = [s if s != "?" else "0" for s in S]
T = int(''.join(T))
SS = T % 13

def get_mod(S):
    c = {}
    iii = 1
    for i in range(len(S)):
        if S[len(S) - i - 1] != "?":
            iii *= 10
            iii %= 13
            continue
        c[i] = {(j * iii) % 13: 1 for j in range(0, 10)}
        iii *= 10
        iii %= 13
    return c
c = get_mod(S)

def get_tdp(pdp):
    tdp = {i: 0 for i in range(13)}
    for r in v.keys():
        for _r, _v in pdp.items():
            tdp[(_r + r) % 13] += _v
    for i in range(13):
        tdp[i] %= con
    return tdp

pdp = {i: 0 for i in range(13)}
pdp[SS] += 1
for k, v in c.items():
    pdp = get_tdp(pdp)

ans = pdp[5]
print(ans)
### BUGGY CODE ###

N=int(input())
S=0
for i in range(N):
  S+=i
print(S)

### FIXED CODE ###

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

def Count(a,b,c,K):
    if (a+b)%K==0 and (a+c)%K==0 and (b+c)%K==0:
        return 1;
    else:
        return 0;

N,K=(int(i) for i in input().split())
count=0

for i in range(1,N+1):
    for j in range(1,N+1):
        for k in range(1,N+1):
            count=count+Count(i,j,k,K)
print(count)

### FIXED CODE ###

N,K=(int(i) for i in input().split())
countG=0
count=0
if K%2==0:
    for i in range(1,N+1):
        if i%K==0:
            count+=1
        elif i%K==K/2:
            countG+=1
else:
    for i in range(1,N+1):
        if i%K==0:
            count+=1
print(count*count*count+countG*countG*countG)
### BUGGY CODE ###

#ALDS_1_1_D Maximum Profit

N=int(input())
A=[]
for i in range(N):
    A.append(int(input())) 
MAX= A[1]-A[0]
for i in range(1,N):
    for j in range(i):
        MAX=max(MAX,A[i]-A[j])
print(MAX)


### FIXED CODE ###

#ALDS_1_1_D Maximum Profit

N=int(input())
A=[]
for i in range(N):
    A.append(int(input())) 
MIN= A[0]
MAX= A[1]-A[0]
for i in range(1,N):
    MAX=max(MAX,A[i]-MIN)
    MIN=min(MIN,A[i])
print(MAX)
### BUGGY CODE ###

n = int(input())
a = [0 for i in range(n)]
for i in range(n):
    a[i] = int(input())
now = a[0]
count = 0
while True:
    count += 1
    if now ==2:
        print(count)
        break
    else:
        now = a[now-1]


### FIXED CODE ###

import sys
a = [int(i) for i in sys.stdin]
now = a[1]
count = 0
while count!=a[0]:
    count += 1
    if now == 2:
        print(count)
        exit()
    now = a[now]
print(-1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


N, M = map(int, input().split())
A = []
for _ in range(M):
    a = tuple(map(int, input().split()))
    A.append(a)
dp = [-1]*(N+1)


def dfs(n):
    global dp
    B = list(filter(lambda x: x[0] == n, A))
    if len(B) == 0:
        return 0
    ma = 0
    for b in B:
        x = dp[b[1]]
        if x != -1:
            ma = max(ma, x + 1)
        else:
            ma = max(ma, dfs(b[1]) + 1)
    dp[n] = ma
    return ma


def main():
    global dp
    for i in range(N):
        dp[i] = dfs(i+1)
    print(max(dp))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
dp = [-1]*N


def dfs(n):
    global dp
    if dp[n] > 0:
        return dp[n]

    ma = 0
    for b in G[n]:
        ma = max(ma, dfs(b) + 1)
    dp[n] = ma
    return ma


def main():
    global dp
    for i in range(N):
        dp[i] = dfs(i)
    print(max(dp))


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

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

ans = 0
for i in range(N-K+1):
    a = sum(P[i:i+K])
    ans = a if a > ans else ans
print((ans+K)/2)


### FIXED CODE ###

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

ans = sum(P[0:K])
tmp = sum(P[0:K])

for i in range(1, N-K+1):
    tmp = tmp - P[i-1] + P[i+K-1]
    ans = max(tmp, ans)
print((ans + K)/2)
### BUGGY CODE ###

n = int(input())
ans=0

for i in range(1,n+1):
    for j in range(1,i+1):
        if str(i)[0]==str(j)[-1] and str(j)[0]==str(i)[-1]:
            if i==j:
                ans+=1
            else:
                ans+=2

print(ans)


### FIXED CODE ###

from collections import defaultdict

n=int(input())
counter=defaultdict(int)

for x in map(str,range(1,n+1)):
    head=x[0]
    tail=x[-1]
    counter[(head,tail)]+=1

ans=0
items=list(counter.items())
for (head, tail), cnt in items:
    ans+=cnt*counter[(tail, head)]

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

n=int(input())
ls = list(map(int,input().split()))
ans = 0
for i in range(n-1):
  for j in range(n-i):
    if i+1!=n and ls[i]<ls[i+1]:
      break
    else:
      i+=1
  ans = max(ans,j)
  if ans > n-1-i:
    break
print(ans)

### FIXED CODE ###

n=int(input())
ls = list(map(int,input().split()))
ls2 = [0]*(n+1)
for i in range(n-1):
  if ls[i]<ls[i+1]:
    ls2[i+1]=ls2[i]*0
  elif ls[i]>=ls[i+1]:
    ls2[i+1]=ls2[i]+1
print(max(ls2))
### BUGGY CODE ###

import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


H, W, M = MI()
h = [0] * H
w = [0] * W
item_list = [[0, 0] for _ in range(M)]

for i in range(M):
    item_h, item_w = MI()
    item_h -= 1
    item_w -= 1
    h[item_h] += 1
    w[item_w] += 1
    item_list[i][0] = item_h
    item_list[i][1] = item_w

ans = max(h) + max(w)
index_num_h = [n for n, v in enumerate(h) if v == max(h)]
index_num_w = [n for n, v in enumerate(w) if v == max(w)]

cnt = -1
for h_i in index_num_h:
    for w_i in index_num_w:
        d = [h_i, w_i]
        if d not in item_list:
            cnt = 0
            break

if cnt == -1:
    ans -= 1

print(ans)



### FIXED CODE ###

import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


H, W, M = MI()
h = [0] * H
w = [0] * W
item_list = [[0, 0] for _ in range(M)]

for i in range(M):
    item_h, item_w = MI()
    item_h -= 1
    item_w -= 1
    h[item_h] += 1
    w[item_w] += 1
    item_list[i][0] = item_h
    item_list[i][1] = item_w

h_max = max(h)
w_max = max(w)
h_cnt = h.count(h_max)
w_cnt = w.count(w_max)
ans = h_max + w_max

cnt = 0
for item in item_list:
    if h[item[0]] == h_max and w[item[1]] == w_max:
        cnt += 1

x = h_cnt * w_cnt
if cnt == x:
    ans -= 1

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

from collections import deque

N, K = map(int, input().split())
p = list(map(float, input().split()))

MV = 0
add = 0
m = 0 #何番目のサイコロを最後に含むか
ev = 0
lst = deque()

for i in range(K, N+1):
    for j in range(i-K, i):
        add += p[j]
        m = j
    if MV < add:
        MV = add
        for k in range(m-K+1, m+1):
            ev += ((p[k]*(p[k]+1))/2)/p[k]
        lst.append(ev)

    add = 0
    ev = 0

print(lst.pop())

### FIXED CODE ###

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

E = []

for i in range(N):
    E.append((P[i]+1)/2)

tnt = sum(E[:K])
ans = tnt

for i in range(N-K):
    tnt = tnt + E[K+i] - E[i]
    ans = max(ans, tnt)

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

import numpy as np
n,m = map(int,input().split())
ab = [[int(i) for i in input().split()]for j in range(m)][1:]

ans = [0]*(m-1)+[int(n*(n-1)/2)]
l = np.array([i for i in range(1,n+1)])
s = {i:1 for i in range(1,n+1)}
for k,i in enumerate(ab[::-1]):
  
  if l[i[0]-1] == l[i[1]-1]:
    ans[m-2-k]=ans[m-1-k]
  else:
    l_a,l_b,s_a,s_b = l[i[0]-1],l[i[1]-1],s[l[i[0]-1]],s[l[i[1]-1]]
    
    if l_a <= l_b:
      c = s_a*s_b
      s[l_b]+=s_a
      s[l_a]=0
      l[l==l_a]=l_b
      ans[m-2-k]=ans[m-1-k]-c
    else:
      c = s_a*s_b
      s[l_a]+=s_b
      s[l_b]=0
      l[l==l_b]=l_a
      ans[m-2-k]=ans[m-1-k]-c
  if ans[-1]==0:
    break
for i in ans:
  print(i)

### FIXED CODE ###

n,m = map(int,input().split())
ab = [[int(i) for i in input().split()]for j in range(m)][1:]
ans = [0]*(m-1)+[int(n*(n-1)/2)]
l = [i for i in range(1,n+1)]
s = {i:1 for i in range(1,n+1)}
 
def serch_l(num):
  if l[num]==num+1:
    return l[num]
  else:
    leader = serch_l(l[num]-1)
    l[num]=leader
    return leader
    
for k,i in enumerate(ab[::-1]):
  k = m-1-k
  l_a,l_b = serch_l(i[0]-1),serch_l(i[1]-1)
  if l_a==l_b:
    ans[k-1]=ans[k]
  else:
    
    s_a,s_b = s[l_a],s[l_b]
    
    if s_a > s_b:
      (s_a,s_b) = (s_b,s_a)
      (l_a,l_b) = (l_b,l_a)
    c = s_a*s_b
    s[l_b]+=s_a
    s[l_a]=0
    l[l_a-1]=l_b
    ans[k-1]=ans[k]-c
for i in ans:
  print(i)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
n = N//2
for i in range(N):
    array = A[0:i]+A[i+1:]
    array.sort()
    print(array[n-1])

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
A_copy = A.copy()
n = N//2
A.sort()
avg = (A[n]+A[n-1])/2
for i in A_copy:
    if i < avg:
        print(A[n])
    else:
        print(A[n-1])
### BUGGY CODE ###

import re

def main():
    s = input()

    hoji = len(s)

    count = len(s) // 2
    while count > 0:
        try:
            s = re.sub('01|10',"",s)
        except:
            break
        count -= 1


    print(hoji - len(s))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    s = input()

    zero = s.count('0')
    one = len(s) - zero

    print(min(zero, one) * 2)

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

from itertools import permutations as 敬語使うべきじゃん
N, C = map(int, input().split())
D = [[0] * (C + 1)] + [[0] + list(map(int, input().split())) for _ in range(C)]
c = [[0] * (N + 1)] + [[0] + list(map(int, input().split())) for _ in range(N)]
#print(D, c)

group = [[] for _ in range(3)]
for i in range(1, N + 1):
  for j in range(1, N + 1):
    m = (i + j) % 3
    group[m].append(c[i][j])
#print(group)

#色変えるだで
#色変えたときにかかるコストを先に計算しますよーしますしますし
costs = [[0] * (C + 1) for _ in range(3)]
for i in range(3):
  for color in range(1, C + 1):
    temp = 0
    for j in range(len(group[i])):
      temp += D[group[i][j]][color]
    costs[i][color] = temp
#print(costs)
res = 10 ** 10
for per in list(敬語使うべきじゃん(list(range(1, C + 1)), 3)):
  #print(per)
  #色はグループごとにちがう
  i, j, k = per[0], per[1], per[2]
  res = min(res, costs[0][i] + costs[1][j] + costs[2][k])
print(res)
  


### FIXED CODE ###

from itertools import permutations as 敬語使うべきじゃん
N, C = map(int, input().split())
D = [[0] * (C + 1)] + [[0] + list(map(int, input().split())) for _ in range(C)]
c = [[0] * (N + 1)] + [[0] + list(map(int, input().split())) for _ in range(N)]
#print(D, c)

group = [[] for _ in range(3)]
for i in range(1, N + 1):
  for j in range(1, N + 1):
    m = (i + j) % 3
    group[m].append(c[i][j])
#print(group)

#色変えるだで
#色変えたときにかかるコストを先に計算しますよーしますしますし
costs = [[0] * (C + 1) for _ in range(3)]
for i in range(3):
  for color in range(1, C + 1):
    temp = 0
    for j in range(len(group[i])):
      temp += D[group[i][j]][color]
    costs[i][color] = temp
#print(costs)
res = 10 ** 10
for per in list(敬語使うべきじゃん(list(range(1, C + 1)), 3)):
  #print(per)
  #色はグループごとにちがう
  i, j, k = per[0], per[1], per[2]
  res = min(res, costs[0][i] + costs[1][j] + costs[2][k])
print(res)
### BUGGY CODE ###

from collections import defaultdict
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    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 tento(xs):
    bit = Bit(max(xs)+1)
    ans = 0
    for i, p in enumerate(xs):
        ans += i-bit.sum(p)
        bit.add(p, 1)
        #print(p, ans)
    #print(xs, ans)
    return ans

N = int(input())
xs = list(map(int, input().split()))
ys = list(map(int, input().split()))
r = 10**18
for i in range(2**N):
    zs = [0]*N
    for j in range(N):
        if i%2:
            # j と偶数離れたらいい
            zs[j] = (xs[j],(j+1)%2,j)
        else:
            zs[j] = (ys[j],j%2,j)
        i = i>>1
#    print(zs)
    zs.sort()
    zs2 = [(0, -1, 0)]*N
    ll,rr=0,1
    for l, (z, m, j) in enumerate(zs):
        if m:
            if ll>=N:
                break
            zs2[ll] = (j, z, m)
            ll += 2
        else:
            if rr>=N:
                break
            zs2[rr] = (j, z, m)
            rr += 2
#    print(zs2)
    b, ff = 0, 0
    for j, z, m in zs2:
        if b>z:
            ff = 1
            break
        b = z
    if ff:
        continue
    zs2 = [j+1 for j,_,m in zs2]
    r = min(r, tento(zs2))
print(r if r != 10**18 else -1)

#    ff = 0
#    for l, (z, j,m) in enumerate(zs):
#        if (m-l)%2==0: 
#            ff = 1
#            break
#    if ff:
#        continue
#    zs = [j+1 for z,j,m in zs]


### FIXED CODE ###


from collections import defaultdict
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    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 tento(xs):
    bit = Bit(max(xs)+1)
    ans = 0
    for i, p in enumerate(xs):
        ans += i-bit.sum(p)
        bit.add(p, 1)
    return ans
N = int(input())
xs = list(map(int, input().split()))
ys = list(map(int, input().split()))
us = []
vs = []
for i in range(N):
    a, b = xs[i], ys[i]
    if i%2:
        us.append((a,i))
        vs.append((b,i))
    else:
        us.append((b,i))
        vs.append((a,i))
vs.sort()
r = 10**18
for i in range(2**N):
    t = 0
    tt = 0
    rs = [0]*N
    rs2 = [0]*(N//2)
    for j in range(N):
        if i%2:
            if 2*t < N:
                rs[t*2] = vs[j]
            t += 1
        else:
            if 2*tt+1 < N:
                rs2[tt] = us[vs[j][1]]
            tt += 1
        i = i>>1
    if t != (N+1)//2:
        continue
    rs2.sort()
    for i in range(N//2):
        rs[i*2+1] = rs2[i]
    b,ff = 0,0
    for z,j in rs:
        if b>z:
            ff = 1
            break
        b = z
    if ff:
        continue
#    print(rs)
    rs = [j+1 for _,j in rs]
    r = min(r, tento(rs))
print(r if r != 10**18 else -1)
### BUGGY CODE ###

A,B = map(int, input().strip().split(' '))

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

def make_primeset(N):
  if N == 2:
    return {2}
  else:
    result = {2}
    for i in range(3,N+1):
      flag = True
      for p in result:
        if i % p == 0:
          flag = False
          break
      if flag:
        result.add(i)
    return result

gcd_ = gcd(A,B)
if gcd_ == 1:
  print(1)
else:
  ans = 1  # 1のぶん
   # 素因数の種類数+1
  for p in make_primeset(gcd_):
    if gcd_ % p == 0:
      ans += 1
  print(ans)


### FIXED CODE ###

import fractions

A,B = map(int, input().strip().split(' '))

# 素因数分解
def trial_division(n):
  result = []
  while n % 2 == 0:
    result.append(2)
    n //= 2
  f = 3
  while f*f <= n:
    if n % f == 0:
      result.append(f)
      n //= f
    else:
      f += 2
  if n != 1:
    result.append(n)
  return result

gcd_ = fractions.gcd(A,B)
if gcd_ == 1:
  print(1)
else:
  print(len(set(trial_division(gcd_)))+1)
### BUGGY CODE ###

N = int(input())
S = input()
r = 0
g = 0
b = 0
for i in range(N):
    if S[i] == "R":
        r += 1
    elif S[i] == "G":
        g += 1
    else:
        b += 1
ans = r * g * b

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        if S[i] != S[j]:
            x = j + j - i
            if x <= N - 1 and S[i] != S[x] and S[x] != S[j]:
                ans -= 1

print(ans)


### FIXED CODE ###

N = int(input())
S = input()
ans = S.count("R") * S.count("G") * S.count("B")

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        if S[i] != S[j]:
            x = 2 * j - i
            if x < N and S[i] != S[x] and S[x] != S[j]:
                ans -= 1

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

n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))

table = [[]*n]*max(M)

def solve(i, m): 
    if m == 0:
        return True
    elif i >= n:
        return False
    else:
        res = solve(i + 1, m) or solve(i + 1, m - A[i])
        return res

for m in M:
    if solve(0, m):
        print('yes')
    else:
        print('no')

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))

table = [[-1 for i in range(max(M)+1)] for j in range(n)]

def solve(i, m):
    if m == 0:
        return True
    elif i >= n:
        return False
    elif table[i][m] != -1:
        return table[i][m]
    elif m - A[i] >= 0:
        res = solve(i + 1, m) or solve(i + 1, m - A[i])
        table[i][m] = res
        return res
    else:
        res = solve(i + 1, m)
        table[i][m] = res
        return res

for m in M:
    if solve(0, m):
        print('yes')
    else:
        print('no')
### BUGGY CODE ###

A,B = map(int,input().split())
K = 0
if (A+B)%2 == 0:
  while abs(A-K) - abs(B-K) != 0:
    K += 1
else:
  K = 'IMPOSSIBLE'
  
print(K)

### FIXED CODE ###

A,B = map(int,input().split())
K = 0
if (A+B)%2 == 0:
  K = int((A+B) /2)
else:
  K = 'IMPOSSIBLE'
  
print(K)
### BUGGY CODE ###

from functools import reduce
from fractions import gcd

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
mod = 10**9 + 7
n = int(input())
As = list(map(int, input().split()))

lcm = lcm_list(As)
b = [lcm//As[i] for i in range(n)]

print(sum(b) % mod)

### FIXED CODE ###

from functools import reduce
from fractions import gcd

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers)
mod = 10**9 + 7
n = int(input())
As = list(map(int, input().split()))

lcm = lcm_list(As)
b = [lcm//As[i] for i in range(n)]

print(sum(b) % mod)
### BUGGY CODE ###

N,M=[int(x) for x in input().split()]
I=[[] for n in range(N)]
ans = int(N * (N-1) / 2)
E=[]
result=[]

def visit(i,V):
    if(V[i]==0):
        V[i]=1
        total=1;
        for n in I[i]:
            if(V[n]==0):
                total+=visit(n,V)
        return total
    else:
        return 0

for m in range(M):
    A,B=[int(x) for x in input().split()]
    E.append((A-1,B-1))

for m in range(M):
    result.append(ans)
    if(ans>0):
        A,B=E.pop()
        V=[0 for n in range(N)]
        Wa=visit(A,V)
        Wb=visit(B,V)
        ans=ans-(Wa*Wb)
        I[A].append(B)
        I[B].append(A)

for r in reversed(result):
    print(r)


### FIXED CODE ###

N,M=[int(x) for x in input().split()]
G=[-1] * N
W=[0] * N
E=[]

result=[]
ans = int(N * (N-1) / 2)

def union(i,j):
    gi=find(i)
    gj=find(j)

    if(gi!=gj):
        if W[gi] > W[gj]:
            G[gi]+=G[gj]
            G[gj]=gi
        else:
            G[gj]+=G[gi]
            G[gi]=gj
            if W[gi]==W[gj]:
                W[gj]+=1

def find(i):
    if G[i]<0:
        return i;
    else:
        G[i]=find(G[i])
        return G[i]

for m in range(M):
    A,B=[int(x) for x in input().split()]
    E.append((A-1,B-1))

for m in range(M):
    result.append(ans)
    if(ans>0):
        A,B=E.pop()
        ga,gb=find(A),find(B)
        if (ga!=gb):
            ans=ans-(G[ga]*G[gb])
            union(A,B)

for r in reversed(result):
    print(r)
### BUGGY CODE ###

n = int(input())
L = tuple(map(int, input().split()))
L = sorted(L, reverse=True)

counts = 0
for i in range(n-2):
    a = L[i]
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            if a < L[j] + L[k]:
                counts += 1
print(counts)

### FIXED CODE ###

n = int(input())
L = tuple(map(int, input().split()))
L = sorted(L, reverse=True)

counts = 0
for i in range(n-2):
    a = L[i]
    for j in range(i+1, n-1):
        cc = a - L[j]
        left = j
        right = n
        while right - left > 1:
            mid = (right+left)//2
            if L[mid] > cc:
                left = mid
            else:
                right = mid
        counts += left - j
print(counts)
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n = INT()
a = LIST()

for i in range(n-1):
    for j in range(i+1, n):
        if a[i] == a[j]:
            print("NO")
            exit()
print("YES")




### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n = INT()
a = LIST()

# for i in range(n-1):
#     for j in range(i+1, n):
#         if a[i] == a[j]:
#             print("NO")
#             exit()
# print("YES")
if len(set(a)) != len(a):
    print("NO")
else:
    print("YES")
### BUGGY CODE ###

n = list(map(int,input().split()))
l = [list(map(int,input().split())) for i in range(n[1])]

passcard = []
for c in range(l[0][1] - l[0][0]+1):
    passcard.append(l[0][0]+c)

for t in range(n[1]):
    for i in range(len(passcard)):
        if not(l[t][0] <= passcard[i] <= l[t][1]):
            passcard[i] = 0
        else:
            passcard[i] = passcard[i]
    passcard = [i for i in passcard if i!=0]
            
out = [i for i in passcard if i!=0]
print(len(out))

### FIXED CODE ###

n = list(map(int,input().split()))
l = [list(map(int,input().split())) for i in range(n[1])]
minp = l[0][0]
maxp = l[0][1]
for t in range(n[1]):
    minp = max(minp,l[t][0])
    maxp = min(maxp,l[t][1])
print(max(0,maxp-minp+1))