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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

H,W = map(int,input().split())
N = H*W
uf = UnionFind(N)
S = [input() for _ in range(H)]
dx = [1,0,-1,0]
dy = [0,1,0,-1]
ans = 0

for k in range(N):
    x = k//W
    y = k-W*x
    for d in range(4):
        nx,ny = x+dx[d],y+dy[d]
        nk = nx*W+ny
        if not (0<=nx<H and 0<=ny<W):
            continue
        if S[x][y]!=S[nx][ny]:
            uf.union(k,nk)

for v in uf.all_group_members().values():
    b = 0
    w = 0
    for k in v:
        x = k//W
        y = k-W*x
        if S[x][y]=='#':
            b += 1
        else:
            w += 1
    ans += b*w

print(ans)

### FIXED CODE ###

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

ans = 0
visited = [[0]*W for _ in range(H)]
stack = []
dx = [1,0,-1,0]
dy = [0,1,0,-1]

for i in range(H):
    for j in range(W):
        b,w = 0,0
        if not visited[i][j]:
            stack.append([i,j])
            visited[i][j] = 1
            while stack:
                x,y = stack.pop()
                if S[x][y]=='#':
                    b += 1
                else:
                    w += 1
                for k in range(4):
                    nx,ny = x+dx[k],y+dy[k]
                    if not(0<=nx<H and 0<=ny<W):
                        continue
                    if not visited[nx][ny] and S[x][y]!=S[nx][ny]:
                        visited[nx][ny] = 1
                        stack.append([nx,ny])
            ans += b*w

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

import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,Q=LI()
HQ=[]
EVS=[]
for i in range(N):
    S,T,X=LI()
    EVS.append((S-0.5-X, 1, X))
    EVS.append((T-0.5-X, 0, X))
for i in range(Q):
    D=II()
    EVS.append((D, 2, D))
EVS.sort()

st=set()
PQ=[]
for time, ev, loc in EVS:
    if ev == 1:
        heapq.heappush(PQ, loc)
        st.add(loc)
    elif ev == 0:
        st.remove(loc)
    else:
        while PQ and PQ[0] not in st:
            heapq.heappop(PQ)
        if PQ:
            print(PQ[0])
        else:
            print(-1)


### FIXED CODE ###

import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,Q=LI()
HQ=[]
EVS=[]
for i in range(N):
    S,T,X=LI()
    EVS.append((S-0.5-X, 1, X))
    EVS.append((T-0.5-X, 0, X))
for i in range(Q):
    D=II()
    EVS.append((D, 2, D))
EVS.sort()

st=set()
PQ=[]
for time, ev, loc in EVS:
    if ev == 1:
        heapq.heappush(PQ, loc)
        st.add(loc)
    elif ev == 0:
        st.remove(loc)
    else:
        while PQ and PQ[0] not in st:
            heapq.heappop(PQ)
        if PQ:
            print(PQ[0])
        else:
            print(-1)
### BUGGY CODE ###

N=int(input())
mylist=list(map(int,input().split()))
    
#print(mylist)
answer=0

#2重forループでは重すぎるのでTLEになる。

i=0
while i<N:
    flag=0
    
    for j in range(i):
        #print("iは")
        #print(i)
        #print("jは")
        #print(j)
        if mylist[i]>mylist[j]:
            #一つでも条件満たさないjがあればflagを-1にする
            flag=-1
            break

    if flag==0:
        #flagが0であれば、そのiに対して答えを+1する
        answer+=1
    
    i+=1
        
print(answer)

### FIXED CODE ###

N=int(input())
lt=list(map(int,input().split()))
#print(lt)

temp=0
answer=0

for i in range(N):
    if i==0:
        answer+=1
        temp=lt[i]
    elif temp>=lt[i]:
        answer+=1
        temp=lt[i]
        
print(answer)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline


def main():
    n = int(input())
    a = list(map(int, input().split()))
    result = []
    for i in range(1, n + 1):
        result.append(a.index(i) + 1)
    print(*result, sep=' ')


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np
import sys
input = sys.stdin.readline


