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

from collections import Counter

N, X, Y = map(int, input().split())
g = [[float("inf")] * N for _ in range(N)]

for i in range(1, N+1):
    for j in range(1, N+1):
        g[i-1][j-1] = min([abs(j-i), abs(X-i)+1+abs(Y-j), abs(Y-i)+1+abs(X-j)])

c = Counter()
for i in range(N):
    c.update(g[i][:i])

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

### FIXED CODE ###

from collections import Counter

N, X, Y = map(int, input().split())
g = [[float("inf")] * N for _ in range(N)]

for i in range(1, N+1):
    for j in range(1, N+1):
        g[i-1][j-1] = min([abs(j-i), abs(X-i)+1+abs(Y-j), abs(Y-i)+1+abs(X-j)])

c = Counter()
for i in range(N):
    c.update(g[i][:i])

for i in range(1, N):
    print(c[i])
### BUGGY CODE ###

import networkx as nx
room, route_count = map(int,input().split())
route = [list(map(int,input().split())) for _ in range(route_count)]

G = nx.Graph()
G.add_nodes_from(range(1,room+1))
G.add_edges_from(route)
shortest_path_dict = nx.single_target_shortest_path(G, target=1)

print('Yes')
for i in range(2,room+1):
  print(shortest_path_dict[i][1])


### FIXED CODE ###

import networkx as nx
room, route_count = map(int,input().split())
route = [list(map(int,input().split())) for _ in range(route_count)]

G = nx.Graph()
G.add_nodes_from(range(1,room+1))
G.add_edges_from(route)
pre = nx.predecessor(G, 1)

print('Yes')
for i in range(2,room+1):
  print(pre[i][0])
### BUGGY CODE ###

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

dp = [0]*(n+1)
dp[0] = 1
if 1 not in a:
  dp[1] = 1

for i in range(2,n+1):
  if i in a:
    continue

  dp[i] += dp[i-1] + dp[i-2]
  dp[i] = dp[i] % 1000000007
print(dp[n])

### FIXED CODE ###

n,m=map(int,input().split())
a=set()
for i in range(m):
  a.add(int(input()))

dp = [0]*(n+1)
dp[0] = 1
if 1 not in a:
  dp[1] = 1

for i in range(2,n+1):
  if i in a:
    continue

  dp[i] += dp[i-1] + dp[i-2]
  dp[i] = dp[i] % 1000000007
print(dp[n])
### BUGGY CODE ###

n = int(input())
ss = []
cnt = 0

for _ in range(n):
    ss.append(input())

for i, s1 in enumerate(ss[0:n-2+1]):
    for s2 in ss[i + 1:n-1+1]:
        # print(s1, s2)
        if sorted(s1) == sorted(s2):
            cnt += 1

print(cnt)

### FIXED CODE ###

n = int(input())
ss = []
cnt = 0

# for _ in range(n):
#     ss.append(input())

# for i, s1 in enumerate(ss[0:n-2+1]):
#     for s2 in ss[i + 1:n-1+1]:
#         # print(s1, s2)
#         if sorted(s1) == sorted(s2):
#             cnt += 1

for _ in range(n):
    ss.append(input())

map = {}
for s in ss:
    sorted_s = ''.join(sorted(s))
    if sorted_s in map.keys():
        map[sorted_s] += 1
    else:
        map[sorted_s] = 1


# map = {'a': 1, 'b': 2, 'c': 3, 'd': 4}
# map = {'a': 10 ** 5}  # maxテスト
# print(map)

# あとはxC2の組み合わせの総数を求めれば良い


for n in map.values():
    if n > 1:
        # cnt += factorial(n) // (2 * factorial(n-2))
        cnt += (n * (n - 1)) // 2
    # print(n)
    # print(cnt)

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

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

c = 0
ans = 0

if N < 1000001:
  for i in range(1,N+1):
    c = int(A*i/B) - A*int(i/B)
    if ans < c:
      ans = c

elif N < B:
  ans = int(A*N/B) - A*int(N/B)
      
