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

N=int(input())
S=input()
import collections
import bisect
table=collections.defaultdict(list)
mod=10**9 +7
for i in range(N):
  table[S[i]].append(i)
ans=0
q=collections.deque()
for x in table:
  for y in table[x]:
    q.append((y,set([x])))
    ans+=1
    while(q):
      id,s=q.popleft()
      for z in table:
        if z in s:
          continue
        else:
          k=bisect.bisect_left(table[z],id)
          if k!= len(table[z]):
            for i in range(k,len(table[z])):
              q.append((table[z][i], s|{z}))
              ans+=1
            ans%=mod               
print(ans)
        
  
  

### FIXED CODE ###

import collections
N = int(input())
S = input()

table = collections.defaultdict(int)
for i in range(N):
    table[S[i]] += 1
ans = 1
mod = 10**9 + 7
alpha = 'abcdefghijklmnopqrstuvwxyz'
for x in alpha:
    ans *= table[x] + 1
    ans %= mod

print((ans-1) % mod)
### BUGGY CODE ###



def dice(p):
    sum = 0
    for i in range(1,p+1):
        sum += i/p
    return sum

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

m = 0
l = []
for i in range(n-k+1):
    t = sum(p[i:i+k])
    if(m <= t):
        l = p[i:i+k]
        m = t

res = 0
for i in l:
    res += dice(i)

print(res)











### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
num_li = [0]*n
for i in range(n):
    num_li[i] = (p[i]+1)/2

num = sum(num_li[:k])
ans = num
for j in range(n-k):
    num = num - num_li[j] + num_li[j+k]
    ans = max(num,ans)

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

N, M = map(int, input().split())
S = [list(map(int, input().split())) for i in range(M)]
ans = set(range(S[0][0], S[0][1] + 1))
for s in S[1:] :
    a = set(range(s[0], s[1] + 1))
    ans = ans & a
    if len(ans) == 0 :
        break
print(len(ans))

### FIXED CODE ###

import collections
N, M = map(int, input().split())
S = [list(map(int, input().split())) for i in range(M)]
smax = max([s[0] for s in S])
smin = min([s[1] for s in S])
if smin - smax + 1 >= 0 :
    print(smin - smax + 1)
else :
    print(0)


#S2 = [set(range(s[0], s[1] + 1)) for s in S]
#S3 = set.intersection(*S2)
#print(len(S3))

#ans = set(range(S[0][0], S[0][1] + 1))
#for s in S[1:] :
#    a = set(range(s[0], s[1] + 1))
#    ans = ans & a
#    if len(ans) == 0 :
#        break
#print(len(ans))
### BUGGY CODE ###

n,k=(int(i) for i in input().split())
l=[int(i) for i in input().split()]
l1=[0]*(k-1)+[1]
for i in range(k):
    l1[k-1]*=l[i]
for i in range(k,n):
    l1+=[(l1[i-1]//l[i-k])*l[i]]
for i in range(k,n):
    if(l1[i]>l1[i-1]):
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n,k=(int(i) for i in input().split())
l=[int(i) for i in input().split()]
for i in range(k,n):
    if(l[i]>l[i-k]):
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import collections

N = int(input())

Ninzu = []
for x in input().split():
	Ninzu.append(int(x))

for i in range(1,N):
	print(Ninzu.count(i))

print(0)

### FIXED CODE ###

import collections

N = int(input())

Ninzu = []
for x in input().split():
	Ninzu.append(int(x))

l = collections.Counter(Ninzu)

for i in range(1,N):
	print(l[i])

print(0)
### BUGGY CODE ###

import math
from collections import defaultdict
def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))

'''D'''
n=r()
a=rl()
b=[0]*(max(a)+1)
for i in a:
    if b[i]!=0:
        b[i]+=1
        continue
    else:
        b[i]+=1
    for j in range(2*i,max(a)+1,i):
        b[j]+=1
ans=0
for i in a:
    ans+=(1 if b[i]==1 else 0)
