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

from collections import deque
n = int(input())
graph = [[] for _ in range(n)]
edge = []
for i in range(n-1):
    a, b = map(lambda x:int(x)-1, input().split())
    edge.append({a,b})
    graph[a].append(b)
    graph[b].append(a)
k = max(len(i) for i in graph)

que = deque()
seen = [False]*n
ans = [0]*(n-1)
que.append((0, -1))
while len(que)>0:
    node, p_color = que.popleft()
    seen[node] = True
    color = 1
    for i in graph[node]:
        if seen[i]:
            continue
        if color==p_color:
            color += 1
        ans[edge.index({node,i})] = color
        que.append((i, color))
        color += 1
print(k)
[print(i) for i in ans]

### FIXED CODE ###

import sys
n = int(input())
sys.setrecursionlimit(2*n)
graph = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(lambda x:int(x)-1, input().split())
    graph[a].append((b, i))
    graph[b].append((a, i))

def DFS(node, p_node=-1, p_color=-1):
    color = 1
    for c_node, edge in graph[node]:
        if c_node==p_node:
            continue
        if color==p_color:
            color += 1
        ans[edge] = color
        DFS(c_node, node, color)
        color += 1
ans = [0]*(n-1)
DFS(0)
k = max(len(i) for i in graph)
print(k)
[print(i) for i in ans]
### BUGGY CODE ###

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

dp = [0] * (n)
dp[0] = 0
dp[1] = abs(h[1] - h[0])
for i in range(2,n):
    x = max(i-k, 0)
    dp[i] = min([d + abs(h[i]-hd) for d, hd in zip(dp[x:i], h[x:i])])

print(dp[n-1])


### FIXED CODE ###

import sys
import numpy as np
n,k = map(int,input().split())
h = np.array(list(map(int,sys.stdin.readline().split())))

dp = np.zeros(n, dtype=int)
dp[0] = 0
for i in range(1,n):
    x = max(i-k, 0)
    #dp[i] = min(d + abs(h[i]-hd) for d, hd in zip(dp[x:i], h[x:i]))
    dp[i] = (dp[x:i] + abs(h[i] - h[x:i])).min()
