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

from collections import defaultdict

N = int(input())
S = input()

S1 = S[:N]
S2 = S[N:][::-1]
D = defaultdict(int)
keys = []
ans = 0

for i in range(2**N):
    bit = bin(2**N+i)[3:]

    red1 = tuple([d for d, s in zip(S1, bit) if s == "1"])
    blue1 = tuple([d for d, s in zip(S1, bit) if s == "0"])
    D[(red1, blue1)] += 1

    red2 = tuple([d for d, s in zip(S2, bit) if s == "1"])
    blue2 = tuple([d for d, s in zip(S2, bit) if s == "0"])
    keys.append((blue2, red2))

for key in keys:
    ans += D[key]
print(ans)


### FIXED CODE ###

from collections import defaultdict

N = int(input())
S = input()

S1 = S[:N]
S2 = S[N:][::-1]
D = defaultdict(int)
ans = 0

for i in range(2**N):
    bit = bin(2**N+i)[3:]
    red1 = "".join([d for d, s in zip(S1, bit) if s == "1"])
    blue1 = "".join([d for d, s in zip(S1, bit) if s == "0"])
    D[(red1, blue1)] += 1

for i in range(2 ** N):
    bit = bin(2 ** N + i)[3:]
    red2 = "".join([d for d, s in zip(S2, bit) if s == "1"])
    blue2 = "".join([d for d, s in zip(S2, bit) if s == "0"])
    ans += D[(blue2, red2)]

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

N = int(input())
S = input()
l = [i for i in S]
ans = min(l.count("W"),l.count("E"))

for i in range(N):
  a = S.find("EW",i)+1
  if a == -1:
    break
  else:
    ans = min(ans,l[:a].count("W") + l[a:].count("E"))

print(ans)

### FIXED CODE ###

N = int(input())
S = [i for i in input()]
ans = S.count("E")
cnt = S.count("E")

for i in S:
  if i == "W":
    cnt += 1
  elif i == "E":
    cnt -= 1
    ans = min(ans,cnt)
  
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
LR = [list(map(int,input().split())) for i in range(K)]
mod = 998244353
ma = [0] * N
ma[0] = 1
for i in range(N):
    if ma[i] != 0:
        for l,r in LR:
            for j in range(l,r+1):
                if i+j < N:
                    ma[i+j] += ma[i]
print(ma[N-1]%mod)

### FIXED CODE ###

N,K = map(int,input().split())
LR = [list(map(int,input().split())) for i in range(K)]
LR.sort()
mod = 998244353
ma = [0] * N
ma[0] = 1
for i in range(N):
    if i >1:
        ma[i] += ma[i-1]
    p = ma[i]%mod
    if p != 0:
        for l,r in LR:
            if i+l <N:
                ma[i+l] += p
            else:
                break
            if i+r+1<N:
                ma[i+r+1] -= p
print(ma[N-1]%mod)
### BUGGY CODE ###


n, m  = map(int, input().split())
g     = {}
used  = {i:[False for _ in range(11)] for i in range(n)}
color     = [0  for _ in range(n)]

for _ in range(m):
    u, v = map(int, input().split())
    u-=1
    v-=1
    if u not in g:
        g[u] = []
    if v not in g:
        g[v] = []
    g[u].append(v)
    g[v].append(u)
    
q = int(input())
Q = []

for _ in range(q):
    node, dis, col = map(int, input().split())
    Q.append([node-1, dis, col])
Q = Q[::-1]

def bfs(node, dis, col):
    if used[node][dis] == True:
        return
        
    used[node][dis] == True    
    
    if color[node] == 0:
        color[node] = col
        
        
    if node in g and dis > 0:
        for v in g[node]:
            bfs(v, dis-1, col)
            
for node, dis, col in Q:
    bfs(node, dis, col)

for x in color:
    print(x)


### FIXED CODE ###

n, m  = map(int, input().split())
g     = {}
used  = {i:[False for _ in range(11)] for i in range(n)}
color     = [0  for _ in range(n)]

for _ in range(m):
    u, v = map(int, input().split())
    u-=1
    v-=1
    if u not in g:
        g[u] = []
    if v not in g:
        g[v] = []
    g[u].append(v)
    g[v].append(u)
    