print(ans)

### FIXED CODE ###

import math
from collections import defaultdict
def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))

'''D'''
n=r()
a=rl()
ma=max(a)
b=[0]*(ma+1)
a.sort()
for i in a:
    if b[i]!=0:
        b[i]+=1
        continue
    else:
        b[i]+=1
    for j in range(2*i,ma+1,i):
        b[j]+=1
ans=0
for i in a:
    if b[i]==1:
        ans+=1
print(ans)
### BUGGY CODE ###

# coding: utf-8

from itertools import permutations
import sys

N, M, R = map(int, sys.stdin.readline().split())
r = [i - 1 for i in map(int, sys.stdin.readline().split())]

G = [[float('inf')] * N for _ in range(N)]

for i in range(N):
    G[i][i] = 0

for i in range(M):
    A, B, C = map(int, sys.stdin.readline().split())
    G[A-1][B-1] =  G[B-1][A-1] = C

# Warshall–Floyd Algorithm
for k in range(N):
    for i in range(N):
        for j in range(N):
            G[i][j] = min(G[i][j], G[i][k] + G[k][j]); 

ans = float('inf')

for i in permutations(r):
    ans = min(ans, sum([G[i[j]][i[j+1]] for j in range(R-1)]))

print ans


### FIXED CODE ###

# coding: utf-8

from itertools import permutations
import Queue

N, M, R = map(int, raw_input().split())
r = [i - 1 for i in map(int, raw_input().split())]

G = [[] for _ in xrange(N)]

for i in range(M):
    A, B, C = map(int, raw_input().split())
    A -= 1; B -= 1;
    G[A].append((B, C))
    G[B].append((A, C))

# dijkstra Algorithm
def dijkstra(s):
    d = [float("inf") for _ in xrange(N)]
    que = Queue.PriorityQueue()
    d[s] = 0
    que.put([0, s])

    while not que.empty():
        p = que.get()
        v = p[1]
        if d[v] < p[0]:
            continue
        for i, j in G[v]:
            if d[i] > d[v] + j:
                d[i] = d[v] + j
                que.put([d[i], i])
    return d

table = {}

for i in r:
    table[i] = dijkstra(i)

ans = float('inf')

for i in permutations(r):
    ans = min(ans, sum([table[i[j]][i[j+1]] for j in xrange(R-1)]))

print ans
### BUGGY CODE ###

N,A=map(int, input().split())
x=list(map(int, input().split()))
dp=[]
for _ in range(N+1):
    dp.append([[0 for _ in range(sum(x)+1)] for _ in range(N+1)])
for j in range(0,N+1):
    for k in range(0, N+1):
        for s in range(0, sum(x)+1):
            if j>=1 and s<x[j-1]:
                dp[j][k][s]=dp[j-1][k][s]
            elif j>=1 and k>=1 and s>=x[j-1]:
                dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-x[j-1]]
            elif j==0 and k==0 and s==0:
                dp[0][0][0]=1
            else:
                dp[j][k][s]=0
ans=0
for k in range(1,N+1):
    if k*A<=sum(x):
        ans+=dp[N][k][k*A]
print(ans)


### FIXED CODE ###

import sys
from sys import stdin
input = stdin.readline

def solve(N, A, x):
    W=sum(x)
    dp=[[[0]*(W+1) for _ in range(N+1)] for _ in range(N+1)]
    for j in range(N+1):
        dp[j][0][0]=1
    for j in range(1,N+1):
        xj=x[j-1]
        for k in range(1, N+1):
            for s in range(1, W+1):
                if s<xj:
                    dp[j][k][s]=dp[j-1][k][s]
                else:
                    dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-xj]

    ans=0
    for k in range(1,N+1):
        if k*A<=W:
            ans+=dp[N][k][k*A]
        else:
            break
    return ans


def main(args):
    N,A=map(int, input().split())
    x=[int(x) for x in input().split()]
    ans=solve(N,A,x)
    print(ans)

