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

#!/usr/bin/env python3
import sys
# sys.setrecursionlimit(10000000)
INF = 1<<32


from bisect import bisect_left, bisect_right

def solve(N: int, M: int, A: "List[int]"):
        
    def binary_search(left: int, right: int):
        s = 0
        c = 0
        mi = INF

        while right-left > 1 or c < M:
            # print("test: ", left, " ", right)
            mid = (left+right)//2
            # print("mid: ", mid)
            # mid以上の価値の握手の個数を求める
            # s = []
            s = 0
            c = 0
            mi = INF
            for i in range(N):
                p = bisect_left(A, mid-A[i])
                if p != N:
                    mi = min(mi, A[i]+A[p])
                # print(A[i], A[p:], aq[N]-aq[p],  A[i]*(N-p))
                s += aq[N]-aq[p]
                s += A[i]*(N-p)
                c += N-p
                
            # mid以上の握手の個数がM以上か否か
            if c > M:
                left = mid

            else:
                right = mid
        
        s -= (c-M)*mi

        return s

    A.sort()
    aq = [0] * (N+1)
    for i in range(N):
        aq[i+1] = aq[i] + A[i]

    print(binary_search(1, A[-1]*2))
    
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
# sys.setrecursionlimit(10000000)
INF = 1<<32


from bisect import bisect_left, bisect_right

def solve(N: int, M: int, A: "List[int]"):
        
    def binary_search(left: int, right: int):
        s = 0
        c = 0
        mi = INF

        while right-left > 1 or c < M:
            # print("test: ", left, " ", right)
            mid = (left+right)//2
            # print("mid: ", mid)
            # mid以上の価値の握手の個数を求める
            # s = []
            s = 0
            c = 0
            mi = INF
            for i in range(N):
                p = bisect_left(A, mid-A[i])
                if p != N:
                    mi = min(mi, A[i]+A[p])
                # print(A[i], A[p:], aq[N]-aq[p],  A[i]*(N-p))
                s += aq[N]-aq[p]
                s += A[i]*(N-p)
                c += N-p
                
            # mid以上の握手の個数がM以上か否か
            if c > M:
                left = mid

            else:
                right = mid
        
        if c > M:
            s -= (c-M)*mi

        return s

    A.sort()
    aq = [0] * (N+1)
    for i in range(N):
        aq[i+1] = aq[i] + A[i]

    print(binary_search(1, A[-1]*2))
    
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, A)

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

N = int(input())
mod = 0
if N == 1:
  print(0)
else:
  for i in range(1,N+1):
    if i == 1:
      mod += 1
    elif i == N:
      mod += 0
    else:
      mod += i
  print(mod)
  

### FIXED CODE ###

N = int(input())
mod = 0
if N == 1:
  print(0)