q = int(input())
Q = []

for _ in range(q):
    node, dis, col = map(int, input().split())
    Q.append([node-1, dis, col])
Q = Q[::-1]

def bfs(now, dist, col):
    if dist < 0:
        return
    
    if used[now][dist]:
        return
 
    used[now][dist] = True
    
    if not color[now]:
        color[now] = col
 
    if now in g:
        for x in g[now]:
            bfs(x, dist - 1, col)
            
for node, dis, col in Q:
    bfs(node, dis, col)

for x in color:
    print(x)
### BUGGY CODE ###

n, k = map(int, input().split())
a_list = []
for i in range(n):
	a, b = map(int, input().split())
	a_list.extend([a for i in range(b)])
a_list.sort()
print(a_list[k-1])


### FIXED CODE ###

n, k = map(int, input().split())
a_list = []
for i in range(n):
	a, b = map(int, input().split())
	a_list.append([a, b])
a_list.sort(key=lambda x: x[0])
for i in range(n):
	k -= a_list[i][1]
	if k <= 0:
		print(a_list[i][0])
		break
### BUGGY CODE ###

if __name__ == '__main__':

	n = int(input())
	
	d = {}
	for i in range(n):
		cmd = input()
		if cmd in d:
			d[cmd] += 1
		else:
			d[cmd] = 1

	A = []
	for kv in d.items():
		if kv[1] == max(d.values()):
			A.append(kv[0])

	B = sorted(A)
	for b in B:
		print(b)


### FIXED CODE ###

if __name__ == '__main__':

	n = int(input())
	
	d = {}
	for i in range(n):
		cmd = input()
		if cmd in d:
			d[cmd] += 1
		else:
			d[cmd] = 1

	mval = max(d.values())
	A = [kv[0] for kv in d.items() if kv[1] == mval]

	B = sorted(A)
	for b in B:
		print(b)
### BUGGY CODE ###

import Queue
import copy

def main():
    H, W = map(int, raw_input().split())
    S = []

    for i in range(H):
        S.append(list(raw_input()))


    def bfs(start, S2):
        q = Queue.Queue()
        q.put(start)
        candidates = [[0, 1], [1, 0], [0, -1], [-1, 0]]
        dist = [[0]*W for _ in range(H)]
        while not q.empty():
            i = q.get()
            x = i[0]
            y = i[1]
            S2[x][y] = "#"

            for candi in candidates:
                x_new = x + candi[0]
                y_new = y + candi[1]

                if x_new < H and x_new >= 0:
                    if y_new < W and y_new >=0:
                        if S2[x_new][y_new] == ".":
                            dist[x_new][y_new] = dist[x][y] + 1
                            q.put([x_new, y_new])

        ans = 0
        for i in range(H):
            ans = max(ans, max(dist[i]))

        return ans

    ans = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == ".":
                S2 = copy.deepcopy(S)
                ans = max(ans, bfs([i, j], S2))

    print ans


if __name__ == "__main__":
    main()


### FIXED CODE ###

import Queue
import copy

def main():
    H, W = map(int, raw_input().split())
    S = []

    for i in range(H):
        S.append(list(raw_input()))


    def bfs(start, S2):
        q = Queue.Queue()
        q.put(start)
        candidates = [[0, 1], [1, 0], [0, -1], [-1, 0]]
        dist = [[0]*W for _ in range(H)]
        S2[start[0]][start[1]] = "#"
        while not q.empty():
            i = q.get()
            x = i[0]
            y = i[1]

            for candi in candidates:
                x_new = x + candi[0]
                y_new = y + candi[1]

                if x_new < H and x_new >= 0:
                    if y_new < W and y_new >=0:
                        if S2[x_new][y_new] == ".":
                            dist[x_new][y_new] = dist[x][y] + 1
                            S2[x_new][y_new] = "#"
                            q.put([x_new, y_new])

        ans = 0
        for i in range(H):
            ans = max(ans, max(dist[i]))

        return ans

    ans = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == ".":
                S2 = copy.deepcopy(S)
                ans_temp = bfs([i, j], S2)