if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

k,s = map(int,input().split())

lst = []
for x in range(k+1):
    for y in range(x,k+1):
        for z in range(y,k+1):
            if x+y+z==s:
                lst.append((x,y,z))

cnt = 0
for e in lst:
    l = len(set(e))
    if l == 1:
        cnt += 1
    elif l == 3:
        cnt += 6
    else:
        cnt += 3

print(cnt)

### FIXED CODE ###

k,s = map(int,input().split())

cnt = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if 0 <= z <= k:
            cnt += 1
print(cnt)
### BUGGY CODE ###

import numpy as np
N,X,Y=map(int, input().split())
ans = np.zeros(N-1)
for i in range(1,N):
  for j in range(i+1,N+1):
    root1 = j-i
    root2 = abs(X-i) + 1 + abs(Y-j)
    min_k = min(root1, root2)
    ans[min_k-1] = ans[min_k-1] + 1

for a in ans:
  print(int(a))

### FIXED CODE ###

import numpy as np
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):
    root1 = j-i
    root2 = abs(X-i) + 1 + abs(Y-j)
    min_k = min(root1, root2)
    ans[min_k-1] = ans[min_k-1] + 1

for a in ans:
  print(a)
### BUGGY CODE ###

n,m = map(int, input().split())
py = []
l = [[] for _ in range(n+1)]
for _ in range(m):
  p,y = map(int, input().split())
  l[p].append(y)
  py.append((p,y))
  
for i in l: i.sort()

for p,y in py:
  s = str(p)
  t = str(l[p].index(y)+1)
  ans = "0"*(6-len(s))+s + "0"*(6-len(t))+t
  print(ans)

### FIXED CODE ###

from bisect import bisect_left
n,m = map(int, input().split())
py = []
l = [[] for _ in range(n+1)]
for _ in range(m):
  p,y = map(int, input().split())
  l[p].append(y)
  py.append((p,y))
  
for i in l: i.sort()

for p,y in py:
  s = str(p)
  t = str(bisect_left(l[p],y)+1)
  ans = "0"*(6-len(s))+s + "0"*(6-len(t))+t
  print(ans)
### BUGGY CODE ###

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

MOD = 10 ** 9 + 7
N=int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]

dp = np.zeros(1<<N, dtype=np.int64)
dp[0] = 1

for A_row in A:
    prev = dp.copy()
    dp = np.zeros_like(prev)
    for n,a in enumerate(A_row):
        if a == 0:
            continue
        x = 1<<n
        dp = dp.reshape(-1,2*x)
        prev = prev.reshape(-1,2*x)
        dp[:,x:] += prev[:,:-x]
        dp = dp.ravel()
        prev = prev.ravel()
    dp %= MOD

answer = dp[-1]
print(answer)

### FIXED CODE ###

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

MOD = 10 ** 9 + 7
N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]

bit_count = [0]
for _ in range(N):
    bit_count += [x+1 for x in bit_count]
    
dp = [0] * (1<<N)
dp[0] = 1

for i in range((1<<N)-1):
    k = bit_count[i]
    for c in range(N):
        if A[k][c]:
            dp[(1<<c)^i] += dp[i]

answer = dp[-1] % MOD
print(answer)
### BUGGY CODE ###

k = int(input())
c = 0
q = [1, 2, 3, 4, 5, 6, 7, 8, 9]
i = 0
while True:
    i = q.pop(0)
    c += 1
    if c == k:
        break
    else:
        e = int(str(i)[-1])
        if e == 0:
            q.append(int(str(i)+str(e)))
            q.append(int(str(i)+str(e+1)))
        elif e == 9:
            q.append(int(str(i)+str(e-1)))
            q.append(int(str(i)+str(e)))
        else:
            q.append(int(str(i)+str(e-1)))
            q.append(int(str(i)+str(e)))
            q.append(int(str(i)+str(e+1)))

print(i)