else:
  count = B-1
  while N > count:
    c = int(A*count/B) - A*int(count/B)
    if ans < c:
      ans = c
    count += B
    
print(int(ans))

### FIXED CODE ###

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

c = 0
ans = 0

if N < 1000001:
  for i in range(1,N+1):
    c = int(A*i/B) - A*int(i/B)
    if ans < c:
      ans = c

elif N < B:
  ans = int(A*N/B) - A*int(N/B)
      
else:
  count = B-1
  for i in range(10000):
    c = int(A*count/B) - A*int(count/B)
    if ans < c:
      ans = c
    count += B
    
print(int(ans))
### BUGGY CODE ###

def solve(pos):
    start = pos
    ans = 0
    a = 0
    b = N - 1
    for i in range(N-1):
        if a==start:
            a += 1
        elif b==start:
            b -= 1
        if abs(A[a]-A[pos])>=abs(A[b]-A[pos]):
            ans += abs(A[a]-A[pos])
            pos = a
            a += 1
        else:
            ans += abs(A[b]-A[pos])
            pos = b
            b -= 1
        #print(ans, a, b)
    #print(ans)
    return ans

N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
A.sort()

if N<=10000:
    pos_list = list(range(N))
else:
    M = (A[0] + A[-1])/2
    for i in range(N-1):
        if A[i]<=M and M<A[i+1]:
            break
    a = max(0, i - 50)
    b = min(N - 1, i + 50)
    pos_list = list(range(a, b+1))
    if pos_list[0]!=0:
        pos_list = [0] + pos_list
    if pos_list[-1]!= N - 1:
        pos_list.append(N-1)
#print(pos_list)

ans = 0
for pos in pos_list:
    tmp = solve(pos)
    ans = max(ans, tmp)
print(ans)


### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
A.sort()