else:
  print(N+N*(N-1)//2-N)
### BUGGY CODE ###

import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n = INT()
a = LIST()
c = Counter(a)
a = sorted(a)

isprime = {a[i]:True for i in range(n)}

for i in range(n): 
    if not isprime[a[i]]: continue
    j = 2
    while a[i]*j < a[-1]+1:
        if a[i]*j in a:
            isprime[a[i]*j] = False
        j += 1

diff = len([i for i in range(len(c)) if list(c.values())[i] != 1 and isprime[list(c.keys())[i]]])
print(list(isprime.values()).count(True)-diff)

### FIXED CODE ###

import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n = INT()
a = LIST()
c = Counter(a)
a = sorted(a)
M = max(a)
isprime = [0]*(M+1)

for i in range(n):
    if isprime[a[i]]==0:
        isprime[a[i]] = 1
        tmp = 2
        while a[i]*tmp < M+1:
            isprime[a[i]*tmp] = 2
            tmp += 1
    elif isprime[a[i]] == 1:
        isprime[a[i]] = 2

ans = 0
for ele in a:
    if isprime[ele] != 2:
        ans += 1
print(ans)
### BUGGY CODE ###

import math
import sys
K, N = [int(i) for i in input().split(' ')]
mod = 998244353
sys.setrecursionlimit(100000)

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, (y-1)//2)**2 * x % mod

def div(a, b):
    return mul(a, power(b, mod-2))

def C(n, r):
    if r < 0:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

olist = [C(N+K-2, N) % mod if K!=1 else 0]

def EE(i):
    k2 = int((K - abs(K - int((i-1)/2) * 2) )/2)
    k1 = K - k2*2 - (1 if i % 2 == 0 else 0)
    result = 0
    for j in range(min(k2, N+1)):
        if i % 2 == 1:
            olist[j] = div(olist[j] * k2, k2-j)
        olist[j] = div(olist[j] * (k1+j) , N+k1)
        result = (result + olist[j]) % mod
        if i % 2 == 0 and j != N:
            result = (result + div(olist[j] * (N-j), N+k1-1)) % mod

    if N >= k2:
        if i % 2 == 1:
            olist.append((C(k2, k2) * C(N+k1-1, N-k2) * pow(2, k2)) % mod)
        else:
            if i != 2:
                olist[k2] = div(olist[k2] * (k1+k2), N+k1)
            result = (result + div(olist[k2] * (N-k2), N+k1-1)) % mod
        result = (result + olist[k2]) % mod
    return result

if K == 1:
    print(0)
else:
    result = []
    for i in range(K):
        result.append(str(EE(i+2)))
    print("\n".join(result + result[:-1][::-1]))


### FIXED CODE ###

import math
import sys
K, N = [int(i) for i in input().split(' ')]
mod = 998244353
sys.setrecursionlimit(100000)

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def cmb_f(n, r, mod):
#    print(n, r)
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
#    print(g1[n] * g2[r] * g2[n-r] % mod)
    return g1[n] * g2[r] * g2[n-r] % mod

NNN = 10**4
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def EN(i):
    k2 = int((K - abs(K - int((i-1)/2) * 2) )/2)
    k1 = K - k2*2 - (1 if i % 2 == 0 else 0)
    result = 0
    for j in range(k2+1):
        if N < j:
            break
        result = (result + mul(mul(cmb_f(k2, j, mod) , cmb_f(N+k1-1, j+k1-1, mod)) , pow(2, j) % mod))% mod
    if i % 2 == 1:
        return result
    for j in range(k2+1):
        if N-1 < j:
            break
        result = (result + mul(mul(cmb_f(k2, j, mod), cmb_f(N+k1-2, j+k1-1, mod)), pow(2, j) % mod))% mod
    return result

if K == 1:
    print(0)
else:
    result = []
    for i in range(K):
        result.append(str(EN(i+2)))
    print("\n".join(result + result[:-1][::-1]))
### BUGGY CODE ###

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

ans = 0
for i in range(n-k+1):
  t = (sum(p[i:i+k])+k)/2
  if ans < t: ans = t
print(ans)

### FIXED CODE ###

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

# 値ごとの期待値を取得
s = [0]*n
for i in range(n):
  s[i] = (p[i]+1)/2

# 期待値を累積していく
p = [0]*(n+1)
for i in range(1, n+1):
  p[i] = p[i-1] + s[i-1]

# 下記の方法で隣接する期待値合計を取得し、比較を行う。
# 隣接する期待値の合計　= 対象とする範囲の最大累積和　- 対象外範囲の最大累積和
ans = 0
for i in range(n-k+1):
  ans = max(ans, p[i+k] - p[i])

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

from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


memo = {}

def countbit(x):
    i = 0
    cnt = 0
    while x >= 1<<i:
        if x & (1<<i):
            cnt += 1
        i += 1
    return cnt


def count(x, c):
    if c == 0:
        return 0
    s = 1
    x = x % c
    while x != 0:
        s += 1
        x = x % countbit(x)
    return s

def main():
    n = int(input())
    x = int(input(), 2)
    c = countbit(x)
    for i in range(n):
        y = x ^ (1<<(n-i-1))
        cc = (x >> (n-i-1)) & 1
        s = count(y, c - 1 if cc else c + 1)
        print(s)


main()


### FIXED CODE ###

from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


memo = {}

def countbit(x):
    i = 0
    cnt = 0
    while x >= 1<<i:
        if x & (1<<i):
            cnt += 1
        i += 1
    return cnt


def count(x):
    # if c == 0:
    #     return 0
    # s = 1
    # x = x % c
    s = 0
    while x != 0:
        s += 1
        x = x % countbit(x)
    return s

def main():
    n = int(input())
    xs = list(input())
    c = len([i for i in xs if i == '1'])
    dp = {}
    dps = {}
    for i in range(-1, 2):
        cc = c + i
        if cc == 0:
            continue
        dp[cc] = [-1] * n
        base = 1 % cc
        dpstmp = 0
        for i in range(n):
            dp[cc][i] = base
            if xs[-i-1] == '1':
                dpstmp += base
            base = base * 2 % cc
        dps[cc] = dpstmp % cc

    for i in range(n):
        cc = c
        if xs[i] == '1':
            cc -= 1
        else:
            cc += 1
        if cc == 0:
            print(0)
            continue
        res = dps[cc]
        if xs[i] == '1':
            res = (res - dp[cc][-i-1]) % cc
        else:
            res = (res + dp[cc][-i-1]) % cc
        s = count(res) + 1
        print(s)


main()
### BUGGY CODE ###

from collections import Counter
s = input()
i = 0
while i < len(s):
    if s[i] == 'd':
        S = s[i:i + 5]
        if i + 6 < len(s):
            if S + s[i + 5] + s[i + 6] == "dreamer":
                i += 7
                if i + 3 < len(s):
                    if s[i:i + 4] == "aser":
                        i += 4
                        continue
                if i + 2 < len(s):
                    if s[i:i + 3] == "ase":
                        i += 3
                        continue
                continue
        if S == "dream":
            i += 5
            continue
    elif s[i] == 'e':
        S = s[i:i + 5]
        if i + 5 < len(s):
            if S + s[i + 5] == "eraser":
                i += 6
                continue
        if S == "erase":
            i += 5
            continue
    if i + 4 >= len(s):
        break
else:
    print("YES")
    exit()
print("NO")

### FIXED CODE ###

from collections import Counter
s = input()
i = 0
while i < len(s):
    if s[i] == 'd':
        S = s[i:i + 5]
        if i + 6 < len(s):
            if S + s[i + 5] + s[i + 6] == "dreamer":
                i += 7
                if i + 3 < len(s):
                    if s[i:i + 4] == "aser":
                        i += 4
                        continue
                if i + 2 < len(s):
                    if s[i:i + 3] == "ase":
                        i += 3
                        continue
                continue
        if S == "dream":
            i += 5
            continue
        break
    elif s[i] == 'e':
        S = s[i:i + 5]
        if i + 5 < len(s):
            if S + s[i + 5] == "eraser":
                i += 6
                continue
        if S == "erase":
            i += 5
            continue
        break
    else:
        break
    if i + 4 >= len(s):
        break
else:
    print("YES")
    exit()
print("NO")
### BUGGY CODE ###

N=int(input())
A=[]
B=[]
str='Yes'
total=0
time=0
for i in range(N):
    a,b = map(int, input().split())
    A.append(a)
    B.append(b)

time=min(B)
for j in range(N):
    if time<=min(B):
        time = min(B)
    K=B.index(min(B))
    B[K]=1000000000000
    total +=A[K]
    if total>time:
        str='No'
print(str)

### FIXED CODE ###

N=int(input())
A=[]

str='Yes'
total=0
time=0
for i in range(N):
    a,b, = map(int, input().split())
    A.append([b,a])

A.sort()


for j in range(N):
    if time<=A[j][0]:
        time = A[j][0]

    A[j][0]=100000000000
    total +=A[j][1]

    if total>time:
        str='No'
print(str)
### BUGGY CODE ###

import copy

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

N = 13
MOD = 1000000000 + 7
s = input()
dp = [0 for i in range(N)]
dp[0] = 1

for i, si in enumerate(reversed(s)):

    nextdp = [0 for i in range(N)]
    for j in range(10):
        c = 0
        if si == "?":
            c = (j * 10 ** i) % N
        elif j == 0:
            c = (int(si) * 10 ** i) % N
        else:
            break

        for k in range(N):
            nextdp[(k + c) % N] += dp[k]
            nextdp[(k + c) % N] %= MOD

    dp = copy.copy(nextdp)

print(dp[5])


### FIXED CODE ###

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

N = 13
MOD = 10 ** 9 + 7

s = input()[::-1]

dp = [0 for i in range(N)]
nextdp = [0 for i in range(N)]
zeros = [0 for i in range(N)]
dp[0] = 1

r = 1
for i, si in enumerate(s):
    nextdp = zeros[:]

    for j in range(10):
        jj = j
        if si == "?":
            pass
            # c = (j * 10 ** i) % N
        elif j == 0:
            jj = int(si)
        else:
            break

        for k in range(N):
            l = (k + r * jj) % N
            nextdp[l] = (nextdp[l] + dp[k]) % MOD

    dp = nextdp
    r = r * 10 % N

print(dp[5])
### BUGGY CODE ###

import sys
import heapq
import copy
import numpy as np
from collections import deque

h,w=list(map(int,input().split()))
a=[['.']*w for i in range(h)]
q=deque()
cnt=0
for i in range(h):
    for j,x in enumerate(input()):
        if x=='#':
            deque.append(q,[i,j])
            a[i][j]=0

while len(q)>0:
    hh,ww=deque.popleft(q)

    for nh,nw in [[hh+dh,ww+dw] for dh,dw in [[1,0],[-1,0],[0,1],[0,-1]]]:
        
        if 0>nh or nh>=h or 0>nw or nw>=w or a[nh][nw]!='.':
            continue
        
        a[nh][nw]=a[hh][ww]+1
        cnt=max(cnt,a[nh][nw])

        deque.append(q,[nh,nw])

print(cnt)


### FIXED CODE ###

from collections import deque

h,w=list(map(int,input().split()))
a=[[c for c in input()] for _ in range(h)]
visit=[[0]*w for _ in range(h)]
q=deque()

for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            deque.appendleft(q,(i,j,0))
            visit[i][j]=1
ans=0
while len(q)>0:
    i,j,cnt=deque.pop(q)

    ans=max(ans,cnt)

    for di,dj in [(-1,0),(1,0),(0,-1),(0,1)]:
        ni=i+di
        nj=j+dj
        if 0<=ni<h and 0<=nj<w and visit[ni][nj]==0:
            visit[ni][nj]=1
            deque.appendleft(q,(ni,nj,cnt+1))

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

N, K = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(N)]
XY.sort()