### FIXED CODE ###

from collections import deque
k = int(input())
c = 0
q = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
i = 0
while True:
    i = q.popleft()
    c += 1
    if c == k:
        break
    else:
        e = int(str(i)[-1])
        if e == 0:
            q.append(int(str(i)+str(e)))
            q.append(int(str(i)+str(e+1)))
        elif e == 9:
            q.append(int(str(i)+str(e-1)))
            q.append(int(str(i)+str(e)))
        else:
            q.append(int(str(i)+str(e-1)))
            q.append(int(str(i)+str(e)))
            q.append(int(str(i)+str(e+1)))

print(i)
### BUGGY CODE ###

n=int(input())
D=list(map(int,input().split()))
D.sort()
for i in range(1, n):
    l = D[:i]
    r = D[i:]
    if len(l) == len(r):
        ans = r[0] - l[-1]
print(ans)

### FIXED CODE ###

n=int(input())
D=list(map(int,input().split()))
D.sort()
i = int(n / 2) - 1
ans = D[i+1] - D[i]
print(ans)
### BUGGY CODE ###

from fractions import gcd
def lcm(a, b):
    return a * b // gcd(a, b)

N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7

L = A[0]
for a in A:
  L = lcm(a,L)
ans = 0
for a in A:
  ans += L//a
  ans %= MOD
print(ans)

### FIXED CODE ###

def main():
  import sys
  input = sys.stdin.readline
  from fractions import gcd
  def lcm(a, b):
      return a * b // gcd(a, b)
  
  N = int(input())
  A = tuple(sorted(list(map(int,input().split()))))
  MOD = 10**9+7
  
  L = 1
  for a in A:
    L = lcm(a,L)
  ans = 0
  for a in A:
    #ans += L//a
    ans += L*pow(a,MOD-2,MOD)
  print(ans%MOD)

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

L=input()
length=len(L)
inf=10**9+7
a=1
b=0
for i in range(0,len(L)):
	if L[i]=="0":
		continue
	else:
		b+=a*(3**(length-i-1))%inf
		a=a*2%inf
print((a+b)%inf)


### FIXED CODE ###

L=input()
length=len(L)
inf=10**9+7
a=2
b=1
for i in range(1,len(L)):
	if L[i]=="0":
		b=b*3%inf
		continue
	else:
		b=(b*3+a)%inf
		a=a*2%inf
print((a+b)%inf)
### BUGGY CODE ###

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

counter = {}
sum = 0
for b in set(balls):
  n = balls.count(b)
  counter[b] = n
  sum += n * (n-1) // 2

for b in balls:
  n_old = counter[b]
  c_old = n_old * (n_old - 1) // 2
  c_new = (n_old - 1) * (n_old - 2) // 2
  
  result = sum - c_old + c_new
  print(result)

### FIXED CODE ###

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

counter = {}
for b in balls:
  counter[b] = counter.get(b, 0) + 1

sum = 0
for v in counter.values():
  sum += v * (v-1) // 2
  
for b in balls:
  n_old = counter[b]
  c_old = n_old * (n_old - 1) // 2
  c_new = (n_old - 1) * (n_old - 2) // 2
  
  result = sum - c_old + c_new
  print(result)
### BUGGY CODE ###

N = int(input())
ans_list = []

for i in range(N):
    A = int(input())
    if A in ans_list:
        ans_list.pop(ans_list.index(A))
    else:
        ans_list.append(A)

print(len(ans_list))

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())

# 集合　listよりも 検索などが高速
# 重複なしの順序も無し
ans_set = set()

for i in range(N):
    A = int(input())
    if A in ans_set:
        ans_set.remove(A)
    else:
        ans_set.add(A)

print(len(ans_set))
### BUGGY CODE ###

import sys

