Harryxun/stf_run huggingface dataset:
N = int(input())
x = list(input())[::-1]
num = 0
nump = 0
numm = 0
pop_num = 0
for i in range(N):
    if x[i] == "1":
        pop_num += 1
for i in range(N):
    if x[i] == "1":
        num += pow(2,i,pop_num)
        num %= pop_num 
        num += pow(2,i,pop_num+1)
        nump %= pop_num  + 1
        num += pow(2,i,pop_num - 1)
        numm %= pop_num - 1



def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

x = x[::-1]
def calc(i,depth,n):
    if depth == 0:
        if x[i] == "1":
            tmp = numm
            tmp -=  2 ** (N - i - 1)
            tmp %= (pop_num - 1)
            return calc(i,depth+1,tmp)
        else:
            tmp = nump
            tmp +=  2 ** (N - i - 1)
            tmp %= (pop_num + 1)
            return calc(i,depth+1,tmp)
    else:
        if n == 0: return depth
        return calc(i,depth+1, n % popcnt(n))
        

for i in range(N):
    print(calc(i,0,0))



### FIXED CODE ###

N = int(input())
x = list(input())[::-1]
num = 0
nump = 0
numm = 0
pop_num = 0
for i in range(N):
        if x[i] == "1":
            pop_num += 1
for i in range(N):
    if x[i] == "1":
        num += pow(2,i,pop_num)
        num %= pop_num 
        nump += pow(2,i,pop_num+1)
        nump %= pop_num  + 1
        if pop_num-1 != 0:
            numm += pow(2,i,pop_num - 1)
            numm %= pop_num - 1



def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

x = x[::-1]
def calc(i,depth,n):
    if depth == 0:
        if x[i] == "1":
            tmp = numm
            if pop_num - 1 != 0:
                tmp -= pow(2,N-i-1,pop_num-1)
                tmp %= (pop_num - 1)
            else:
                return 0
            return calc(i,depth+1,tmp)
        else:
            tmp = nump
            tmp += pow(2,N-i-1,pop_num+1)
            tmp %= (pop_num + 1)
            return calc(i,depth+1,tmp)
    else:
        if n == 0: return depth
        return calc(i,depth+1, n % popcnt(n))
        

for i in range(N):
    print(calc(i,0,0))
import math
n=int(input())
arr=list(map(int,input().split()))
dic={}
for c in arr:
    dic.setdefault(c,0)
    dic[c]+=1
ans=True
#n is odd 5(4 2 0 2 4)
if n%2!=0:
    if dic[0]!=1:
        ans=False
        print(0)
    for c in range(2,n-1,2):
        if dic[c]!=2:
            ans=False
            break
#n is even 8 (7 5 1 1 7 3 5 3)        
else:
    for c in range(1,n-1,2):
        if dic[c]!=2:
            ans=False
if ans:
    print(2**math.floor(n/2)%((10**9)+7))
else:
    print(0)
  

### FIXED CODE ###

N=int(input())
l=list(map(int,input().split()))
a=1
if N%2==0:
    if len(l)!=len(set(l))*2:
        a=0
else:
    if l.count(0) == 1:
        l.remove(0)
        if len(l) != 2*len(set(l)):
            a = 0
    else:
        a=0