def count(x_min, x_max, y_min, y_max, i, j):
    cnt = 0
    for m in range(i, j + 1):
        if x_min <= XY[m][0] <= x_max and y_min <= XY[m][1] <= y_max:
            cnt += 1
    return cnt

ans = 10 ** 20
for i in range(N - 1):
    for j in range(i + 1, N):
        for k in range(N):
            for l in range(N):
                if XY[k][1] < XY[l][1]:
                    if count(XY[i][0], XY[j][0], XY[k][1], XY[l][1], i, j) >= K:
                        # print ('A')
                        ans = min(ans, (XY[j][0] - XY[i][0]) * (XY[l][1] - XY[k][1]))
print (ans)


### FIXED CODE ###

#PythonだとTLEする
N, K = map(int, input().split())
X = [0] * N
Y = [0] * N
for i in range(N):
    x, y = map(int, input().split())
    X[i] = x
    Y[i] = y

def count(x_min, x_max, y_min, y_max):
    cnt = 0
    for i in range(N):
        if x_min <= X[i] <= x_max and y_min <= Y[i] <= y_max:
            cnt += 1
    return cnt

ans = 10 ** 20
for i in range(N):
    for j in range(N):
        for k in range(N):
            for l in range(N):
                # print ('i, j , k, l = ', i, j, k, l)
                if X[i] < X[j] and Y[k] < Y[l]:
                    if count(X[i], X[j], Y[k], Y[l]) >= K:
                        # print ('A')
                        ans = min(ans, (X[j] - X[i]) * (Y[l] - Y[k]))