s = str(sys.stdin.readline())
count = 0
f = False
while True:
  for i in range(len(s)-1):
    if s[i] == '0' and s[i+1] == '1':
      count += 2
      s = s[:i] + s[i+2:]
      f = True
      break 
    if s[i] == '1' and s[i+1] == '0':
      count += 2
      f = True
      s = s[:i] + s[i+2:]
      break 
  if f:
    f = False
    continue
  break
print(count)

### FIXED CODE ###

import sys

s = str(sys.stdin.readline())
c0 = s.count('0')
c1 = s.count('1')
r = c0 if c0 < c1 else c1
print(r*2)
### BUGGY CODE ###

from heapq import *
from numpy import array,inf


def djikstra(s):
    que = []
    d = [inf]*V
    d[s] = 0
    heappush(que,(0,s))
    while(len(que)!=0):
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(G[v])):
            e = G[v][i]
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heappush(que,(d[e[0]],e[0]))
    return d


n,m,s,t = map(int,input().split())
V = n
Ga = [[] for i in range(n)]
Gb = [[] for i in range(n)]
for i in range(m):
    u,v,a,b = map(int,input().split())
    Ga[u-1].append((v-1,a))
    Ga[v-1].append((u-1,a))
    Gb[u-1].append((v-1,b))
    Gb[v-1].append((u-1,b))

G = Ga
S = djikstra(s-1)
G = Gb
T = djikstra(t-1)

M = 10**15-(array(S)+array(T))
ans = [0]*n
ans[n-1] = M[n-1]
for i in range(n-2,-1,-1):
    ans[i] = max(ans[i+1],M[i])

for i in range(n):
    print(ans[i])


### FIXED CODE ###

from heapq import *
from numpy import array,inf


def djikstra(G,s):
    que = []
    d = [inf]*V
    d[s] = 0
    visited = [False] * V
    heappush(que,(0,s))
    while(len(que)!=0):
        p = heappop(que)
        v = p[1]
        if visited[v]:
            continue
        visited[v] = True
        for i in range(len(G[v])):
            e = G[v][i]
            if visited[e[0]]:
                continue
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heappush(que,(d[e[0]],e[0]))
    return d


n,m,s,t = map(int,input().split())
V = n
Ga = [[] for i in range(n)]
Gb = [[] for i in range(n)]
for i in range(m):
    u,v,a,b = map(int,input().split())
    Ga[u-1].append((v-1,a))
    Ga[v-1].append((u-1,a))
    Gb[u-1].append((v-1,b))
    Gb[v-1].append((u-1,b))

S = djikstra(Ga,s-1)

T = djikstra(Gb,t-1)

M = 10**15-(array(S)+array(T))
ans = [0]*n
ans[n-1] = M[n-1]
for i in range(n-2,-1,-1):
    ans[i] = max(ans[i+1],M[i])

for i in range(n):
    print(ans[i])
### BUGGY CODE ###

#累積和の利用！！！！！！！！
from itertools import accumulate
n,k = map(int,input().split())
p = list(map(int,input().split()))

def expect_dice(n):
    return sum(range(1,n+1))/n 

for i in range(len(p)):
    p[i] = expect_dice(p[i])
    
p = [0] + p
p = list(accumulate(p))

ans = []
for i in range(n-k+1):
    ans.append(p[i+k] - p[i])
    
print(max(ans))

### FIXED CODE ###

#累積和の利用！！！！！！！！
from itertools import accumulate
n,k = map(int,input().split())
p = list(map(int,input().split()))

m = [(e + 1) / 2 for e in p]
    
m = [0] + m
m = list(accumulate(m))

ans = []
for i in range(n-k+1):
    ans.append(m[i+k] - m[i])
    
print(max(ans))
### BUGGY CODE ###

from bisect import bisect_left,bisect_right
import bisect
from collections import defaultdict
N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
S=[[] for i in range(30)]
num=[0]*30
for i in range(30):
    t = pow(2,i)
    for b in B:
        bisect.insort_left(S[i],b%(2*t))