print(dp[-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

class Node_Class():
    def __init__(self, c_list):
        self.c_list = c_list

n = int(raw_input())
node_dic = {}
p_list = [0]*n
d_list = [0]*n
t_list = ['']*n
for i in range(n):
    line = map(str, raw_input().split())
    if int(line[1]) > 0:
        node_dic[int(line[0])] = Node_Class(map(int, line[2:]))
    else:
        node_dic[int(line[0])] = Node_Class([])
#parent
for i in range(n):
    flag = False
    for j in range(n):
        if i in node_dic[j].c_list:
            p_list[i] = j
            flag = True
            break
    if not flag:
        p_list[i] = -1
#depth
for i in range(n):
    j = i
    while p_list[j] > -1:
        j = p_list[j]
        d_list[i] += 1
#type
for i in range(n):
    if p_list[i] == -1:
        t_list[i] = t_list[i] + "root"
    else:
        if len(node_dic[i].c_list):
            t_list[i] = t_list[i] + "internal node"
        else:
            t_list[i] = t_list[i] + "leaf"
#print
for i in range(n):
    s = "node %d: parent = %d, depth = %d, %s," %(i, p_list[i], d_list[i], t_list[i])
    print s, node_dic[i].c_list

### FIXED CODE ###

# -*- coding: utf-8 -*-

class Node_Class():
    def __init__(self, c_list):
        self.c_list = c_list

n = int(raw_input())
node_dic = {}
p_list = [0]*n
d_list = [0]*n
t_list = ['']*n
root = 0
for i in range(n):
    root += i
for i in range(n):
    line = map(str, raw_input().split())
    if int(line[1]) > 0:
        node_dic[int(line[0])] = Node_Class(map(int, line[2:]))
    else:
        node_dic[int(line[0])] = Node_Class([])
#parent
for i in range(n):
    for j in node_dic[i].c_list:
        p_list[j] = i
        root -= j
p_list[root] = -1
#depth
for i in range(n):
    j = i
    while p_list[j] > -1:
        j = p_list[j]
        d_list[i] += 1
#type
for i in range(n):
    if p_list[i] == -1:
        t_list[i] = t_list[i] + "root"
    else:
        if len(node_dic[i].c_list):
            t_list[i] = t_list[i] + "internal node"
        else:
            t_list[i] = t_list[i] + "leaf"
#print
for i in range(n):
    s = "node %d: parent = %d, depth = %d, %s," %(i, p_list[i], d_list[i], t_list[i])
    print s, node_dic[i].c_list
### BUGGY CODE ###

#A1 ~ Aiまでの和 O(logN)
def BIT_query(BIT,idx):
    res_sum = 0
    if idx == 0:
        return 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(BIT,idx,x,n):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return

def main():
    N, Q = map( int, input().split())
    C = list( map( int, input().split()))
    LR = [ tuple( map( int, input().split())) for _ in range(Q)]
    LRI = []
    for i, x in enumerate(LR):
        LRI.append((x[1], x[0], i))
    LRI.sort(key=lambda x:x[0])
    lastAppend = [-1]*(N+1)
    BIT = [0]*(N+1)
    ANS = [0]*Q
    now = 1
    for r, l, i in LRI:
        while now <= r:
            c = C[now-1]
            if lastAppend[c] == -1:
                BIT_update(BIT, now, 1,N)
            else:
                BIT_update(BIT, now, 1,N)
                BIT_update(BIT, lastAppend[c],-1,N)
            lastAppend[c] = now                
            now += 1
        ANS[i] = BIT_query(BIT,r) - BIT_query(BIT,l-1)
    print( "\n".join( map( str, ANS)))
    
    

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, Q = map( int, input().split())
    C = list( map( int, input().split()))
    LRI = []
    for i in range(Q):
        l, r = map( int, input().split())
        LRI.append((r,l,i))
    LRI.sort(key=lambda x:x[0])
    lastAppend = [-1]*(N+1)
    BIT = [0]*(N+1)
    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        if idx == 0:
            return 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= N:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    ANS = [0]*Q
    now = 1
    for r, l, i in LRI:
        while now <= r:
            c = C[now-1]
            if lastAppend[c] == -1:
                BIT_update(now, 1)
            else:
                BIT_update( now, 1)
                BIT_update(lastAppend[c],-1)
            lastAppend[c] = now                
            now += 1
        ANS[i] = BIT_query(r) - BIT_query(l-1)
    print( "\n".join( map( str, ANS)))
    
    

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

N = int(input())
d = {}
for i in range(N):
  s = "".join(sorted(input()))
  if s in d.keys():
    d[s] += 1
  else:
    d.setdefault(s, 1)
count = 0
for v in d.values():
  count += (v-1)*v//2
print(count)

### FIXED CODE ###

N = int(input())
d = {}
for i in range(N):
  s = "".join(sorted(input()))
  if s in d.keys():
    d[s] += 1
  else:
    d.setdefault(s, 1)
count = 0
for v in d.values():
  count += (v-1)*v//2
print(count)
### BUGGY CODE ###

from sys import stdin
readline = stdin.readline

R, C, K = map(int, readline().split())

goods = [[0] * C for _ in range(R)]
for _ in range(K):
    r, c, v = map(int, readline().split())
    goods[r - 1][c - 1] = v

dp = [[[0] * 4 for _ in range(C + 1)] for _ in range(R + 1)]
for i in range(R):
    for j in range(C):
        if goods[i][j] != 0:
            for k in range(2, -1, -1):
                if dp[i][j][k] + goods[i][j] > dp[i][j][k + 1]:
                    dp[i][j][k + 1] = dp[i][j][k] + goods[i][j]
        for k in range(4):
            if dp[i][j][k] > dp[i][j + 1][k]:
                dp[i][j + 1][k] = dp[i][j][k]
            if dp[i][j][k] > dp[i + 1][j][0]:
                dp[i + 1][j][0] = dp[i][j][k]

print(max(dp[R - 1][C - 1]))


### FIXED CODE ###

from sys import stdin
readline = stdin.readline

R, C, K = map(int, readline().split())

goods = [[0] * C for _ in range(R)]
for _ in range(K):
    r, c, v = map(int, readline().split())
    goods[r - 1][c - 1] = v

n = [0] * (C + 1)
for i in range(R):
    c = [0] * 4
    c[0] = n[0]
    for j in range(C):
        if goods[i][j] != 0:
            for k in range(2, -1, -1):
                if c[k] + goods[i][j] > c[k + 1]:
                    c[k + 1] = c[k] + goods[i][j]
        for k in range(4):
            if c[k] > n[j]:
                n[j] = c[k]
        if n[j + 1] > c[0]:
            c[0] = n[j + 1]

print(max(c))
### BUGGY CODE ###

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
 
totalA = [0]
totalB = [0]
sumA = 0
for i in range(N):
    sumA += A[i]
    totalA.append(sumA)
sumB = 0
for i in range(M):
    sumB += B[i]
    totalB.append(sumB)

iA = N
iB = 0
countMax = 0
while iA >= 0:
    if totalA[iA] + totalB[iB] > K:
        iA -= 1
    else:
        while totalA[iA] + totalB[iB] <= K:
          countMax = max(countMax,iA+iB)
          if iB == M:
            break
          iB += 1
    if iA == N and iB == M:
      break
          
print(countMax)
 

### FIXED CODE ###

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

totalA = [0]
totalB = [0]
sumA = 0
for i in range(N):
    sumA += A[i]
    totalA.append(sumA)
sumB = 0
for i in range(M):
    sumB += B[i]
    totalB.append(sumB)

iB = M
countMax = 0
for iA in range(N+1):
  if totalA[iA]>K:
    break
  else:
    while totalA[iA] + totalB[iB] > K:
      iB -= 1
  countMax = max(countMax,iA+iB)

print(countMax)
### BUGGY CODE ###

s = raw_input()

n = len(s)
K = 0
s_i1=""
size=1

while len(s.strip(s[0]))>0 or len(s)>2:
    s_i=s[0:size]

    if s_i1 == s_i:
        size = size + 1
    else:
        s_i1=s_i
        s = s[size:]
        size = 1
        K = K + 1

print K+1


### FIXED CODE ###

s = raw_input()

n = len(s)
K = 0
s_i1=""
size=1

#while len(s.strip(s[0]))>0 or len(s)>2:
while len(s)>2:
    s_i=s[0:size]

    if s_i1 == s_i:
        size = size + 1
    else:
        s_i1=s_i
        s = s[size:]
        size = 1
        K = K + 1
if not s_i1==s[0]:
    if len(s.strip(s[0]))>0:
        K=K+1
K=K+1
print K
### BUGGY CODE ###

from collections import deque

queue = deque()

H,W = [int(v) for v in input().split()]
ch,cw = [int(v) for v in input().split()]
dh,dw = [int(v) for v in input().split()]

S = [input() for _ in range(H)]
visited = [[-1 for _ in range (W)] for _ in range(H)]

queue.append((cw-1,ch-1,0))

def check(x,y):
    return x > -1 and x < W and y > -1 and y < H and S[y][x] != "#" and visited[y][x] == -1

while len(queue) != 0:
    x,y,c = queue.popleft()
    if visited[y][x] != -1:
        continue
    visited[y][x] = c

    for d in [1,-1]:
        if check(x+d,y):
            queue.appendleft([x+d,y,c])
        if check(x,y+d):
            queue.appendleft([x,y+d,c])
    
    for dx in [-2,-1,0,1,2]:
        for dy in [-2,-1,0,1,2]:
            if check(x+dx,y+dy):
                queue.append((x+dx,y+dy,c+1))

print(visited[dh-1][dw-1])


### FIXED CODE ###

from collections import deque

queue = deque()

H,W = [int(v) for v in input().split()]
ch,cw = [int(v) for v in input().split()]
dh,dw = [int(v) for v in input().split()]

S = [input() for _ in range(H)]
visited = [[-1 for _ in range (W)] for _ in range(H)]

queue.append((cw-1,ch-1,0))

def check(x,y):
    return x > -1 and x < W and y > -1 and y < H and S[y][x] != "#" and visited[y][x] == -1

while len(queue) != 0:
    x,y,c = queue.popleft()
    if visited[y][x] != -1:
        continue
    visited[y][x] = c

    for d in [1,-1]:
        if check(x+d,y):
            queue.appendleft([x+d,y,c])
        if check(x,y+d):
            queue.appendleft([x,y+d,c])
    
    for dx in [-2,-1,0,1,2]:
        for dy in [-2,-1,0,1,2]:
            if check(x+dx,y+dy):
                queue.append((x+dx,y+dy,c+1))

print(visited[dh-1][dw-1])
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def LIST(): return list(map(int, input().split()))
mod = 10 ** 9 + 7

#0埋め　桁合わせ
def digit(n, r):
    n = str(n)
    l = len(n)
    n = '0' * (r - l) + n
    return n

n = INT()
a = LIST()
arr = [0 for _ in range(61)]
arr2 = [0 for _ in range(61)]
for i in range(1, n + 1):
    bn = digit(bin(a[i - 1])[2:], 61)
    for j in range(61):
        arr[j] += int(bn[j])
for i in range(61):
    arr2[i] = n - arr[i]
    if arr2[i] == n:
        arr2[i] = 0
ans = 0
for i in range(61):
    ans *= 2
    ans += arr[i] * arr2[i]
    ans %= mod
print(ans)


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def LIST(): return list(map(int, input().split()))
mod = 10 ** 9 + 7

n = INT()
a = LIST()
arr = [0 for _ in range(61)]
for i in range(n):
    ai = a[i]
    for j in reversed(range(61)):
        arr[j] += ai % 2
        ai //= 2
ans = 0
for i in range(61):
    ans *= 2
    arri = arr[i]
    ans += arri * (n - arri if arri != 0 else 0)
    ans %= mod
print(ans)
### BUGGY CODE ###

H, W = map(int, input().split())
a = [input() for i in range(H)]

# 黒マスの位置を記録
stack = []
black_map = [[ a[i][j] == "#" for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if a[i][j] == "#":
            stack.append([i, j])

cnt = 0
while True:
    _stack = []
    for pos in stack:
        for i in [[-1,0], [1, 0], [0, -1], [0, 1]]:
            _x = pos[0] + i[0]
            _y = pos[1] + i[1]
            if 0 <= _x <= H-1 and 0 <= _y <= W-1 and not black_map[_x][_y]:
                _stack.append([_x, _y])
                black_map[_x][_y] = True
    if len(_stack) > 0:
        stack = _stack[::]
    else:
        break
    cnt += 1
print(cnt)

### FIXED CODE ###

from collections import deque
h,w = list(map(int,input().split()))
f = []
q = deque()
for i in range(h):
    a = list(input())
    for j in range(w):
        if a[j] == '#':
            q.append([0,i,j])
    f.append(a)
 
ans =0
dxy = [0,1,0,-1,0]
while(len(q)):
    c,y,x = q.popleft()
    for i in range(4):
        ny = y+dxy[i]
        nx = x+dxy[i+1]
        if nx >= w or ny >= h or nx <0 or ny <0:
            continue
        if f[ny][nx] == '.':
            f[ny][nx] = c+1
            q.append([c+1,ny,nx])
            ans = max(ans,c+1)
        elif f[ny][nx] != '#' and f[ny][nx] > c+1:
            f[ny][nx] = c+1
            q.append([c+1,ny,nx])
            ans = max(ans,c+1)
 
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 2)
 
    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


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

rli = []
for i in range(q):
    l, r = map(int, input().split())
    rli.append((r, l, i))
rli.sort()

last = [-1] * (n + 1)

bit = Bit(n)
ans = [0] * q
cur = 1
for r, l, i in rli:
    for j in range(cur, r + 1):
        if last[c[j - 1]] != -1:
            bit.add(last[c[j - 1]], -1)
        last[c[j - 1]] = j
        bit.add(j, 1)
    cur = r + 1
    ans[i] = bit.sum(r) - bit.sum(l - 1)
print(*ans, sep="\n")


### FIXED CODE ###

import sys
input = sys.stdin.readline


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0 for _ in range(n + 2)]
 
    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


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

rli = []
for i in range(q):
    l, r = map(int, input().split())
    rli.append((r, l, i))
rli.sort(key=lambda x: x[0])

last = [-1 for _ in range(n + 1)]

bit = Bit(n)
ans = [-1 for _ in range(q)]
cur = 1
for r, l, i in rli:
    for j in range(cur, r + 1):
        if last[c[j - 1]] != -1:
            bit.add(last[c[j - 1]], -1)
        last[c[j - 1]] = j
        bit.add(j, 1)
    cur = r + 1
    ans[i] = bit.sum(r) - bit.sum(l - 1)
print(*ans, sep="\n")
### BUGGY CODE ###

def solve(a, b):
    pdp = {a[0]:0}
    ndp = {}
    for ai in a[1:] + [0]:
        for k, v in pdp.items():
            for bi in b:
                vb = v + st(k, bi)
                kb = k & (65535 ^ bi) | ai
                try:
                    ndp[kb] = max(ndp[kb], vb)
                except KeyError:
                    ndp[kb] = vb
        pdp, ndp = ndp, {}
        
    return max(pdp.values())

def memoize(f):
    cache = {}
    def helper(x, y):
        if (x, y) not in cache:
            cache[(x, y)] = f(x, y)
        return cache[(x, y)]
    return helper

@memoize
def st(i, j):
    return bin(i).count('1') - bin(i & (65535 ^ j)).count('1')



import sys
f = sys.stdin

while True:
    n, c = map(int, f.readline().split())
    if n == c == 0:
        break
    a = [int(''.join(f.readline().split()), 2) for i in range(n)]
    b = [int(''.join(f.readline().split()), 2) for i in range(c)]
    print(solve(a, b))

### FIXED CODE ###

bitcount = [bin(i).count('1') for i in range(0x10000)]
def solve(a, b):
    global bitcount
    b = [65535 ^ bi for bi in b]
    pdp = {a[0]:0}
    ndp = {}
    for ai in a[1:] + [0]:
        for k, v in pdp.items():
            v += bitcount[k]
            for bi in b:
                bi &= k
                vb = v - bitcount[bi]
                bi |= ai
                try:
                    if ndp[bi] < vb:
                        ndp[bi] = vb
                except KeyError:
                    ndp[bi] = vb
        pdp, ndp = ndp, {}
        
    return max(pdp.values())

import sys
f = sys.stdin


while True:
    n, c = map(int, f.readline().split())
    if n == c == 0:
        break
    a = [int(''.join(f.readline().split()), 2) for i in range(n)]
    b = [int(''.join(f.readline().split()), 2) for i in range(c)]
    print(solve(a, b))
### BUGGY CODE ###

from itertools import permutations
n,m,r = map(int,input().split())
rl = list(map(int,input().split()))
d = [[10**8]*n for i in range(n)]
for i in range(m):
  a,b,c = map(int,input().split())
  d[a-1][b-1] = d[b-1][a-1] = c
for i in range(n):
  for j in range(n):
    for k in range(n):
      d[i][j] = min(d[i][j],d[i][k]+d[k][j])
m = 10**9
for i in permutations(rl):
  c = 0
  for j in range(1,r):
    c += d[i[j-1]-1][i[j]-1]
  m = min(m,c)
print(m)

### FIXED CODE ###

from itertools import permutations
n,m,r = map(int,input().split())
rl = list(map(int,input().split()))
d = [[10**8]*n for i in range(n)]
for i in range(m):
  a,b,c = map(int,input().split())
  d[a-1][b-1] = d[b-1][a-1] = c
for k in range(n):
  for i in range(n):
    for j in range(n):
      d[i][j] = min(d[i][j],d[i][k]+d[k][j])
m = 10**9
for i in permutations(rl):
  c = 0
  for j in range(1,r):
    c += d[i[j-1]-1][i[j]-1]
  m = min(m,c)
print(m)
### BUGGY CODE ###

N = int(input())
nums = [int(i) for i in input().split()]
from fractions import gcd
from functools import reduce
def compute_gcd(numbers):
    return reduce(gcd, numbers)
from copy import copy
gcds = []
for i in range(len(nums)):
    n = copy(nums)
    n.pop(i)
    gcds.append(compute_gcd(n))
print(max(gcds))

### FIXED CODE ###

N = int(input())
nums = [int(i) for i in input().split()]
nums_sorted = sorted(list((set(nums))), reverse=True)
def compute_divs(n):
    divs = []
    if n == 1: return [1]
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            divs.append(i)
            if i != n // i:
                divs.append(n//i)
    divs.append(n)
    return divs
ans = 1
if len(nums_sorted) == 1: ans = nums[0]
else:
    divs1 = compute_divs(nums_sorted[0])
    divs2 = compute_divs(nums_sorted[1])
    divs = sorted(list(set(divs1+divs2)))
    for i in reversed(divs):
        c= 0
        for j in nums:
            if j % i != 0:
                c += 1
                if c == 2:
                    break
        if c <= 1:
            ans = i
            break
print(ans)
### BUGGY CODE ###

import math
K = int(input())
def gcd(a,b,c) :
  x = math.gcd(a,b)
  return math.gcd(x,c)
count = 0
for i in range(K):
  for j in range(K):
    for k in range(K):
      count += gcd(i+1,j+1,k+1)
      
print(count)

### FIXED CODE ###

import math
K = int(input())
count = 0
for i in range(K):
  for j in range(K):
    x = math.gcd(i+1,j+1)
    for k in range(K):
      count += math.gcd(x,k+1)    
print(count)
### BUGGY CODE ###

from numpy import*;B=searchsorted;a,b=loadtxt(open(0),skiprows=1);c=0;h=1
while h<2**29:l=h;h*=2;y=sort(hstack((b%h-h,b%h)));c+=sum(B(y,h-a%h)-B(y,l-a%h))%2*l
print(c)

### FIXED CODE ###

from numpy import*;B,I=searchsorted,lambda:int32(input().split());input();a,b=I(),I();c=0
for k in range(29):l=2**k;h=l*2;x,y=a%h,sort(b%h);y=hstack((y-h,y));c+=sum(B(y,h-x)-B(y,l-x))%2*l
print(c)
### BUGGY CODE ###

import math
N = int(input())
n = int(math.sqrt(N))

while n < N:
    if (N/n).is_integer() == True:
        print(int(N/n + n - 2))
        break
    else:
        n += 1

### FIXED CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

import math
import bisect
N = int(input())
N_list = sorted(make_divisors(N))
p = bisect.bisect_left(N_list, math.sqrt(N))
n = N_list[p]
print(int(N/n + n - 2))
### BUGGY CODE ###

n=int(input())
a=[int(x) for x in input().split()]

def func1():
    cnt=0
    a.sort()
    chker={}
    for i in a:
        candiv=False
        if a.count(i)>1:
            candiv=True
        else:
            for j2 in chker:
                j=int(j2)
                if i%j==0:
                    candiv=True
                    break
        if candiv==False:
            cnt+=1
        chker[str(i)]=1
    print(cnt)
func1()


### FIXED CODE ###

n=int(input())
a=[int(x) for x in input().split()]
a.sort()
max=a[-1]
dp=[False for _ in range(max+1)]

for i in a:
    if dp[i]==False:
        j=1
        while 1:
            j+=1
            if i*j>max:
                break
            dp[i*j]=True
for i in range(len(a)-1):
    if a[i]==a[i+1]:
        dp[a[i]]=True
cnt=0
for i in a:
    if dp[i]==False:
        cnt+=1

print(cnt)
### BUGGY CODE ###

n=int(input())
ct=0
p=list(map(int,input().split()))
for i in range(n):
    list1=sorted(p[0:i+1])
    if list1[0]==p[i]:
        ct+=1
print(ct)

### FIXED CODE ###

n=int(input())
ct=0
p=list(map(int,input().split()))
mn=p[0]
for i in range(1,n):
    if mn>=p[i]:
        ct+=1
        mn=p[i]
print(ct+1)
### BUGGY CODE ###

def main():
    N, *a = map(int, open(0).read().split())
    print(min(abs(2 * sum(a[:i]) - sum(a)) for i in range(1, N)))
    return


main()


### FIXED CODE ###

INF = float('inf')


def main():
    N, *a = map(int, open(0).read().split())
    ans = INF
    tmp = 0
    total = sum(a)
    for i in range(N - 1):
        tmp += a[i]
        ans = min(ans, abs(2 * tmp - total))
    print(ans)
    return


main()
### BUGGY CODE ###

s = [input()]
q = int(input())
forward = True
for _ in range(q):
    que = list(input().split())
    if int(que[0]) == 1:
        if forward:
            forward = False
        else:
            forward = True
    else:
        if (int(que[1]) == 1 and forward) or (int(que[1]) == 2 and not forward):
            s = [que[2]] + s
        else:
            s.append(que[2])
if forward:
    print("".join(s))
else:
    ss = "".join(s)
    ans = ""
    for i in reversed(range(len(ss))):
        ans += ss[i]
    print(ans)

### FIXED CODE ###

from collections import deque
s = input()
q = int(input())
f = ""
b = ""
forward = True
for _ in range(q):
    que = list(input().split())
    if int(que[0]) == 1:
        if forward:
            forward = False
        else:
            forward = True
    else:
        if (int(que[1]) == 1 and forward) or (int(que[1]) == 2 and not forward):
            f+=que[2]
        else:
            b+=que[2]

if forward:
    print(f[::-1]+s+b)
else:

    print(b[::-1]+s[::-1]+f)