print (ans)
### BUGGY CODE ###

n = int(input())

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

ans = 1

for i in range(n):
  ans = ans * a[i]

if ans > (10 ** 18):
  print("-1") 
else:
  print(ans)

### FIXED CODE ###

n = int(input())

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

ans = 1

if 0 in a:
  ans = 0
else:
  for i in range(n):
    ans = ans * a[i]
    if ans > (10 ** 18): 
      break
      
if ans > (10 ** 18):
  print("-1") 
else:
  print(ans)
### BUGGY CODE ###

from collections import deque
#空のリスト 作った後は普通にappend使えばOK
n,m,k=map(int,input().split())
 
tomodati=[[] for i in range(n+1)]
 
group=[0]*(n+1)
 
block=[0]*(n+1)
 
tansaku=deque()
 
for i in range(m):
    a,b=map(int,input().split())
    tomodati[a].append(b)
    tomodati[b].append(a)
 
num=1
 
for i in range(1,n+1):
    if group[i]==0:
        tansaku.append(i)
        group[i]=num
    else:
        continue
    while len(tansaku)>0:
        for j in tomodati[tansaku[0]]:
            if group[j]==0:
                group[j]=num
                tansaku.append(j)
        tansaku.popleft()
    num+=1
 
for i in range(k):
    c,d=map(int,input().split())
    if group[c]==group[d]:
        block[c]+=1
        block[d]+=1
 