for i in range(30):
    t = pow(2,i)
    dd =defaultdict(int)
    for a in A:
        dd[a%(2*t)] +=1
    #L=[i%(2*t) for i in B]
    L=S[i]
    #print(K,L)
    a = 0
    for k,l in dd.items():
        x = bisect_left(L,2*t-k)-bisect_left(L,t-k)
        y = bisect_left(L,4*t-k)-bisect_left(L,3*t-k)
        #print(x,y)
        a =(a+x*l+y*l)%2
    num[i]=a
ans =0
s=1
for z in num:
    ans += z*s
    s*=2
print(ans)




### FIXED CODE ###

from bisect import bisect_left,bisect_right
N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

num=[0]*30
for i in range(30):
    t = pow(2,i)
    K=sorted(i%(2*t) for i in A)
    L=sorted(i%(2*t) for i in B)
    #L=sort()
    #print(K,L)
    a = 0
    #尺取り法,i*tより小さい整数を数える
    S=[i*t for i in range(1,5)]
    count=[N]*4
    for k in K:
        for j in range(4):
            while L[count[j]-1]+k>=S[j] and count[j]>0:
                count[j]-=1
        a +=count[3]-count[2]+count[1]-count[0]
        #print(count,a)
    num[i]=a%2
ans =0
s=1
for z in num:
    ans += z*s
    s*=2
print(ans)
### BUGGY CODE ###

K=int(input())
i=0
current_num=0
while (i<K) :
  current_num+=1
  current_string=str(current_num)
  flag=True
  for k in range(len(current_string)-1) :
    if abs(int(current_string[k])-int(current_string[k+1]))>1 :
      flag=False
      break
  if flag==True :
    i+=1
  
  
print(current_num)

### FIXED CODE ###

from collections import deque
a=int(input())
list1=deque([1,2,3,4,5,6,7,8,9])
i=1
while(i<=a) :
  #print (list1)
  if i!=a :
    k=list1.popleft()
    k=str(k)
    if int(k[-1])==0 :
      list1.append(int(str(k)+'0'))
      list1.append(int(str(k)+'1'))
      i+=1
    elif int(k[-1])==9 :
      list1.append(int(str(k)+'8'))
      list1.append(int(str(k)+'9'))
      i+=1
    else :
      list1.append(int(str(k)+str(int(k[-1])-1)))
      list1.append(int(str(k)+str(int(k[-1]))))
      list1.append(int(str(k)+str(int(k[-1])+1)))
      i+=1
  else :
    print(list1[0])
    break
### BUGGY CODE ###

n=int(input())
g=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append((b-1,i))

vc=[[] for _ in range(n)]
ec=[-1]*(n-1)
for p,ci in enumerate(g):
    color = 1
    for c, i in ci:
        while True:
            if color not in vc[p]:
                vc[p].append(color)
                vc[c].append(color)
                ec[i] = color
                break
            else:
                color += 1
        

print(max(ec))
for i in range(n-1):
    print(ec[i])


### FIXED CODE ###

n=int(input())
g=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append((b-1,i))

vc=[0] * n
ec=[-1]*(n-1)
for p,ci in enumerate(g):
    color = 1
    for c, i in ci:
        if vc[p] == color:
            color += 1
        vc[c] = color
        ec[i] = color
        color += 1
        

print(max(ec))
for i in range(n-1):
    print(ec[i])
### BUGGY CODE ###

inf = 1001001001
n = int(input())
lis = list(map(int, input().split()))
lis.sort()
ans = 0
for i in range(n-1):
    a = lis[i]
    for j in range(i + 1, n):
        b = lis[j]
        nl = lis[j:]
        nl.append(inf)
        l = 0
        r = n-j
        while r > l+1:
            mid = (l+r) // 2
            if nl[mid] < a + b:
                l = mid
            else:
                r = mid
        ans += l
print(ans)

### FIXED CODE ###