PLUS = A[int((N+1)//2):]
MINUS = A[:int((N+1)//2)]
#print(PLUS, MINUS)
ans = sum(PLUS)*2 - sum(MINUS)*2
if N%2==0:
    ans += MINUS[-1] - PLUS[0]
else:
    ans += sum(MINUS[-2:])

PLUS = A[int(N//2):]
MINUS = A[:int(N//2)]
#print(PLUS, MINUS)
ans2 = sum(PLUS)*2 - sum(MINUS)*2
if N%2==0:
    ans2 += MINUS[-1] - PLUS[0]
else:
    ans2 -= sum(PLUS[:2])

print(max(ans, ans2))
### BUGGY CODE ###

x,k,d=map(int,input().split())
for _ in range(k):
    pos=abs(x-d)
    neg=abs(x+d)
    if pos<neg:
        x=x-d
    else:
        x=x+d
print(abs(x))

### FIXED CODE ###

x,k,d=map(int,input().split())
x=abs(x)
if x>k*d:
    print(x-k*d)
else:
    if (k-x//d)%2==0:
        print(x-d*(x//d))
    else:
 
        print(abs(d-(x-d*(x//d))))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
S = input()
s=S
ans=0
while True:
    s=s.replace('10','')
    s=s.replace('01','')

    cnt10=s.count('10')
    cnt01=s.count('01')
       
    if cnt10==0 and cnt01==0:
        break
print(len(S)-len(s))

### FIXED CODE ###

# -*- coding: utf-8 -*-
s = input()
print(len(s)-abs(s.count('0')-s.count('1')))
### BUGGY CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
 
pos = 0
saidai = 0
for i in range(N-K+1):
  temp = sum(p[i:i+K])
  if saidai < temp:
    saidai = temp
    pos = i
    
kitaichi = 0
for i in range(K):
  temp = (p[pos+i]+1)*p[pos+i]/2
  kitaichi = kitaichi + float(temp/p[pos+i])
  
print('{:.12f}'.format(kitaichi))

### FIXED CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
 
now = sum(p[:K])
saidai = now
for i in range(K, N):
  now -= p[i-K]
  now += p[i]
  if now > saidai:
    saidai = now
 
print('{:.12f}'.format((saidai + K)/2))
### BUGGY CODE ###

def main():
    mod = 10**9+7
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    pow2 = [1]
    for i in range(200000):
        pow2.append(pow2[-1]*2 % mod)

    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]
    root = 0
    d = [-1]*n
    d[root] = 0
    q = [root]
    cnt = 0
    while q:
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq

    for i in range(n):
        di = d[i]
        remove_list = []
        for j in g[i]:
            if di > d[j]:
                remove_list.append(j)
        for j in remove_list:
            g[i].remove(j)
    dd = sorted([(j, i) for i, j in enumerate(d)])[::-1]
    dd = [j for i, j in dd]

    dp = [(0, 0, 1) for _ in [0]*n]
    for i in dd:
        if g:
            n = 1
            for j in g[i]:
                n += dp[j][2]
            x, y = pow(2, n-1, mod)-1, 0
            for j in g[i]:
                xj, yj, nj = dp[j]
                x += xj*pow2[n-nj]+yj * \
                    (pow2[n-nj]-1)-pow2[nj]+1
                y += yj+pow2[nj]-1
            dp[i] = (x % mod, y % mod, n)

    x = dp[0][0]
    y = pow(2, dp[0][2], mod)
    print(x*pow(y, mod-2, mod) % mod)


main()


### FIXED CODE ###

def main():
    from sys import stdin
    input = stdin.readline
    mod = 10**9+7
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    pow2 = [1]
    for i in range(200000):
        pow2.append(pow2[-1]*2 % mod)

    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]
    root = 0
    d = [-1]*n
    d[root] = 0
    q = [root]
    cnt = 0
    while q:
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq

    for i in range(n):
        di = d[i]
        remove_list = []
        for j in g[i]:
            if di > d[j]:
                remove_list.append(j)
        for j in remove_list:
            g[i].remove(j)
    dd = sorted([(j, i) for i, j in enumerate(d)])[::-1]
    dd = [j for i, j in dd]

    dp = [(0, 0, 1) for _ in [0]*n]
    for i in dd:
        if g:
            n = 1
            for j in g[i]:
                if j != i:
                    n += dp[j][2]
            x, y = pow(2, n-1, mod)-1, 0
            for j in g[i]:
                if j != i:
                    xj, yj, nj = dp[j]
                    p1, p2 = pow2[n-nj], pow2[nj]
                    x += xj*p1+yj*(p1-1)-p2+1
                    y += yj+p2-1
            dp[i] = (x % mod, y % mod, n)

    x = dp[0][0]
    y = pow(2, dp[0][2], mod)
    print(x*pow(y, mod-2, mod) % mod)


main()
### BUGGY CODE ###

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

if 1 in a:
    ans = 1
    while ans in a:
        a = a[a.index(ans):]
        ans += 1
    print(N - ans + 1)
else:
    print(-1)

### FIXED CODE ###

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

if 1 in a:
    ans = 1
    for i in range(N):
        if a[i] == ans:
            ans += 1
    print(N - ans + 1)
else:
    print(-1)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in a[:n-1]:
    for j in a[a.index(i)+1:]:
        ans += (i*j)%(10**9+7)
print(ans%(10**9+7))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
r = sum(a)
for i in a[:n-1]:
    r = r - i
    ans = (ans+i*r)%(10**9+7)
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
l=[0]*N
for i in range(M):
    L,R=map(int,input().split())
    for j in range(L,R+1):
        l[j-1]+=1

print(l.count(M))

### FIXED CODE ###

N,M=map(int,input().split())
l=0
r=0

for i in range(M):
    L,R=map(int,input().split())
    if l<L:
        l=L
    if r==0:
        r=R
    else:
        if r>R:
            r=R
if r>=l:
    print(r-l+1)
else:
    print(0)
### BUGGY CODE ###

import sys
def solve(S):
    dp = [0] * 2019
    ans = 0
    for c in S:
        dp2 = [0] * 2019
        dp2[c] = 1
        for i in range(2019):
            if dp[i] == 0: continue
            dp2[(i*10+c)%2019] += dp[i]
        dp = dp2
        ans += dp[0]
    return ans
S = [x-ord('0') for x in sys.stdin.buffer.read().rstrip()]
print(solve(S))

### FIXED CODE ###

S = input()
r = 1
arr = [0]
for c in S[::-1]:
    arr.append((arr[-1] + int(c) * r) % 2019)
    r *= 10
    r %= 2019
from collections import Counter
ctr = Counter(arr)
ans = 0
for v in ctr.values():
    ans += v*(v-1)//2
print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    a = [int(v) for v in input().split()]
    for j in range(n):
        x = 0
        for i in range(0, j):
            x ^= a[i]
        for i in range(j+1, n):
            x ^= a[i]
        print(x)

main()

### FIXED CODE ###

def main():
    n = int(input())
    a = [int(v) for v in input().split()]
    x = 0
    for i in range(n):
        x ^= a[i]
    for i in range(n):
        print(x ^ a[i])

main()
### BUGGY CODE ###

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

b=0
r=0
while b+r<N:
    for i in range(A):
        b+=1
        if b+r==N:
            break
    for j in range(B):
        r+=1
        if b+r==N:
            break
print(b)

### FIXED CODE ###

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

C=A+B
d=N//C
N -= C*d

b=0
r=0
while N>0:
    N-=A
    b+=A
    if N<=0:
        b+=N
        break

    N-=B
    r+=B
    if N<=0:
        break

print(b+d*A)
### BUGGY CODE ###

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

d_max = 0
for i in range(n-k+1):
  d_max = max(d_max,sum(p[i:k+i]))

ans = (d_max + k)/2
print(ans)

### FIXED CODE ###

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

d_tmp = sum(p[0:k])
d_max = sum(p[0:k])
for i in range(n-k):
  d_tmp = d_tmp + p[k+i] - p[i]
  d_max = max(d_max,d_tmp)

ans = (d_max + k)/2
print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]


for i in range(n):
  l = list(a)
  del l[i] 
  print(max(l))

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

b = list(a)
a.sort()

for i in range(n):
  if b[i] == a[n - 1]:
    print(a[n - 2])
  else:
    print(a[n - 1])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
ans = 0
for i in range(n):
    ans += a[i] * sum(a[(i + 1):])
print(ans % mod)


### FIXED CODE ###

mod = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
dp = [0]

def calc(A, n, dp):
    dp += [A[0] * A[1]]
    rsum = A[0] + A[1]
    for i in range(2, n):
        dp += [dp[-1] + rsum * A[i]]
        rsum += A[i]

    i = dp.index(max(dp))
    rsum = 0
    for j in range(i + 1):
        rsum += A[j]
    res = max(dp)
    dp2 = max(dp)
    for j in range(0, i):
        rsum -= A[j]
        dp2 -= A[j] * rsum
        res = max(dp2, res)
    return res

ans = calc(a, n, dp) % mod
print(ans)
### BUGGY CODE ###

s=input()
n=len(s)
rst=[0 for j in range(2019)]
x=0
ans=0
for i in range(n):
    y=(int(s[n-1-i])*(10**i))%2019
    x+=y
    if x>=2019:
        x%=2019
    #print(x,y)
    ans+=rst[x]
    rst[x]+=1
if rst[0]==1:
    ans+=1

print(ans)

### FIXED CODE ###

s=input()
n=len(s)
rst=[0 for j in range(2019)]
rst[0]=1
x=0
ans=0
drst=1
for i in range(n):
    y=(int(s[n-1-i])*drst)%2019
    drst=(drst*10)%2019
    x+=y
    if x>=2019:
        x%=2019
    #print(x,y,drst)
    ans+=rst[x]
    rst[x]+=1
#if rst[0]==1:
    #ans+=0

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

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

cnt = 0
for i in range(q):
    a = [i for i in input().split()]
    if a[0] == '1':
        cnt += 1
    else:
        if (a[1] == '1' and cnt % 2 == 0) or (a[1] == '2' and cnt % 2 == 1):
            s = a[2] + s
        else:
            s = s + a[2]

if cnt % 2 == 0:
    print(s)
else:
    print(''.join(list(reversed(s))))


### FIXED CODE ###

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

cnt = 0
left = []
right = []
for j in range(q):
    a = [str(i) for i in input().split()]
    if a[0] == '1':
        cnt += 1
    else:
        if (a[1] == '1' and cnt % 2 == 0) or (a[1] == '2' and cnt % 2 == 1):
            right.append(a[2])
        else:
            left.append(a[2])

if cnt % 2 == 0:
    print(''.join(reversed(right)) + s + ''.join(left))
else:
    print(''.join(reversed(left)) + ''.join(list(reversed(s))) + ''.join(right))
### BUGGY CODE ###

x, y = map(int, input().split())
i = 0
while True:
    if x > 10**18:
        print(-1)
        quit()
    elif (x * i) % y != 0:
        print(x * i)
        quit()
    i += 1

### FIXED CODE ###

x, y = map(int, input().split())
i = 0
if x % y == 0:
    print(-1)
    quit()
while True:
    if x > 10**18:
        print(-1)
        quit()
    elif (x * i) % y != 0:
        print(x * i)
        quit()
    i += 1
### BUGGY CODE ###

A = list(input())
n = len(A)

count = 0
for i in range(n):
    if A[i] == 'W':
        count += A[:i].count('B')

print(count)


### FIXED CODE ###

A = list(input())

count = 0
ans = 0
for a in A:
    if a == 'B':
        count += 1
    else:
        ans += count

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

n = int(input())
ans = 0
used_s = {}
for _ in range(n):
    s = tuple(sorted(input()))
    if not s in used_s.keys():
        used_s[s] = 0
    else:
        used_s[s] += 1
        ans += 1 * used_s[s]

print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
used_s = {}
for _ in range(n):
    s = "".join(sorted(input()))
    if not s in used_s.keys():
        used_s[s] = 0
    else:
        used_s[s] += 1
        ans += 1 * used_s[s]

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

#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 998244353

#C
def C():
    n = I()
    s = S()
    ans = float("inf")
    for i in range(n+1):
        m = 0
        for j in range(i):
            if s[j] == "#":
                m += 1
        for j in range(i,n):
            if s[j] == ".":
                m += 1
        ans = min(ans,m)
    print(ans)
    return

#D
def D():
    n = I()
    a = IR(n)

    return

#E
def E():
    return

#F
def F():
    return


#Solve
if __name__ == "__main__":
    C()


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 998244353

#C
def C():
    n = I()
    s = S()
    ans = float("inf")
    b = [0 for i in range(n)]
    for i in range(n):
        if s[i] == "#":
            b[i] = 1
    w = [0 for i in range(n)]
    for i in range(n):
        if s[i] == ".":
            w[i] = 1
    b.insert(0,0)
    w.insert(0,0)
    for i in range(n):
        b[i+1] += b[i]
        w[i+1] += w[i]
    for i in range(n+1):
        m = b[i]+w[n]-w[i]
        ans = min(ans,m)
    print(ans)
    return

#D
def D():
    n = I()
    a = IR(n)

    return

#E
def E():
    n = I()

    return

#F
def F():
    return


#Solve
if __name__ == "__main__":
    C()
### BUGGY CODE ###

N = int(input())
ai = list(map(int, input().split()))

box = [0] * N
v = N // 2  # 後半部の最初のindex

for i in range(v, N):
    if ai[i] == 0:
        box[i] = 0
    else:
        box[i] = 1

for i in range(v - 1, -1, -1):
    s = [ai[x] == 1 for x in range(i + 1, N) if (x + 1) % (i + 1) == 0]
    cnt = s.count(True)
    if cnt & 1 == 1:
        box[i] = 0 if ai[i] & 1 == 1 else 1
    else:
        box[i] = 0 if ai[i] & 1 == 0 else 1

print(box.count(1))
for x in box:
    if x == 1:
        print(x)


### FIXED CODE ###

N = int(input())
ai = list(map(int, input().split()))

box = [0] * N
v = N // 2  # 後半部の最初のindex

for i in range(v, N):
    if ai[i] == 0:
        box[i] = 0
    else:
        box[i] = 1

for i in range(v - 1, -1, -1):
    value = i + 1
    sum = 0
    for j in range(value * 2 - 1, N, value):
        sum += box[j]
    if sum & 1 == 1:
        box[i] = 0 if ai[i] & 1 == 1 else 1
    else:
        box[i] = 0 if ai[i] & 1 == 0 else 1
print(box.count(1))
for i in range(N):
    if box[i] == 1:
        print(i + 1)
### BUGGY CODE ###

# 解説AC
N,M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

color = [0] * N

def is_bipartite():
    """ 二部グラフか判定する """
    stack = [(0,1)]
    while stack:
        v, c = stack.pop()
        color[v] = c
        for w in edge[v]:
            if color[w] == c: return False
            if color[w] == 0:
                stack.append((w, (-1) * c))
    return True

if is_bipartite():
    B = color.count(1)
    W = color.count(-1)
    print(B * W - M)
else:
    print(N * (N - 1) // 2 - M)

### FIXED CODE ###

# 解説AC
N,M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

color = [0] * N

def is_bipartite():
    """ 二部グラフか判定する """
    stack = [(0,1)]
    while stack:
        v, c = stack.pop()
        color[v] = c
        for w in edge[v]:
            if color[w] == c: return False
            if color[w] == 0:
                stack.append((w, (-1) * c))
    return True

if is_bipartite():
    B = color.count(1)
    W = N - B
    print(B * W - M)
else:
    print(N * (N - 1) // 2 - M)
### BUGGY CODE ###

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

res = 1

for a in A:
    res *= a

if res > 10 ** 18:
    res = -1

print(res)

### FIXED CODE ###

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

A.sort()


res = 1
for a in A:
    res *= a
    if res > 10 ** 18:
        res = -1
        break

print(res)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
B = [0]
for i in range(N):
    B.append(A[i]+B[i])
ans = 0
for i in range(N):
    for j in range(i+1,N+1):
        if B[j]-B[i]==0:ans+=1
print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
b = 0
c  = Counter([0])
ans = 0
for i in range(N):
    b += A[i]
    ans += c[b]
    c[b] += 1
print(ans)
### BUGGY CODE ###

#https://atcoder.jp/contests/abc154/tasks/abc154_c

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

for i in range(n):
    for j in range(n):
        if j<=i:
            continue
        if a[i]==a[j]:
            print("NO")
            exit()

print("YES")

### FIXED CODE ###

#https://atcoder.jp/contests/abc154/tasks/abc154_c

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

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

print("YES")
### BUGGY CODE ###

import sys
import heapq as hq
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

base = 10 ** 10
sb = [(-b[i], i) for i in range(N) if a[i] != b[i]]
h = []
for t in sb: hq.heappush(h, t)
res = 0
while len(h):
  v, i = hq.heappop(h)
  v = -v
  if v < a[i]:
    print(-1)
    exit(0)
  d = v - a[i]
  x = b[i - 1] + b[(i + 1) % N]
  t = d // x
  if t == 0:
    if v == a[i]: continue
    print(-1)
    exit(0)
  b[i] -= x * (t)
  res += t
  hq.heappush(h, (-b[i], i))
print(res)

### FIXED CODE ###

import sys
from heapq import heappush as hpu
from heapq import heappop as hpo
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

base = 10 ** 6
sb = [-(b[i] * base + i) for i in range(N) if a[i] != b[i]]
h = []
for t in sb: hpu(h, t)
res = 0
while len(h):
  v = hpo(h)
  i = -v % base
  v = -v // base
  if v < a[i]:
    print(-1)
    exit(0)
  d = v - a[i]
  x = b[i - 1] + b[(i + 1) % N]
  t = d // x
  if t == 0:
    if v == a[i]: continue
    print(-1)
    exit(0)
  b[i] -= x * (t)
  res += t
  hpu(h, -(b[i] * base + i))
print(res)