ans=""
 
for i in range(1,n+1):
    ans+=str(group.count(group[i])-len(tomodati[i])-block[i]-1)+" "
 
print(ans)

### FIXED CODE ###

from collections import deque
#空のリスト 作った後は普通にappend使えばOK
n,m,k=map(int,input().split())
 
tomodati=[[] for i in range(n+1)]
 
group=[0]*(n+1)

group_cnt=[0]*(n+1)
 
block=[0]*(n+1)
 
tansaku=deque()
 
for i in range(m):
    a,b=map(int,input().split())
    tomodati[a].append(b)
    tomodati[b].append(a)
 
num=1
 
for i in range(1,n+1):
    if group[i]==0:
        tansaku.append(i)
        group[i]=num
        group_cnt[num]+=1
    else:
        continue
    while len(tansaku)>0:
        for j in tomodati[tansaku[0]]:
            if group[j]==0:
                group[j]=num
                group_cnt[num]+=1
                tansaku.append(j)
        tansaku.popleft()
    num+=1
 
for i in range(k):
    c,d=map(int,input().split())
    if group[c]==group[d]:
        block[c]+=1
        block[d]+=1
 
ans=[]
 
for i in range(1,n+1):
    ans.append(group_cnt[group[i]]-len(tomodati[i])-block[i]-1)
 
print(*ans)
### BUGGY CODE ###

import numpy as np
n, k = list(map(int, input().split()))

def get_bound(x):
    if x < k-1:
        return [(0, x+1), (x+k+1, 2*k)]
    else:
        return [(x-k+1, x+1)]

blacks = np.zeros((2*k+1, 2*k+1))
for _ in range(n):
    x, y, c = input().split()
    x = int(x)%(2*k)
    y = int(y)%(2*k) if c == 'B' else (int(y)+k)%(2*k)

    for shift in [0, k]:
        for b, t in get_bound((y+shift)%(2*k)):
            for l, r in get_bound((x+shift)%(2*k)):
                blacks[b, l] += 1
                blacks[t, l] -= 1
                blacks[b, r] -= 1
                blacks[t, r] += 1
        
ans = np.max(np.cumsum(np.cumsum(blacks, axis = 1), axis = 0))
print(int(ans))


### FIXED CODE ###

import numpy as np
n, k = list(map(int, input().split()))

def get_bound(x):
    if x < k-1:
        return [(0, x+1), (x+k+1, 2*k)]
    else:
        return [(x-k+1, x+1)]

blacks = [[0]*(2*k+1) for _ in range(2*k+1)]
for _ in range(n):
    x, y, c = input().split()
    x = int(x)%(2*k)
    y = int(y)%(2*k) if c == 'B' else (int(y)+k)%(2*k)

    for shift in [0, k]:
        for b, t in get_bound((y+shift)%(2*k)):
            for l, r in get_bound((x+shift)%(2*k)):
                blacks[b][l] += 1
                blacks[t][l] -= 1
                blacks[b][r] -= 1
                blacks[t][r] += 1
        