inf = 1001001001
n = int(input())
lis = list(map(int, input().split()))
lis.sort()
lis.append(inf)
ans = 0
for i in range(n-2):
    a = lis[i]
    for j in range(i + 1, n-1):
        b = lis[j]
        l = j
        r = n
        while r > l+1:
            mid = (l+r) // 2
            if lis[mid] < a + b:
                l = mid
            else:
                r = mid
        ans += l - j
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())

broken_step = []
for _ in range(M):
    broken_step.append(int(input()))
    
import sys
sys.setrecursionlimit(10000000)

mod = 1000000007

memo = [-1] * (N+1)

if 0 not in broken_step:
    memo[0] = 1
elif N == 0 and N in broken_step:
    memo[0] = 0

if 1 not in broken_step:
    memo[1] = 1
elif 1 in broken_step:
    memo[1] = 0

def step_memo(N):
    
    if N in broken_step:
        broken_step.remove(N)
        memo[N] = 0
        return 0
        
    if memo[N] != -1:
        return memo[N]
    
    memo[N] =  (step_memo(N-1) + step_memo(N-2)) % mod
    return (step_memo(N-1) + step_memo(N-2)) % mod
  
print(step_memo(N))

### FIXED CODE ###

N, M = map(int, input().split())
import sys
sys.setrecursionlimit(10000000)

mod = 1000000007

memo = [-1] * (N+1)

for _ in range(M):
    broken_step = int(input())
    memo[broken_step] = 0
    
memo[0] = 1
if memo[1] == -1:
    memo[1] = 1

def step_memo(N):
    
    if memo[N] != -1:
        return memo[N]
    
    memo[N] =  (step_memo(N-1) + step_memo(N-2)) % mod
    return (step_memo(N-1) + step_memo(N-2)) % mod
  
print(step_memo(N))
### BUGGY CODE ###

A, B, K = list(map(int, input().split()))
ans = [i for i in range(A,B+1)]
res = []
for i in ans[:K]:
    res.append(i)
for i in ans[-K:]:
    res.append(i)
for i in sorted(list(set(res))):
    print(i)


### FIXED CODE ###

A, B, K = list(map(int, input().split()))
ans = set() 
mi = max(B-K+1, A)
ma = min(A+K, B+1)
for i in range(A, ma):
    ans.add(i)
for i in range(mi, B+1):
    ans.add(i)
ans = list(ans)
for i in sorted(ans):
    print(i)
### BUGGY CODE ###

MOD = 10**9 + 7
N = int(input())
A = list(map(int, input().split()))
bit = [0] * 60
for i in range(N):
  n = A[i]
  cnt = 0
  while(n>=1):
    bit[cnt] += n%2
    n = n//2
    cnt += 1
ans = 0
POW = 1
for j in range(60):
  ans = (ans +bit[j]*(N-bit[j])*POW)%MOD
  POW = (POW * 2)%MOD
print(ans%MOD)

### FIXED CODE ###

MOD = 10**9 + 7
N = int(input())
A = list(map(int, input().split()))
bit = [0] * 60
for i in range(N):
  n = bin(A[i])
  for j in range(len(n)-1, 1, -1):
    bit[len(n)-j-1] += int(n[j])
ans = 0
POW = 1
for j in range(60):
  ans = (ans +bit[j]*(N-bit[j])*POW)%MOD
  POW = (POW * 2)%MOD
print(ans%MOD)
### BUGGY CODE ###

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

distList = []

for idx, dist in enumerate(As):
  if idx == 0:
    distList.append(K - As[-1] + dist)
  else:
    distList.append(dist - As[idx - 1])

min_dist = 0
for idx, dist in enumerate(distList):
  target_dist = 0
  for i in range(N - 1):
    if idx == 0:
      target_dist += distList[idx - i]
      min_dist = target_dist
    else:
      target_dist += distList[idx - i]
  if target_dist < min_dist:
    min_dist = target_dist
print(min_dist)

### FIXED CODE ###

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

As.append(K + As[0])
print(K - max([y - x for x,y in zip(As, As[1:])]))