def main():
    n = int(input())
    a = list(map(int, input().split()))
    a = np.argsort(np.array(a))+1
    # print(a)
    # result = []
    # for i in range(1, n + 1):
    #     result.append(a.where(lambda x: x == i))
    print(*a, sep=' ')


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

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


def xor(x, y):
    X = bin(max(x, y))
    Y = bin(min(x, y))
    s = len(X)
    l = len(Y)
    ans = ""
    for k in range(2, 2+s-l):
        ans += X[k]
    for i in range(2, l):
        ans += str(int(X[i+s-l]) ^ int(Y[i]))

    return int(ans, 2)


Ans = 0
mod = 10**9 + 7
for i in range(n-1):
    for j in range(i+1, n):
        Ans = (Ans + xor(a[i], a[j])) % mod
print(Ans)


### FIXED CODE ###

def powmod(x, y, mod):
    if y == 0:
        return 1
    return (((powmod(x, y >> 1, mod) ** 2) % mod) * x ** (y & 1)) % mod


n = int(input())
a = tuple(map(int, input().split()))
mod = 10**9 + 7
cnt = [0] * 60
for i in range(n):
    r = a[i]
    for j in range(60):
        if r & 1:
            cnt[j] += 1
        r >>= 1

ans = 0
for i in range(60):
    ans += powmod(2, i, mod) * cnt[i] * (n-cnt[i])
    ans %= mod
print(ans)
### BUGGY CODE ###

X,Y = map(int,input().split())

if X==Y:
    print(-1)
else:
    for i in range(10**18):
        X1 = int(X*X)
        if X1 % Y != 0:
            print(str(X1))
            break
    



### FIXED CODE ###

X, Y = map(int, input().split())

if X % Y == 0:
    print(-1)
else:
   print(X)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

need =[2,5,5,4,5,6,3,7,6]

if 2 in A and 3 in A:
  del A[A.index(2)]
if 3 in A and 5 in A:
  del A[A.index(3)]
if 6 in A and 9 in A:
  del A[A.index(6)]
if 1 in A and 4 in A:
  del A[A.index(4)]
if 6 in A and 7 in A:
  del A[A.index(6)] 
if 7 in A and 9 in A:
  del A[A.index(9)] 
if 1 in A and 6 in A:
  del A[A.index(6)] 
if 1 in A and 9 in A:
  del A[A.index(9)] 
  
M = len(A)

dp = [[0]*(N+1) for _ in range(M)]
dpmax = [0]*(N+1)

for j in range(2,N+1):
  tmpmax = 0
  for i in range(M):
    tmp = need[A[i]-1]
    if j == tmp:
      dp[i][j] = A[i]
    elif j > tmp:
      if dpmax[j-tmp] != 0:
        tmp2 = dpmax[j-tmp]
        dp[i][j] = max(A[i]*(10**len(str(tmp2)) + tmp2,tmp2*10+A[i]))
    if tmpmax < dp[i][j]:
      tmpmax = dp[i][j]
  dpmax[j] = tmpmax
  
print(dpmax[-1])

### FIXED CODE ###

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