ans = np.max(np.cumsum(np.cumsum(blacks, axis = 1), axis = 0))
print(int(ans))
### BUGGY CODE ###

#!/usr/bin/env python3
n=int(input())
p=list(map(int,input().split()))
ans=0
for i in range(n):
    data=[-1]*2+[n]*2
    now=p[i]
    for j in range(i-1,-1,-1):
        if p[j]>now:
            if data[1] == -1:
                data[1]=j
            else:
                data[0]=j
                break
    for j in range(i+1,n):
        if p[j]>now:
            if data[2] == n:
                data[2]=j
            else:
                data[3]=j
                break

    ans+=((data[1]-data[0])*(data[2]-i)+(data[3]-data[2])*(i-data[1]))*now  
print(ans)
        
            

### FIXED CODE ###

#!/usr/bin/env python3
N=int(input())
p=list(map(int,input().split()))
LL = [0] + [i for i in range(N+1)]
RR = [i+1 for i in range(N+1)] + [N+1]
E = [(v, i+1) for i, v in enumerate(p)]
E.sort()
ans=0
for v, i in E:
  r0 = RR[i]
  r1 = RR[r0]
  l0 = LL[i]
  l1 = LL[l0]
  RR[l0] = r0
  LL[r0] = l0

  ans += ((r1 - r0)*(i-l0)+(r0-i)*(l0 - l1))*v

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

n = int(input())
num_list = list(map(int, input().split()))
dis = n * 10**9

for i in range(1,n):
    a = sum(num_list[:i])
    b = sum(num_list[i:])
    if abs(a-b) < dis:
        dis = abs(a-b)

print(dis)


### FIXED CODE ###

n = int(input())
num_list = list(map(int, input().split()))
total = sum(num_list)
dis = []
a=0

for i in range(n-1):
    a += num_list[i]
    b = total - a
    dis.append(abs(a-b))

print(min(dis))
### BUGGY CODE ###

N = int(input())
T, A = map(int, input().split())
num = T + A
for _ in range(N-1):
  t, a = map(int, input().split())
  while True:
    if num%(t+a) == 0 and (num*t)//(t+a) >= T and (num*a)//(t+a) >= A:
      T = (num*t)//(t+a)
      A = (num*a)//(t+a)
      break
    num += 1
print(num)

### FIXED CODE ###

import math

N = int(input())
x, y = map(int, input().split())
for _ in range(N-1):
  a, b = map(int, input().split())
  # n = max(math.ceil(x/a), math.ceil(y/b))
  na = nb = 0
  if x%a == 0:
    na = x//a
  else:
    na = x//a+1
  if y%b == 0:
    nb = y//b
  else:
    nb = y//b+1
  n = max(na, nb)
  x, y = n*a, n*b
print(x+y)
### BUGGY CODE ###

n,m = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
a = sorted(a)
b=[]
c=[]
for i in range(0, m):
    ib,ic = map(int, input().split(" "))
    b.append(ib)
    c.append(ic)
for i in range(0, m):
    ax = list(map(lambda x: x if c[i] < x else c[i], a[0:b[i]]))
    a[0:b[i]] = ax
    a = sorted(a)
print(sum(a))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
a.sort()
bc=[None]*m
for i in range(m):
    bc[i] = list(map(int, input().split(" ")))
bc.sort(reverse=True, key=lambda x:x[1])
l=[]
for [b,c] in bc:
    l.extend([c]*b)
    if n < len(l):
        break
for i in range(n):
    if len(l) <= i or l[i] <= a[i]:
        break
    a[i] = l[i]
print(sum(a))
### BUGGY CODE ###

n, m = map(int, input().split())
lr = [tuple(map(int, input().split())) for _ in range(m)]

l, r = lr[0]
ans = set()
for k in range(l, r+1):
        ans.add(k)

for i, j in lr[1:]:
    ID = set()
    for k in range(i, j+1):
        ID.add(k)
    ans = ans & ID
print(len(ans))


### FIXED CODE ###

n, m = map(int, input().split())
lr = [tuple(map(int, input().split())) for _ in range(m)]
l = 1
r = n
for i, j in lr:
    l = max(i, l)
    r = min(j, r)
print(max(r-l+1, 0))