if a:
      print((2**(N//2))%(10**9+7))
else:
      print(0)
def main() {
    n = int(input())
    ans = n * (n + 1) * (n + 2) // 6;
    for i in range(n):
        x, y = map(int, input().split())
        if (x > y) { y, x = x, y; }
        ans -= x * (n - y + 1);
    }
    print(ans);
}
main()

### FIXED CODE ###

def main():
    n = int(input())
    ans = n * (n + 1) * (n + 2) // 6
    
    for i in range(n-1):
        x, y = map(int, input().split())
        if x > y:
            y, x = x, y
        ans -= x * (n - y + 1)
    print(ans)
    
main()
n=int(input())
if n==1:print(2)
elif n==2:print(1)
else:
    nu1=2
    nu2=1
    for i in range(n-1):
        nu3=nu1+nu2
        nu1=nu2
        nu2=nu3
print(nu3)

### FIXED CODE ###

n=int(input())
if n==0:
    print(2)
    exit()
elif n==1:
    print(1)
    exit()
else:
    nu1=2
    nu2=1
    for i in range(n-1):
        nu3=nu1+nu2
        nu1=nu2
        nu2=nu3
print(nu3)
n,k = map(int,input().split())
ls = []
b_num = 0

for i in range(n):
    a,b = [int(i) for i in input().split()]
    if b_num <= k:
        tmp = [a] * b
        ls.extend(tmp)
        ls.sort()
        b_num += b
    else:
        if(a <= ls[-1]):
            tmp = [a] * b
            ls.extend(tmp)
            ls.sort()
        
print(ls[k-1])

### FIXED CODE ###

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

for i in range(m):
    a,b = [int(i) for i in input().split()]
    road.append([a,b])

road = sum(road,[])
#print(road)
    
for j in range(n):
   print (road.count(j+1))
def mod3(n):
    b= n
    sho = []
    while b >= 1:
        a = int(b % 3)
        b = int((b - a)/3)
        sho.append(a)
    return sho

def cal_dis(ss,tt):
    s,t = mod3(ss),mod3(tt)
    if len(s) == len(t):
        n = len(s)
        k = 0
        for i in range(n):
            if s[i] == 1 and t[i] == 1:
                k = i+1
                if i > 0:
                    b = abs(s[i-1] - t[i-1])
        a = ss - tt if ss > tt else tt-ss
        return a + 2*k - 2* b

    else:
        return ss - tt if ss > tt else tt-ss

N = int(input())
dic ={}
for i in range(N):
    dic[i] = [int(a) for a in input().split(' ')]

for i in range(N):
    s = [dic[i][0]-1,dic[i][1]-1]
    t = [dic[i][2]-1,dic[i][3]-1]


    print(cal_dis(s[0],t[0]) + cal_dis(s[1], t[1]))

### FIXED CODE ###

def solve(A,B,C,D, level):
    E = 3**level
    if level == -1:
        return int(abs(A-C) + abs(B-D))
    a,b,c,d = A//E, B//E, C//E, D//E
    if a != c and b != d:
        return int(abs(A-C) + abs(B-D))

    if a == c and b==d:
        return solve(A,B,C,D,level-1)

    if a != c and b==d:
        A,B,C,D = B,A,D,C
        a,b,c,d = b,a,d,c

    if b != d and a == c:
        if a%3 != 1:
            return solve(A,B,C,D,level-1)
        if abs(b-d) == 1:
            return solve(A,B,C,D,level-1)

        if B > D:
            A, B, C, D = C, D, A, B
            a, b, c, d = c, d, a, b

        x = E * a -1
        y1 = E * (b+1) -1
        y2 = E * d
        d = abs(x-A) + abs(y1-B) + abs(y1-y2) + abs(x-C) + abs(y2-D)
        x = E *(a+1)
        d2 = abs(x-A) + abs(y1-B) + abs(y1-y2) + abs(x-C) + abs(y2-D)
        return min(d,d2)

N = int(input())

for i in range(N):
    sg = [int(j.strip())  for j in input().split(' ')]
    s,g = [sg[0]-1,sg[1]-1],[sg[2]-1,sg[3]-1]
    A,B,C,D = s[0],s[1],g[0],g[1]
    print(solve(A,B,C,D,30))
import math
a, b = map(int, input().split())
def lcm(aa, bb):
    return (aa*bb)//math.gcd(aa, bb)
print(lcm(a, b))    

### FIXED CODE ###

import fractions
a, b = map(int, input().split())
def lcm(aa, bb):
    return (aa*bb)//fractions.gcd(aa, bb)
print(lcm(a, b))
from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def main():
    
    h, w = map(int, input().split())
    a = [input() for i in range(h)]
    queue = []
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                queue.append([i, j])

    visited = [[-1 for i in range(w)] for j in range(h)]
    ans = 0
    nqueue = []
    while queue:
        x, y = queue.pop(0)
        visited[x][y] = 1
        for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            nx = x + i
            ny = y + j
            if nx >= 0 and ny >= 0 and nx < w and ny < h:
                if visited[nx][ny] == -1:
                    nqueue.append([nx, ny])
                    visited[nx][ny] = 1
        
        if len(queue) == 0:
            queue = nqueue
            nqueue = []
            ans += 1
    print(ans-1)


        
                





if __name__ == '__main__':
    main()


### FIXED CODE ###

from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def main():
    
    h, w = map(int, input().split())
    a = [list(input()) for i in range(h)]
    queue = deque()
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                queue.append((i, j))

    visited = [[-1 for i in range(w)] for j in range(h)]
    ans = 0
    nqueue = deque()
    while queue:
        x, y = queue.popleft()
        visited[x][y] = 1
        for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            nx = x + i
            ny = y + j
            if nx >= 0 and ny >= 0 and nx < h and ny < w:
                if visited[nx][ny] == -1 and a[nx][ny] != "#":
                    nqueue.append([nx, ny])
                    visited[nx][ny] = 1
                    a[nx][ny] = "#"
        
        if len(queue) == 0:
            queue = nqueue
            nqueue = deque()
            ans += 1
        
    print(ans-1)

if __name__ == '__main__':
    main()
b=[1]*2**31
for i in range(3,100,2):
 if b[i//2]:b[i*i//2::i]=[0]*len(b[i*i//2::i])
print(sum(b[int(input())]for _ in[0]*int(input())))


### FIXED CODE ###

b=[1]*500000
for i in range(3,999,2):
 if b[i//2]:b[i*i//2::i]=[0]*len(b[i*i//2::i])
def p(x):
 if x<5*1e5:return b[x]
 x=2*x+1
 for i in range(3,int(x**.5+1),2):
  if x%i==0:return 0
 return 1
print(sum(p(int(input()))for _ in[0]*int(input())))
N,T=map(int,input().split())
root=[tuple(map(int,input().split())) for i in range(N)]

minc=1000
for cand in range(N):
    if cand[1]<=T:
        if cand[0]<minc:
            minc=cand[0]
if minc==1000:
    print("TLE")
else:
    print(minc)

### FIXED CODE ###

N,T=map(int,input().split())
root=[tuple(map(int,input().split())) for i in range(N)]

minc=1001
for cand in root:
    if cand[1]<=T:
        if cand[0]<minc:
            minc=cand[0]
if minc==1001:
    print("TLE")
else:
    print(minc)
X=int(input())
ps=[]
x=2
while x=<X:
  f=True
  for p in ps:
    if x%p==0:
      f=False
      break
  if f:ps.append(x)
  x+=1
print(x)

### FIXED CODE ###

def is_prime(p):
  if p>1:
    for i in range(2,p):
      if p%i==0:return True
  return False

X=int(input())
p=X
while is_prime(p) != False:p+=1
print(p)
from sys import stdin


def main():

    S = stdin.readline().rstrip()
    S_len = len(S)

    sum = 0
    s = S[0]
    x = 1

    while True:
        if len(s) == 1:
            if s == S[x]:
                s = s + S[x]
            else:
                sum += 1
                s = S[x]
        else:
            sum += 2
            x += 1
            s = S[x]
        x += 1

        if x == S_len:
            sum += 1
            break

    print(sum)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from sys import stdin


def main():

    S = stdin.readline().rstrip()
    S_len = len(S)

    sum = 0
    s = S[0]
    x = 1

    while True:
        if len(s) == 1:
            if s == S[x]:
                s = s + S[x]
            else:
                sum += 1
                s = S[x]
        else:
            sum += 2
            x += 1

            if x >= S_len:
                break
            s = S[x]
        x += 1

        if x >= S_len:
            sum += 1
            break

    print(sum)


if __name__ == "__main__":
    main()
N = int(input())
a = [int(input()) for _ in range(N)]
a.sort()
res = a[-2] % 2
print("second" if res == 0 else "first")

### FIXED CODE ###

N = int(input())
a = [int(input()) % 2 for _ in range(N)]
res = sum(a)
print("first" if res > 0 else "second")
s = input()
ss = s.split('/')
sss = ''.join(ss)

if sss>20190430:
    print("TBD")
else:
    print("Heisei")

### FIXED CODE ###

Y, M, D = map(str, input().split("/"))
s = ''.join([Y,M,D])

if int(s)>20190430:
    print("TBD")
else:
    print("Heisei")
from collections import deque
N = int(input())
A = sorted(list(map(int,input().split())))
A = deque(A)
C = []
if A[-1]<=0:
    a = A.pop()
    b = A.pop()
    C.append((a,b))
    A.append(a-b)
B = deque(list(A)[:-1])
while B[-1]>0:
    a = B.popleft()
    b = B.pop()
    C.append((a,b))
    B.appendleft(a-b)
B.append(A[-1])
while len(B)>1:
    a = B.pop()
    b = B.popleft()
    C.append((a,b))
    B.append(a-b)
print(a-b)
for i in range(N-1):
    print(C[i][0],C[i][1])


### FIXED CODE ###

from collections import deque
N = int(input())
A = sorted(list(map(int,input().split())))
A = deque(A)
C = []
while len(A)>1 and A[-1]<=0:
    a = A.pop()
    b = A.pop()
    C.append((a,b))
    A.append(a-b)
if len(A)==1:
    x = A[0]
else:
    B = deque(list(A)[:-1])
    while B[-1]>0:
        a = B.popleft()
        b = B.pop()
        C.append((a,b))
        B.appendleft(a-b)
    B.append(A[-1])
    while len(B)>1:
        a = B.pop()
        b = B.popleft()
        C.append((a,b))
        B.append(a-b)
    x = B[0]
print(x)
for i in range(N-1):
    print(C[i][0],C[i][1])
n,k = map(int,input().split())
p = list(map(int,input().split()))
ans = 0
for i in range(n):
  a = p[i:i+k]
  ans = (max(ans,sum(a))
  if i+k == n:
       break
       
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

    tmp_max = sum(P[:K])
    tmp = sum(P[:K])
    for i in range(N-K):
        tmp += P[i+K]
        tmp -= P[i]

        if tmp > tmp_max:
            tmp_max = tmp

    print((tmp_max + K) / 2)

main()
from collections import deque
import sys
input=sys.stdin.readline


def solve():
    H, W = map(int, input().split())
    m = [[-1]*W for _ in range(H)]
    candidate = [(i, j, 0) for i in range(H) for j, s in enumerate(input()) if s=="#"]
    q = deque(candidate)
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    while q:
        y, x, cost = q.popleft()
        m[y][x] = cost

        for i in range(4):
            x1, x2 = x + dx[i], y + dy[i]
            if not (0<=x1<W and 0<=y1<H):
                continue
            if m[y1][x1] == -1:
                q.append((y1, x1, cost+1))

    print(max(map(max, m)))


if __name__ == "__main__":
    solve()


### FIXED CODE ###

from collections import deque


def solve():
    H, W = map(int, input().split())
    m = [[-1]*W for _ in range(H)]
    l = [list(input()) for _ in range(H)]
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    q = deque([])

    for i in range(H):
        for j in range(W):
            if l[i][j]=="#":
                q.append((i, j))
                m[i][j] = 0
    
    while q:
        y, x = q.popleft()

        for px, py in zip(dx, dy):
            x1, y1 = x + px, y + py
            if not (0<=x1<W and 0<=y1<H):
                continue
            if m[y1][x1] == -1:
                q.append((y1, x1))
                m[y1][x1] = m[y][x] + 1

    print(max(map(max, m)))


if __name__ == "__main__":
    solve()
from collections import defaultdict

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

d = defaultdict(int)
for i in range(n):
    for j in range(n):
        if i== j:
            continue
        a,b = l[i]
        c,e = l[j]
        d[(a-c,b-e)] += 1
ans = n
m = max(d.values())
for i,j in d.items():
    if j != m:
        continue

    x,y = i
    if x==0 and y == 0:
        continue
    count = 0
    for c,d in l:
        if [c+x,d+y] in l:
            count += 1
    ans = min(ans,n-count)
print(ans)

### FIXED CODE ###

from collections import defaultdict

n = int(input())
l = [list(map(int,input().split())) for i in range(n)]
if n == 1:
    print(1)
    exit()
d = defaultdict(int)
for i in range(n):
    for j in range(n):
        if i== j:
            continue
        a,b = l[i]
        c,e = l[j]
        d[(a-c,b-e)] += 1
ans = n
m = max(d.values())
for i,j in d.items():
    if j != m:
        continue

    x,y = i
    if x==0 and y == 0:
        continue
    count = 0
    for c,d in l:
        if [c+x,d+y] in l:
            count += 1
    ans = min(ans,n-count)
print(ans)
import sys

stdin = sys.stdin

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

a = ni()
b = ni()

if a >= 9 or b >= 9:
    print(":(")
else:
    print("Yay!")


### FIXED CODE ###

import sys

stdin = sys.stdin

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

a,b = na()

if a >= 9 or b >= 9:
    print(":(")
else:
    print("Yay!")
x = input()
pow(x, 3)

### FIXED CODE ###

x = int(input())
print(x ** 3)
a = [list(map(int, input().split())) for i in range(2)]
a[0][0] = H
a[0][1] = W
a[1][0] = h
a[1][1] = w
my_result = H * W - h * W - H * w + h * w
print(my_result)

### FIXED CODE ###

a = [list(map(int, input().split())) for i in range(2)]
H = a[0][0] 
W = a[0][1] 
h = a[1][0] 
w = a[1][1] 
my_result = H * W - h * W - H * w + h * w
print(my_result)
N = int(input())
H = list(map(int, input().split()))
 
if N == 1:
    print(0)
    quit()

count = 0
moves = []
for h0, h1 in zip(H,H[1:]):
    if h0 >= h1:
        count += 1
    else:
        moves.append(count)
        count = 0
print(max(moves))


### FIXED CODE ###

def solve(string):
    n, *h = map(int, string.split())
    ans = count = 0
    for h0, h1 in zip(h, h[1:]):
        if h0 >= h1:
            count += 1
        else:
            ans = max(ans, count)
            count = 0
    return str(max(ans, count))


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))
h,w=map(int,input().strip())
print("#"*(w+2))
for _ in range(h):
  print("#"+input().strip()+"#")
print("#"*(w+2))


### FIXED CODE ###

h,w=map(int,input().split())
print("#"*(w+2))
for _ in range(h):
  print("#"+input().strip()+"#")
print("#"*(w+2))
n=int(input())
x=list(map(int,input().split()))
sorted_x=sorted(x)
for i in range(n):
  if x[i]<sorted_x[n//2]:
    print(x[n//2-1])
  else:
    print(x[n//2+1])


### FIXED CODE ###

n=int(input())
x=list(map(int,input().split()))
y=sorted(x)
a=y[n//2-1]
b=y[n//2]
for i in range(n):
  if x[i]<=a:
    print(b)
  else:
    print(a)
a,b = map(int(),input().split())

if a % b ==1:
  print("Odd")
else:
  print("Even")
  
    

### FIXED CODE ###

a,b = map(int,input().split())
 
if a*b % 2 == 1:
    print("Odd")
else:
    print("Even")
N=int(input())
S=[]
for i in range(N):
    S.append(str(input()))

S_set=set(S)

c_max=0
ans=[]
for i in S_set:
    c= S.count(i)
    if c > c_max:
        c_max = c
        ans=[]
        ans.append(i)
    elif c == c_max:
        ans.append(i)

ans=sorted(ans)
for j in ans:
    print(j)
    

### FIXED CODE ###

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

if (a[0] != a[2] and a[1]==a[0] )or (a[0] != a[2] and a[1]==a[2] ):
    
    print('Yes')

else:
    print('No')
r=int(input())
print 3*r*r

### FIXED CODE ###

r=int(input())
print(3*r*r)
import sys
sys.setrecursionlimit(10**7)

class Event:
    def __repr__(self):
            return str(self.__dict__)

class User:
    def __repr__(self):
            return str(self.__dict__)

def solve():
    n, q = map(int, input().split())
    l_event = []
    for i in range(n):
        s, t, x = map(int, input().split())

        # 追加イベント
        e = Event()
        e.time = s-x
        e.type = 1 # add
        e.pos = x
        l_event.append(e)

        # 削除イベント
        e = Event()
        e.time = t-x
        e.type = -1 # delete
        e.pos = x
        l_event.append(e)

    l_user = []
    for i in range(q):
        d = int(input())

        # ユーザ評価イベント
        u = User()
        u.time = d + 0.5 # ユーザが出発する時刻までのイベントを先に処理したいので、0.5ずらす
        u.idx = i
        l_user.append(u)

    # リストを時刻でソート O(NlogN)
    l_event = sorted(l_event, key=lambda e: e.time)

    # ユーザも時刻でソート O(QlogQ)
    l_user = sorted(l_user, key=lambda e: e.time)

    ans = [-1]*q # 答えの配列
    s_stop = set()
    minstop = 10**9 + 1

    current_user_idx = 0

    # リストを順に処理する 全体 O(N + Qlog(2N))
    for e in l_event: # 中身が O(1) なら O(N)


        # 次処理するイベントの時刻より前のユーザをすべて処理する
        while(True): # この while 文は最大Q回しか回らないので、全体 O(Qlog(2N))
            u = l_user[current_user_idx]
            if u.time < e.time:
                if len(s_stop) != 0:
                    if minstop == -1 or minstop == 10**9 + 1:
                        minstop = min(s_stop) # O(log(2N))
                    ans[u.idx] = minstop

                current_user_idx += 1 # 次のユーザへ
                if current_user_idx >= len(l_user):  # 人の処理が終わっている場合、終わり
                    break
            else:
                break

        if e.type == 1: # add
            s_stop.add(e.pos)
            if minstop > e.pos:
                e.pos = minstop # update minstop in advance

        else: # delete
            s_stop.remove(e.pos)
            if minstop == e.pos:
                minstop = -1 # unknown

    print("\n".join([str(a) for a in ans]))

solve()

### FIXED CODE ###

import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop

print('\n'.join(map(str, ans)))
K, N = map(int, input().split())
A = list(map(int, input().split()))

A.remove(0)
A.append(A[0])

max_distance = 0
pre = 0

for i in A:

    if abs(i - pre) > max_distance:
        max_distance = abs(i - pre)
    pre = i



print (K - max_distance)

### FIXED CODE ###


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

diff = K + A[0] - A[-1]

for i in range(N-1):
    diff = max(diff , A[i+1]-A[i])

print(K-diff)
# 解説 https://betrue12.hateblo.jp/entry/2019/03/17/011847

from collections import defaultdict

mod = 10 ** 9 + 7

N = int(input())
C = [int(input()) for _ in range(N)]
L = [-1] * (N + 10)  # 出たところ
dp = [-1] * (N + 10)
dp[0] = 1

for i in range(N):
    if L[C[i]] == -1:
        dp[i + 1] = dp[i]
    elif C[i] == C[i - 1]:
        dp[i + 1] = dp[i]
    else:
        dp[i + 1] = dp[i] + dp[L[C[i]]]
    
    dp[i + 1] %= mod
    L[C[i]] = i + 1

print(dp[N])


### FIXED CODE ###

# 解説 https://betrue12.hateblo.jp/entry/2019/03/17/011847
# from collections import defaultdict

mod = 10 ** 9 + 7

N = int(input())
C = [int(input()) for _ in range(N)]
# L = [-1] * (N + 10)  # 出たところ
# dp = [-1] * (N + 10)
# dp[0] = 1
L  = [-1] * (2*10**5 + 10)
dp = [-1] * (2*10**5 + 10)
dp[0] = 1
 

for i in range(N):
    if L[C[i]] == -1:
        dp[i + 1] = dp[i]
    elif C[i] == C[i - 1]:
        dp[i + 1] = dp[i]
    else:
        dp[i + 1] = dp[i] + dp[L[C[i]]]
    
    dp[i + 1] %= mod
    L[C[i]] = i + 1

print(dp[N])