if N % 2 == 0:
  if 1 in A:
    print(int('1'*(N//2)))
    exit()

need =(2,5,5,4,5,6,3,7,6)

if 2 in A and 3 in A:
  del A[A.index(2)]
if 3 in A and 5 in A:
  del A[A.index(3)]
if 6 in A and 9 in A:
  del A[A.index(6)]
if 1 in A and 4 in A:
  del A[A.index(4)]
if 6 in A and 7 in A:
  del A[A.index(6)] 
if 7 in A and 9 in A:
  del A[A.index(9)] 
if 1 in A and 6 in A:
  del A[A.index(6)] 
if 1 in A and 9 in A:
  del A[A.index(9)] 
  
A = tuple(A)
M = len(A)

dp = [[0]*(N+1) for _ in range(M)]
dpmax = [0]*(N+1)

def take_max():
  return max(A[i]*(10**len(str(tmp2)) + tmp2,tmp2*10+A[i]))

for j in range(2,N+1):
  tmpmax = 0
  for i in range(M):
    tmp = need[A[i]-1]
    if j == tmp:
      dp[i][j] = A[i]
    elif j > tmp:
      if dpmax[j-tmp] != 0:
        tmp2 = dpmax[j-tmp]
        dp[i][j] = take_max()
    if tmpmax < dp[i][j]:
      tmpmax = dp[i][j]
  dpmax[j] = tmpmax
  
print(dpmax[-1])
### BUGGY CODE ###

# Problem D - Pairs

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

# initialization
a_nums = sorted(a_nums)
left = -10**19
right = 10**19

# binary search
while right-left>1:
    x = (right + left) // 2
    S = 0
    T = 0
    # 判定部分
    for a in a_nums:
        if a>0:
            r2 = N
            l2 = -1
            while r2-l2>1:
                mid = (r2 + l2) // 2
                if a*a_nums[mid]<=x:
                    l2 = mid
                else:
                    r2 = mid
            S += r2
        elif a<0:
            r2 = N
            l2 = -1
            while r2-l2>1:
                mid = (r2 + l2) // 2
                if a*a_nums[mid]<=x:
                    r2 = mid
                else:
                    l2 = mid
            S += N - r2
        elif x>=0: # a==0の時
            S += N
        # 重複を数える
        if a*a<=x:
            T += 1
    # 判定部分（大元）
    check_nums = (S - T) // 2
    if check_nums>=K:
        right = x
    else:
        left = x

# output
print(right)


### FIXED CODE ###

#!/usr/bin/env python3

def solve_m(S, T, K):
    def count(x):
        ret, ti = 0, 0
        for s in S:
            # 積がxを初めて下回るtiを求める。なければlen(T)
            while ti < len(T) and s * T[ti] > x:
                ti += 1
            if ti == len(T):
                break
            ret += len(T) - ti
        return ret
    left, right = -(10**18)-1, 10**18+1
    while abs(right - left) > 1:
        mid = (left + right) // 2
        if count(mid) < K:
            left = mid
        else:
            right = mid
    return right

def solve(S, mS, K):
    def count(x, T):
        ret, j = 0, len(T) - 1
        for i, t in enumerate(T):
            while j >= 0 and t * T[j] > x:
                j -= 1
            if j == -1:
                break
            ret += j + 1 - (1 if i <= j else 0)
        return ret // 2
    left, right = -(10**18)-1, 10**18+1
    while abs(right - left) > 1:
        mid = (left + right) // 2
        if count(mid, S) + count(mid, mS) < K:
            left = mid
        else:
            right = mid
    return right

def main():
    N, K = list(map(int, input().split()))
    A = sorted(map(int, input().split()), reverse=True)
    B = {-1:[], 0:[], 1:[]}
    for a in A:
        if a == 0:
            B[0].append(0)
        else:
            B[a//abs(a)].append(a)
    m = len(B[-1]) * len(B[1])
    z = len(B[0]) * (N-len(B[0])) + len(B[0]) * (len(B[0])-1) // 2
    if K <= m:
        print(solve_m(B[1], B[-1], K))
    elif K <= m + z:
        print(0)
    else:
        print(solve(sorted(B[1]), B[-1], K - m - z))


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

n,ma,mb=map(int,input().split())
zen=[]
kou=[]
A=[ list(map(int,input().split())) for i in range(n//2)];a=len(A)
B=[ list(map(int,input().split())) for i in range(n-n//2)];b=len(B)
for bit in range(1<<a):
    now=[0,0,0]
    for i in range(a):
        if (bit>>i)&1:
            now[0]+=A[i][0]
            now[1]+=A[i][1]
            now[2]+=A[i][2]
    zen.append(now)
for bit in range(1<<b):
    now=[0,0,0]
    for i in range(b):
        if (bit>>i)&1:
            now[0]+=B[i][0]
            now[1]+=B[i][1]
            now[2]+=B[i][2]
    kou.append(now)

ans=10**10
for li in zen:
    for lj in kou:
        if li[0]+lj[0]==0 :continue
        if (li[0]+lj[0])*mb==ma*(li[1]+lj[1]):
            ans=min(ans,li[2]+lj[2])
print(ans if ans!=10**10 else -1)

### FIXED CODE ###

n,ma,mb=map(int,input().split())
zen=[[10**10]*401 for i in range(401)]
kou=[[10**10]*401 for j in range(401)]
A=[ list(map(int,input().split())) for i in range(n//2)];a=len(A)
B=[ list(map(int,input().split())) for i in range(n-n//2)];b=len(B)
for bit in range(1<<a):
    now=[0,0,0]
    for i in range(a):
        if (bit>>i)&1:
            now[0]+=A[i][0]
            now[1]+=A[i][1]
            now[2]+=A[i][2]
    zen[now[0]][now[1]]=min(zen[now[0]][now[1]],now[2])
for bit in range(1<<b):
    now=[0,0,0]
    for i in range(b):
        if (bit>>i)&1:
            now[0]+=B[i][0]
            now[1]+=B[i][1]
            now[2]+=B[i][2]
    kou[now[0]][now[1]]=min(kou[now[0]][now[1]],now[2])


ans=10**10
for base in range(1,401):
    na=base*ma ; nb=base*mb 
    if max(na,nb)>400: break
    for i in range(na+1):
        for j in range(nb+1):
            ans=min(ans,zen[i][j]+ kou[na-i][nb-j])


print(ans if ans<10**6 else -1)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,m,*pqc = map(int, read().split())

g = {}
M = iter(pqc)

for p,q,c in zip(M,M,M):
    pc = ((p-1)<<20)+c
    qc = ((q-1)<<20)+c
    pp = (p-1)<<20
    qq = (q-1)<<20
    
    if pc not in g: g[pc] = []
    if qc not in g: g[qc] = []
    if pp not in g: g[pp] = []
    if qq not in g: g[qq] = []
    
    g[pc].append(qc)
    g[pc].append(pp)

    g[qc].append(pc)
    g[qc].append(qq)

    g[pp].append(pc)
    g[qq].append(qc)

if 0 not in g: g[0] = []

from collections import deque
q = deque([(0,0)])
res = {0:0}

mask = (1<<20)-1
INF = 1<<30
while q:
    vl,dv = q.popleft()
    if res[vl] < dv: continue

    for tl in g[vl]:
        cost = (vl&mask==0 or tl&mask==0)
        ndv = cost + dv
        if (tl not in res or res[tl] > ndv):
            res[tl] = ndv
            if cost: q.appendleft((tl,ndv))
            else: q.append((tl,ndv))
            

if (n-1)<<20 in res:
    print(res[(n-1)<<20]//2)
else:
    print(-1)






### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,m,*pqc = map(int, read().split())

g = {}
M = iter(pqc)

for p,q,c in zip(M,M,M):
    pc = ((p-1)<<20)+c
    qc = ((q-1)<<20)+c
    pp = (p-1)<<20
    qq = (q-1)<<20
    
    if pc not in g: g[pc] = []
    if qc not in g: g[qc] = []
    if pp not in g: g[pp] = []
    if qq not in g: g[qq] = []
    
    g[pc].append(qc)
    g[pc].append(pp)

    g[qc].append(pc)
    g[qc].append(qq)

    g[pp].append(pc)
    g[qq].append(qc)

if 0 not in g: g[0] = []

from collections import deque
q = deque([(0,0)])
res = {0:0}

mask = (1<<20)-1
while q:
    vl,dv = q.popleft()
    if res[vl] < dv: continue
    if (vl>>20) == n-1:
        res[(n-1)<<20] = dv+1
        break
    for tl in g[vl]:
        ndv = dv + (vl&mask==0 or tl&mask==0)
        if tl not in res or res[tl] > ndv:
            res[tl] = ndv
            if vl&mask==0 or tl&mask==0:
                q.append((tl,ndv))
            else:
                q.appendleft((tl,ndv))

if (n-1)<<20 in res:
    print(res[(n-1)<<20]//2)
else:
    print(-1)
### BUGGY CODE ###

from collections import Counter
import numpy as np

def bi(s):
  return list(map(int, list(np.binary_repr(int(s),width=64))))

mod = 10**9+7
base = 2**np.arange(63,-1,-1) % mod

N=int(input())
A=list(map(bi,input().split()))
count=np.array(A).reshape(N,64).sum(0)

print((base*count*(N-count)).sum() % mod)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
mod = 10**9+7
base = [(2**i)%mod for i in range(63,-1,-1)]

count = [0 for i in range(64)]
for i in range(N):
  b = list(map(int, list(bin(A[i])[2:])))
  b = [0]*(64-len(b))+b
  for j in range(64):count[j]+=b[j]

print(sum([base[i]*count[i]*(N-count[i]) for i in range(64)])%mod)
### BUGGY CODE ###

S = input()

N = len(S)
ans = 0

for i in range(N-3):
    for j in range(i+3,N):
        num = S[i:j+1]
        if int(num)%2019 == 0:
            ans += 1
        
print(ans)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import Counter

S = input()

P = 2019
N = len(S)

def solve_2(S):
    ind = (i for i, x in enumerate(S, 1) if x % 2 == 0)
    return sum(ind)

def solve_5(S):
    ind = (i for i, x in enumerate(S, 1) if x % 5 == 0)
    return sum(ind)

def solve(S,P):
    if P == 2:
        return solve_2(S)
    if P == 5:
        return solve_5(S)
    S = S[::-1]
    T = [0] * len(S)
    T[0] = int(S[0]) % P
    power = 1
    for i in range(1, len(S)):
        power *= 10
        power %= P
        T[i] = T[i-1] + power * int(S[i])
        T[i] %= P
    counter = Counter(T)
    return sum(x * (x - 1) // 2 for x in counter.values()) + counter[0]


print(solve(S,P))
### BUGGY CODE ###

from collections import Counter

n = int(input())
a = []
for i in range(n):
    a.append(input())
b = Counter(a)
for k, v in sorted(b.items()):
    if v == max(b.values()):
        print(k)


### FIXED CODE ###

b = {}
for _ in range(int(input())): s=input(); b[s]=b.get(s,0)+1
m = max(b.values())
print(*sorted(k for k in b if b[k]==m))
### BUGGY CODE ###

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

for i in range(K):
    table = [0 for _ in range(N*2)]
    # imos法 - メモ
    for j in range(N):
        ai = As[j]
        # 電球が照らす左端をメモ
        table[max((j-ai)*2-1, 0)] += 1
        # 電球が照らす右端をメモ
        table[min((j+ai)*2+1, N*2-1)] -= 1
    
    # imos法 - シミュレート
    for j in range(N*2):
        if j > 0:
            table[j] += table[j-1]
    
    # 答えになおす
    for j in range(N):
        As[j] = table[j*2]
    
    exit_condition = True
    for j in range(N):
        if As[j] != N:
            exit_condition = False
            break
    
    if exit_condition:
        print(*As)
        exit(0)
            

print(*As)

### FIXED CODE ###

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

for i in range(K):
    table = [0 for _ in range(N*2)]
    # imos法 - メモ
    for j in range(N):
        ai = As[j]
        # 電球が照らす左端をメモ
        table[max((j-ai)*2-1, 0)] += 1
        # 電球が照らす右端をメモ
        table[min((j+ai)*2+1, N*2-1)] -= 1
    
    # imos法 - シミュレート
    for j in range(N*2):
        if j > 0:
            table[j] += table[j-1]
    
    # 答えになおす
    for j in range(N):
        As[j] = table[j*2]
    
    exit_condition = True
    for j in range(N):
        if As[j] != N:
            exit_condition = False
            break
    
    if exit_condition:
        print(*As)
        exit(0)
            

print(*As)
### BUGGY CODE ###

from __future__ import print_function
from sys import stdin
def lcs(x, y):
    m = len(x)
    n = len(y)
    c = [[0]*(n + 1) for a in range(m + 2)]
    for i in xrange(1, m + 1):
        for j in xrange(1, n + 1):
            if x[i-1] == y[j-1]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])
    return max(max(c))
 
n = int(raw_input().rstrip())
strs = stdin.readlines()
ret = []
for i in xrange(n):
    s1 = strs[i*2].rstrip()
    s2 = strs[i*2+1].rstrip()
    ret.append(lcs(s1, s2))
print(*ret, sep="\n")

### FIXED CODE ###

def lcs(x, y):
    a = len(x)
    b = len(y)
    c1 = [0] * (b + 1)
    for i in range(a):
        e1 = x[i]
        c2 = c1[:]
        for j in range(b):
            if e1 == y[j]:
                c1[j+1] = c2[j] + 1
            elif c1[j+1] < c1[j]:
                c1[j+1] = c1[j]
    return c1[-1]
   
n = int(input().rstrip())
ret = []
for i in range(n):
    s1 = input().rstrip()
    s2 = input().rstrip()
    ret.append(lcs(s1, s2))
print(*ret, sep="\n")
### BUGGY CODE ###

import copy
N, M = map(int, input().split())
LR = []
LR2 = []
count = 0
for i in range(M):
    l, r = map(int, input().split())
    LR2.append(l)
    LR2.append(r)
    LR3 = copy.copy(LR2)
    LR.append(LR3)
    LR2.clear()
for i in range(1, N+1):
    flag = 1
    for j in LR:
        if not (i >= j[0] and i <= j[1]):
            flag = 0
            break
    if flag == 1:
        count += 1

print(count)






### FIXED CODE ###

import copy
N, M = map(int, input().split())
LR = []
LR2 = []
count = 0
min = 1
max = N
for i in range(M):
    l, r = map(int, input().split())
    LR2.append(l)
    LR2.append(r)
    LR3 = copy.copy(LR2)
    LR.append(LR3)
    LR2.clear()
#print(M, N, LR)

for i in LR:
    if min < i[0]:
        min = i[0]
    if max > i[1]:
        max = i[1]
    #print(min, max)
if max - min >= 0:
    ans = max - min + 1
else:
    ans = 0
print(ans)
### BUGGY CODE ###

def warshall_floyd(d, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if (d[i][k] == 0 or d[k][j] == 0):
                    continue
                if (i == j):
                    continue
                if (d[i][j] == 0):
                    d[i][j] = d[i][k] + d[k][j]
                else:
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])

n, x, y = map(int, input().split())

result = [[0] * n for i in range(n)]
for i in range(n):
    if (i-1 >= 0):
        result[i][i-1] = 1
    if (i+1 < n):
        result[i][i+1] = 1
result[x-1][y-1] = 1
result[y-1][x-1] = 1

warshall_floyd(result, n)

result_hash = [0] * (n-1)
for i in range(n):
    for j in range(n):
        if result[i][j] == 0:
            continue
        result_hash[result[i][j] - 1] += 1

for i in range(n-1):
    print(int(result_hash[i] / 2))


### FIXED CODE ###

n, x, y = map(int, input().split())
result = [0] * n
for i in range(1,n):
    for j in range(i+1, n+1):
        result[min([(j - i), (abs(i - x) + 1 + abs(j - y))])] += 1

for i in range(1,n):
    print(result[i])
### BUGGY CODE ###

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

babies=[(a,i) for i,a in enumerate(a)]
babies.sort(reverse=True)

dp=[[0]*(n+1) for i in range(n+1)]
ans=0
for l in range(n):
    for r in range(n):
        if l+r==n:
            ans=max(ans,dp[l][r])
            break
        activeness,ind=babies[r+l]
        dp[l+1][r]=max(dp[r+1][r],dp[l][r]+abs(ind-l)*activeness)
        dp[l][r+1]=max(dp[l][r+1],dp[l][r]+abs(ind-(n-1-r))*activeness)

print(ans)


### FIXED CODE ###

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

babies=[(a,i) for i,a in enumerate(a)]
babies.sort(reverse=True)

dp=[[0]*(n+1) for i in range(n+1)]#左、右から何人いるか? 家庭菜園
ans=0
for l in range(n):
    for r in range(n):
        if l+r==n:
            ans=max(ans,dp[l][r])
            break
        activeness,ind=babies[r+l]
        dp[l+1][r]=max(dp[r+1][r],dp[l][r]+abs(ind-l)*activeness)
        dp[l][r+1]=max(dp[l][r+1],dp[l][r]+abs(ind-(n-1-r))*activeness)

print(ans)