#                print i, j, ans_temp                                                                                                                     
                ans = max(ans, ans_temp)


    print ans


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

N,K = map(int,input().split(' '))
ans_list = []
ans_list.append(N)
ans = N
for i in range(N//K+1):
    if N == ans:
        ans = abs(N-K)
    else:
        ans = abs(ans-K)
    ans_list.append(ans)
    
print(min(ans_list))

### FIXED CODE ###

N,K = map(int,input().split(' '))
first = N - (K*(N//K))
second = abs(first - K)
final = [first,second,K]
print(min(final))
### BUGGY CODE ###



def comp(ext,list0,dev):
    if list0[int((ext[0]+ext[1])/2)]>dev:
        return ext[0],int((ext[0]+ext[1])/2)
    else:
        return int((ext[0]+ext[1])/2),ext[1]


def bis(a,b,list0,dev):
    ls=[a,b]
    while ls[0]+1<ls[1]:
        ls=comp(ls,list0,dev)
    if list0[ls[0]]==dev:
        return ls[0]-1
    elif list0[ls[1]]==dev:
        return ls[1]-1
    else:
        return ls[0]


n=int(input())
l=[int(x) for x in input().split()]
l.sort()
s=0
for a in range(n-2):
    for b in range(a+1,n-1):
        if l[a]+l[b]>l[n-1]:
            c=n-1
        elif l[a]+l[b]<l[b+1]:
            c=b
        else:
            c=bis(b+1,n-1,l,l[a]+l[b])
        s=s+c-b
print(s)

### FIXED CODE ###

def bis_right(lis,dev):
    a=0
    b=len(lis)-1
    while a<b:
        c=(a+b)//2
        if lis[c]>dev:
            b=c
        else:
            a=c+1
    if lis[a]<=dev:
        return a
    return a-1



n=int(input())
l=[int(x) for x in input().split()]
l.sort()
s=0
for a in range(n-2):
    for b in range(a+1,n-1):
        c=bis_right(l[b+1:],l[a]+l[b]-1)
        s+=c+1
print(s)
### BUGGY CODE ###

n, m = map(int, input().split())
#n個に分けてあげなきゃいけない
#できる限り平均的に分けてあげたほうがいいってことはわかる。
#大きい方から下って見つかって瞬間終わりにするほうが賢いかも
#候補のうち最大の数字は
i = int(m/n)
ans = 1
while n*i <= m:
    if m % i == 0 and m / i >= n:
        ans = i
        break
    i -= 1
print(ans)


### FIXED CODE ###

def solve():
    n, m = map(int, input().split())
    for i in range(m//n,0,-1):
        if m % i == 0:
            break
    print(i)

solve()
### BUGGY CODE ###


def main():
    N = int(input())
    NN = [[0]*10 for _ in range(11)]
    for i in range(11,100):
        As = str(i)[0]
        Ae = str(i)[-1]
        cnt = 0
        for j in range(1,N+1):
            if str(j)[-1]== As and str(j)[0] == Ae:
                cnt +=1
        NN[int(As)][int(Ae)] = cnt


    ans = 0
    for i in range(1,N+1):
        ans += NN[int(str(i)[0])][int(str(i)[-1])]

    print(ans)

if __name__ == '__main__':
        main()



### FIXED CODE ###

N = int(input())
NN = [[0]*10 for _ in range(11)]
for i in range(11,100):
    As = str(i)[0]
    Ae = str(i)[-1]
    cnt = 0
    for j in range(1,N+1):
        if str(j)[-1]== As and str(j)[0] == Ae:
            cnt +=1
    NN[int(As)][int(Ae)] = cnt


ans = 0
for i in range(1,N+1):
    ans += NN[int(str(i)[0])][int(str(i)[-1])]

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

from fractions import gcd
import functools
import math

n = int(input())
a = [int(i) for i in input().split()]
l = []
for i in range(n):
 b = a[i]
 del a[i]
 l.append(functools.reduce(gcd, a))
 a.insert(i,b)
print(max(l))

### FIXED CODE ###

import fractions
n = int(input())
a = list(map(int,input().split()))
l = []
m = []
l.append(0)
m.append(0)
for i in range(n):
    l.append(fractions.gcd(l[i],a[i]))
    m.append(fractions.gcd(m[i],a[-(i+1)]))
b = [fractions.gcd(l[i],m[-(i+2)]) for i in range(n)]
print(max(b))
### BUGGY CODE ###

n=int(input())
def digitsum(n):
    x=0
    while n>=10:
        x+=n%10
        n//=10
    x+=n
    return x
x=digitsum(n)
print("Yes" if x%9==0 else "No")

### FIXED CODE ###

n=int(input())
print("Yes" if n%9==0 else "No")
### BUGGY CODE ###

#問題 D
import numpy as np
N, W = map(int,input().split())
VAL = np.zeros(W+1)
val = np.zeros(W+1)
for n in range(N):
    w,v = map(int,input().split())
    for weight in range(w,W+1):
        val[weight] = max(VAL[weight],VAL[weight-w]+v)
    VAL = np.copy(val)
#    print(val)
print(int(VAL[W]))
    # listをコピーするときは注意　https://qiita.com/utgwkk/items/5ad2527f19150ae33322

### FIXED CODE ###

import numpy as np
N, W = map(int,input().split())
#普通に書くとTLEだったのでNumpy化
dp = np.zeros(W+1,dtype=int)
for i in range(N):
    w,v = map(int,input().split())
    dp[w:] = np.maximum(dp[w:],dp[:-w]+v)
print(int(dp[-1]))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
 
import collections
from functools import reduce
from operator import mul

def combinations_count2(n, r):
    if n < 2:
        return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

c = collections.Counter(A)

dic = {}
for i in c:
    dic[i]= [combinations_count2(c[i], 2), combinations_count2(c[i] - 1, 2)]
dic_ans = {}
for ai in A:
    if ai in dic_ans:
         print(dic_ans[ai])
    ans = 0
    for i in dic:
        if i == ai:
            ans += dic[i][1]
        else:
            ans += dic[i][0]
    print(ans)

### FIXED CODE ###

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

d = {}
for a in A:
    if a in d:
        d[a] += 1
    else:
        d[a] = 1

s = 0
for k in d:
    s += d[k] * (d[k] - 1) // 2

for i in range(N):
    t = d[A[i]]
    print(s - t * (t - 1) // 2 + (t - 1) * (t - 2) // 2)
### BUGGY CODE ###

#!/usr/bin/env python3

def main():
    s = input()
    K = int(input())
    substrings = []

    for i in range(len(s)):
        for ii in range(i,len(s)):
            if s[i:ii+1] not in substrings:
                substrings.append(s[i:ii+1])
    
    substrings.sort()
    print(substrings[K-1])
        

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    s = input()
    K = int(input())
    substrings = []

    for i in range(len(s)):
        for ii in range(i,len(s)):
            if len(s[i:ii+1]) > K:
                break
            if s[i:ii+1] not in substrings:
                substrings.append(s[i:ii+1])
    
    substrings.sort()
    print(substrings[K-1])
        

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

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

inf = 10**18
ans = 1
for i in a:
    ans *= i

print(ans if ans <= inf else "-1")


### FIXED CODE ###

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

inf = 10**18
ans = 1

sorted(a, reverse=True)
if 0 in a:
    print(0)
    exit()
else:
    for i in a:
        ans *= i
        if ans > inf:
            print(-1)
            exit()

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

n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
from heapq import heappop, heappush
def main():
  push = lambda x,i: heappush(BB,(-x,i))
  BB=[]

  for i,b in enumerate(B):
    push(b,i)

  ans=0
  while BB:
    b,ind=heappop(BB)
    b,ai=-b,A[ind]
    if b<ai:
      ans=-1
      break
    d=B[(ind-1)%n]+B[(ind+1)%n]
    dd=(b-ai)//d
    if dd==0:
      if b==ai:
        continue
      ans=-1
      break
    ans+=dd
    B[ind]-=d*dd
    push(b-d*dd,ind)
  
  print(ans)
main()

### FIXED CODE ###

n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

from heapq import heappop, heappush
push = lambda x,i: heappush(BB,(-x,i))
BB=[]

for i,b in enumerate(B):
  push(b,i)

ans=0
while BB:
  b,ind=heappop(BB)
  b,ai=-b,A[ind]
  if b<ai:
    ans=-1
    break
  d=B[(ind-1)%n]+B[(ind+1)%n]
  dd=(b-ai)//d
  if dd==0:
    if b==ai:
      continue
    ans=-1
    break
  ans+=dd
  B[ind]-=d*dd
  push(b-d*dd,ind)
  
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
h_arr = list(map(int, input().split()))
dp = [0]*N
 
for i in range(1, N):
	dp[i] = min(abs(h_arr[i]-h_arr[j]) + dp[j] for j in range(max(i-K, 0), i))
print(dp[-1])

### FIXED CODE ###

n, k = list(map(int, input().split()))
h = list(map(int, input().split()))
inf = 10 ** 4 + 1
dp = [inf] * n
dp[0] = 0
for i in range(1,n):
    H = h[i]
    dp[i] = min([dp[j] + abs(h[j] - H) for j in range(max(0, i - k), i)])
print(dp[-1])
### BUGGY CODE ###

#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    h, w = map(int, input().split())
    c_h, c_w = map(int, input().split())
    d_h, d_w = map(int, input().split())
    s = ["" for _ in range(h)]
    for i in range(h):
        s[i] = str(input())

    #output
    from collections import deque

    INF = pow(10, 10)
    dp = [[INF] * w for _ in range(h)]

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    dxb = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1,  1, 1, 2, 2, 2, 2, 2]
    dyb = [-2, -1, 0,   1,  2, -2, -1,  1,  2,-2, 2, -2,-1, 1, 2, -2,-1,0, 1, 2]

    def clear_maze(sx, sy, gx, gy, maze):
        def bfs():
            q = deque([])
            q.append((sx, sy))
            dp[sx][sy] = 0

            while len(q):
                x, y = q.popleft()

                if x == gx and y == gy:
                    break

                for i in range(0, 4):
                    nx, ny = x + dx[i], y + dy[i]
                    if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and dp[nx][ny] > dp[x][y]:
                        q.appendleft((nx, ny))#ここを変更
                        dp[nx][ny] = dp[x][y]#ここを変更

                for j in range(0, 20):
                    nx2, ny2 = x + dxb[j], y + dyb[j]
                    if 0 <= nx2 < h and 0 <= ny2 < w and maze[nx2][ny2] != "#" and dp[nx2][ny2] > dp[x][y]:
                        q.append((nx2, ny2))
                        dp[nx2][ny2] = dp[x][y] + 1 
            return dp[gx][gy]
        return bfs()

    answer = clear_maze(c_h-1, c_w-1, d_h-1, d_w-1, s)
    # %%
    if answer == INF:
        print(-1)
    else:
        print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque


H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
import itertools
count = 0
check = tuple([int(abs((N-i+1)- i)) for i in range(1,N+1)])

import math
flag = True
for i in check[0:math.ceil(N/2)]:
    if A.count(i) != 2 and i != 0:
        flag = False
    if A.count(i) != 1 and i == 0:
        flag = False
        
if flag:
    print(2 ** (N//2))
else:
    print(0)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]

import itertools
count = 0
check = [int(abs((N-i+1)- i)) for i in range(1,N+1)]
flag = sorted(A) == sorted(check)
if flag:
    print(2 ** (N//2) % (10 ** 9 + 7))
else:
    print(0)
### BUGGY CODE ###

N,M=map(int,input().split())
p=list(map(int,input().split()))
p=[0]+p

par=[i for i in range(N+1)]
size=[1 for i in range(N+1)]

def find(x):
    if par[x]==x:
        return x
    else:
        return find(par[x])

def union(x,y):
    if size[x]>size[y]:
        size[x]+=size[y]
        par[y]=find(x)
    elif size[y]>size[x]:
        size[y]+=size[x]
        par[x]=find(y)
    elif size[x]==size[y]:
        size[x]+=size[y]
        par[y]=find(x)
        
for i in range(M):
    a,b=map(int,input().split())
    if find(a)==find(b):
        pass
    else:
        union(find(a),find(b))
#print(par)
ans=0
for i in range(1,N+1):
    if find(i)==find(p.index(i)):
        ans+=1
        #print(i,find(i))
print(ans)

### FIXED CODE ###

N,M=map(int,input().split())
p=list(map(int,input().split()))
p=[0]+p

par=[i for i in range(N+1)]
size=[1 for i in range(N+1)]

def find(x):
    if par[x]==x:
        return x
    else:
        return find(par[x])

def union(x,y):
    if size[x]>size[y]:
        size[x]+=size[y]
        par[y]=find(x)
    elif size[y]>size[x]:
        size[y]+=size[x]
        par[x]=find(y)
    elif size[x]==size[y]:
        size[x]+=size[y]
        par[y]=find(x)
        
for i in range(M):
    a,b=map(int,input().split())
    if find(a)==find(b):
        pass
    else:
        union(find(a),find(b))
#print(par)
ans=0
for i in range(1,N+1):
    if find(i)==find(p[i]):
        ans+=1
        #print(i,find(i))
print(ans)
### BUGGY CODE ###


from operator import itemgetter
 
n,m=map(int, input().split())
A=[]
a=0
b=0
for i in range(m):
  a,b=map(int, input().split())
  A.append([a,b])

A.sort(key=itemgetter(1))
bri=[1 for i in range(n)] #bri[0]は1,2番目の島をつなぐ

count=0

#print(A)
for i in range(m):
  #print(i)
  a=A[i][0]
  b=A[i][1]
  #print(bri[a-1:b-1])

  if not 0 in bri[a-1:b-1]:



    #print(bri[a-1:b-1])
    bri[b-2]=0
    #print(bri)
    #print(A[i])
    #print(A)
    #print(bri)
    count+=1

print(count)


### FIXED CODE ###


from operator import itemgetter
 
n,m=map(int, input().split())
A=[]
B=[]
a=0
b=0
for i in range(m):
  a,b=map(int, input().split())
  A.append([a,b])

A.sort(key=itemgetter(1))
bri=0 #取った橋のうち番号最大の島のもの。bri=5なら4,5番目の島の橋

count=0

for i in range(m):
  a=A[i][0]
  b=A[i][1]
  
  if a>=bri:
    bri=b
    count+=1

print(count)
### BUGGY CODE ###

#! /usr/bin/env python3

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

A, B, C = map(int, read().split())

if A == B == C:
    if A % 2 == 0:
        print(-1)
    else:
        print(0)
else:
    cnt = 0
    while True:
        A, B, C = (B + C) / 2, (A + C) / 2, (A + B) / 2
        if max([A, B, C]) - min([A, B, C]) == 1:
            break

        cnt += 1

    print(cnt)


### FIXED CODE ###

#! /usr/bin/env python3

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

A, B, C = map(int, read().split())

if A == B == C:
    if A % 2 == 0:
        print(-1)
    else:
        print(0)
else:
    cnt = 0
    while True:
        if (A % 2 + B % 2 + C % 2) >= 1:
            break
        cnt += 1
        A, B, C = (B + C) // 2, (A + C) // 2, (A + B) // 2

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

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

INF = float('inf')
dp = [[INF] * (n+1) for _ in range(n+1)]

acum = [0] * (n+1)
for i, ai in enumerate(a):
    acum[i+1] += acum[i] + ai

for i in range(n+1):
    dp[i][i] = 0
    if i+1 <= n:
        dp[i][i+1] = 0

for l in range(2, n+1):
    for i in range(n-l+1):
        j = i + l
        for k in range(i+1, j):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + acum[j] - acum[i])

print(dp[0][n])



### FIXED CODE ###

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

INF = float('inf')
dp = [[INF] * (n+1) for _ in range(n+1)]

acum = [0] * (n+1)
for i, ai in enumerate(a):
    acum[i+1] += acum[i] + ai

for i in range(n+1):
    dp[i][i] = 0
    if i+1 <= n:
        dp[i][i+1] = 0

for l in range(2, n+1):
    for i in range(n-l+1):
        j = i + l
        for k in range(i+1, j):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + acum[j] - acum[i])

print(dp[0][n])