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

#!/usr/bin/env python3
from collections import defaultdict
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.buffer.readline
def LI(): return list(map(int, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def LIR(n):
    res = [None] * n
    for i in range(n):
        l, r = map(int, input().split())
        res[i] = (l - 1, r - 1, i)
    return res

#solve
def solve():
    n, q = LI()
    c = LI()
    lr = LIR(q)
    ans = [None] * q
    lr.sort(key=lambda x: x[1])
    dp = [-1] * (max(c) + 1)
    bit = [0] * (n + 1)
    def add(i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= n:
            bit[x - 1] += w
            x += x & -x
        return
    def sum(i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += bit[x - 1]
            x -= x & -x
        return res
    t = 0
    def f(t):
        l, r, j = lr[t]
        xr = sum(r)
        xl = sum(l-1)
        tmp = xr - xl
        ans[j] = tmp
        
    for i in range(n):
        ci = c[i]
        l = dp[ci]
        add(i, 1)
        dp[ci] = i
        if l != -1:
            add(l, -1)
        while t < q and lr[t][1]<= i:
            f(t)
            t += 1
        if t == q:
            break
    for ai in ans:
        print(ai) 
    return


#main
if __name__ == '__main__':
    solve()


### FIXED CODE ###

#!/usr/bin/env python3
from collections import defaultdict
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
def LI(): return list(map(int, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def LIR(n):
    res = [None] * n
    for i in range(n):
        l, r = map(int, input().split())
        res[i] = (l-1, r-1, i)
    return res

#solve
def solve():
    n, q = LI()
    c = LI()
    lr = LIR(q)
    ans = [None] * q
    lr.sort(key=lambda x: x[1])
    dp = [-1] * (max(c) + 1)
    bit = [0] * (n + 1)
    def add(i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= n:
            bit[x - 1] += w
            x += x & -x
        return
    def sum(i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += bit[x - 1]
            x -= x & -x
        return res
    t = 0
    def f(t):
        l, r, j = lr[t]
        xr = sum(r)
        xl = sum(l-1)
        tmp = xr - xl
        ans[j] = tmp
        
    for i in range(n):
        ci = c[i]
        l = dp[ci]
        add(i, 1)
        dp[ci] = i
        if l != -1:
            add(l, -1)
        while t < q and lr[t][1]<= i:
            f(t)
            t += 1
        if t == q:
            break
    for ai in ans:
        print(ai) 
    return


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


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

for i in range(1,1000000000001):
  for j in range(1,1000000000001):
    if i * j == N: 
      L.append(i + j - 2)
print(min(L))


### FIXED CODE ###

import math
N = int(input())
L = []

def f(x):
  n = int(math.sqrt(x))
  for i in range(n,0,-1):
    if x % i == 0:
       return i
result = f(N) + N // f(N) - 2
print(result)
### BUGGY CODE ###



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


counter = 0
for i in range(N-2):
    while a[i] + a[i+1] > x :
        if a[i+1] > 0:
            a[i+1] -=  1
        else :
            a[i] -=  1
        
        counter += 1
       
while a[N-2] + a[N-1] > x:
    if a[N-2] > 0:
        a[N-2] -= 1
    else :
        a[N-1] -= 1
    
    counter += 1

print(counter)

### FIXED CODE ###



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


counter = 0


dif1 = a[N-2] + a[N-1] - x
if dif1 > 0:
        a1 = a[N-2] - dif1
        if a1 > 0:
            a[N-2] -= dif1
            counter  += dif1
        else:
            a[N-1]-= -a1
            a[N-2] = 0
            counter += dif1

for i in range(N-2):
    dif1 = a[i] + a[i+1] - x
    if dif1 > 0:
        a1 = a[i+1] - dif1
        if a1 > 0:
            a[i+1] -= dif1
            counter  += dif1
        else:
            a[i]-= -a1
            a[i+1] = 0
            counter += dif1

       
while a[N-2] + a[N-1] > x:
    if a[N-2] > 0:
        a[N-2] -= 1
    else :
        a[N-1] -= 1
    
    counter += 1

print(counter)
### BUGGY CODE ###

import numpy as np
H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
L = np.zeros((H,W))
R = np.zeros((H,W))
U = np.zeros((H,W))
D = np.zeros((H,W))
for i in range(H):
    for j in range(W):
        if j == 0:
            if S[i][j] == "#":
                L[i,j] = -1
            continue
        if S[i][j] == ".":
            L[i,j] += L[i,j-1]+1
        else:
            L[i,j] = -1
    for j in reversed(range(W)):
        if j == W-1:
            if S[i][j] == "#":
                R[i,j] = -1
            continue
        if S[i][j] == ".":
            R[i,j] += R[i,j+1]+1
        else:
            R[i,j] = -1
for j in range(W):
    for i in range(H):
        if i == 0:
            if S[i][j] == "#":
                U[i,j] = -1
            continue
        if S[i][j] == ".":
            U[i,j] += U[i-1,j]+1
        else:
            U[i,j] = -1
    for i in reversed(range(H)):
        if i == H-1:
            if S[i][j] == "#":
                D[i,j] = -1
            continue
        if S[i][j] == ".":
            D[i,j] += D[i+1,j]+1
        else:
            D[i,j] = -1
su = L+R+U+D
#print(L,R,U,D,sep="\n")
print(int(np.amax(su)+1))


### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.readline
def main():
    H,W = map(int,input().split())
    S = np.array([list(input().rstrip()) for _ in range(H)]) == "."
    L = np.zeros((H,W),dtype=int)
    R = np.zeros((H,W),dtype=int)
    U = np.zeros((H,W),dtype=int)
    D = np.zeros((H,W),dtype=int)
    #[-1]はインデックス内(all 0)なのでエラーを吐かない！
    for i in range(H):
        U[i] = (U[i-1]+1)*S[i]
        D[-i-1] = (D[-i]+1)*S[-i-1]  
    for j in range(W):
        L[:,j] = (L[:,j-1]+1)*S[:,j]
        R[:,-j-1] = (R[:,-j]+1)*S[:,-j-1]

    su = L+R+U+D
    #print(L,R,U,D,sep="\n")
    print(np.amax(su)-3)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

X, Y, A, B, C = map(int ,input().split(' '))
p = list(map(int ,input().split(' ')))
q = list(map(int ,input().split(' ')))
R = set(map(int ,input().split(' ')))

eat = sorted(p, reverse=True)[:X]
eat[len(eat):] = sorted(q, reverse=True)[:Y]

eat.sort()

for r in R:
  if r>eat[0]:
    eat.remove(min(eat))
    eat.append(r)
  
print(sum(eat))

### FIXED CODE ###

X, Y, A, B, C = map(int ,input().split(' '))
p = list(map(int ,input().split(' ')))
q = list(map(int ,input().split(' ')))
R = list(map(int ,input().split(' ')))
 
eat = sorted(p, reverse=True)[:X]
eat[len(eat):] = sorted(q, reverse=True)[:Y]
eat[len(eat):] = R
eat.sort(reverse=True)


print(sum(eat[:X+Y]))
### BUGGY CODE ###

from collections import defaultdict
d, g = list(map(int, input().split()))
pc = [list(map(int, input().split())) for _ in range(d)]

dp = defaultdict(int)
dp[0] = 0
for i, (p, c) in enumerate(pc):
    dp_cur = list(dp.items())
    for p_cur, n_cur in dp_cur:
        for n in range(1, p+1):
            if n < p:
                if dp[p_cur+n*100*(i+1)] == 0:
                    dp[p_cur+n*100*(i+1)] = n_cur+n
                else:
                    dp[p_cur+n*100*(i+1)] = min(dp[p_cur+n*100*(i+1)], n_cur+n)
            else:
                if dp[p_cur+n*100*(i+1)+c] == 0:
                    dp[p_cur+n*100*(i+1)+c] = n_cur+n
                else:
                    dp[p_cur+n*100*(i+1)+c] = min(dp[p_cur+n*100*(i+1)+c], n_cur+n)

# print(dp)
ans = 10**9
v = 0
for p, n in list(dp.items()):
    if p < g:
        continue
    else:
        ans = min(ans, n)
print(ans)


### FIXED CODE ###

d, g = list(map(int, input().split()))
pc = [list(map(int, input().split())) for _ in range(d)]

ans = 10**9
for bit in range(1<<d):
    score = 0
    n = 0
    
    for i in range(d): 
        if bit & 1<<i: # Problems completely answered
            score += pc[i][1] + pc[i][0]*100*(i+1)
            n += pc[i][0]

    if score >= g:
        ans = min(ans, n)
    else: # additional answering
        for i in range(d-1, -1, -1): # answer from high-score problem
            if bit & 1<<i: # already answered completely
                continue
            for j in range(pc[i][0]): # answer to remaining problems
                if score >= g:
                    break
                score += 100*(i+1)
                n += 1
        ans = min(ans, n)

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

from operator import mul
from functools import reduce

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

ans = reduce(mul, a)

if ans > 1000000000000000000:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import collections
import sys


def pow2(x, n):
    ret = 1
    while (n > 0):
        if (n & 1):
            ret *= x
        x *= x
        n = n >> 1
    return ret


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

if 0 in a:
    print(0)
    sys.exit(0)

c = collections.Counter(a)

l = sorted(list(c.keys()))

ans = 1
for num in l:
    ans *= pow2(num, c[num])
    if ans > 1000000000000000000:
        print(-1)
        sys.exit(0)
print(ans)
### BUGGY CODE ###

S=input()
T=input()

import numpy as np
dp=np.zeros((len(S)+1,len(T)+1),dtype=int)
dp[0][0]=0

for i in range(len(S)):
  for j in range(len(T)):
    if S[i]==T[j]:
      dp[i+1][j+1]=dp[i][j]+1
    else:
      dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])

ans=""
i=len(S)
j=len(T)
while i>0 and j>0:
  if dp[i][j]==dp[i-1][j]:
    i-=1
  elif dp[i][j]==dp[i][j-1]:
    j-=1
  else:
    ans=S[i-1]+ans
    i-=1
    j-=1
print(ans)

### FIXED CODE ###

import sys
readline = sys.stdin.readline

S = readline().rstrip()
T = readline().rstrip()

# dp[i][j] = Sをi文字目、Tをj文字目まで進めたときの最長
# S[i] == S[j]のとき
# dp[i][j] = dp[i - 1][j - 1] + 1
# S[i] != S[j]のとき
# dp[i][j] = max(dp[i - 1][j],dp[i][j - 1])

# その際、自分がどこから来たか？を記録する
# dp[i - 1][j] > dp[i][j - 1]であれば
# route[i][j] = (i,j)を記録

dp = [[0] * (len(T) + 1) for i in range(len(S) + 1)]
route = [[(0,0)] * (len(T) + 1) for i in range(len(S) + 1)]

for i in range(len(S)):
  for j in range(len(T)):
    if S[i] == T[j]:
      dp[i + 1][j + 1] = dp[i][j] + 1
      route[i + 1][j + 1] = (i,j)
    else:
      if dp[i][j + 1] > dp[i + 1][j]:
        dp[i + 1][j + 1] = dp[i][j + 1]
        route[i + 1][j + 1] = (i,j + 1)
      else:
        dp[i + 1][j + 1] = dp[i + 1][j]
        route[i + 1][j + 1] = (i + 1,j)

# routeのとびさきの文字を追加していく
x,y = len(S),len(T)
ans = ""
while x != 0 and y != 0:
  if S[x - 1] == T[y - 1]:
    ans += S[x - 1]
  x,y = route[x][y]

print(ans[::-1])
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Thu Jun 13 14:27:40 2019

@author: YudNK
"""
import bisect

N, Q = map(int, input().split())
X = []
for i in range(N):
    s, t, x = map(int, input().split())
    X.append([s - x, t - x, x])
D = [[i, int(input())] for i in range(Q)]
X.sort(key = lambda x:x[2])
ans = [-1 for i in range(Q)]
for i in X:
    m = i[0]
    n = i[1]
    xi = i[2]
    keys = [r[1] for r in D]
    it = bisect.bisect_left(keys, m)
    while it != len(D):
        if D[it][1] >= n:
            break
        ans[D[it][0]] = xi
        D.pop(it)
[print(i) for i in ans]

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 15 16:58:00 2019

@author: YudNK
"""
import bisect as bs

N, Q = map(int, input().split())
E = []
for i in range(N):
    s, t, x = map(int, input().split())
    a = [s - x, t - x, x] #イベント
    E.append(a)
E.sort(key = lambda x: x[2])
D = []
for i in range(Q):
    D.append(int(input()))

ans = [-1]*Q
check = [-1]*Q

for e in E:
    l = bs.bisect_left(D, e[0])
    r = bs.bisect_left(D, e[1])
    while l < r:
        if check[l] == -1:  
            ans[l] = e[2]
            check[l] = r
            l += 1
        else:
            l = check[l]
        
[print(i) for i in ans]
### BUGGY CODE ###

# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W, K = lr()
X1, Y1, X2, Y2 = lr()
X1 -= 1; Y1 -= 1; X2 -= 1; Y2 -= 1
C = [sr() for _ in range(H)]
graph = [[] for _ in range((H*W)*4)]  # 0-indexed
for i in range(H):
    for j in range(W):
        pos = (W*i + j)*4
        left = False; right = False
        if C[i][j] == '@':
            continue
        if j == 0: left = True
        if j == W-1: right = True
        for con, dir in [(0, -4*W), (1, 4), (2, 4*W), (3, -4)]:
            # 0を上、1を右
            if left and con == 3: continue
            if right and con == 1: continue
            if 0 <= pos + con + dir < H*W*4:
                graph[pos + con].append(((pos+con+dir), 1 / K))
        for con in range(4):
            graph[pos+con].append(((pos+(con+1)%4), K+1))
            graph[pos+con].append(((pos+(con-1)%4), K+1))

INF = 10 ** 10

def dijkstra(start):
    dist = [INF] * H * W * 4
    que = [(0, start)]
    dist[start] = 0
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for next, dis in graph[prev]:
            if dis == K+1:
                d1 = -(-d//1)
            else:
                d1 = d + dis
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
    return dist

start = (W*X1+Y1)*4
dist = dijkstra(start)
goal = (W*X2 + Y2)*4
answer = min(dist[goal:goal+4])
answer = int(-(-answer//1))
print(answer if answer != INF else -1)


### FIXED CODE ###

# coding: utf-8
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W, K = lr()
SX, SY, GX, GY = lr()
SX -= 1; SY -= 1; GX -= 1; GY -= 1
pond = [sr() for _ in range(H)]
INF = 10 ** 10
dist = [[INF] * W for _ in range(H)]
dist[SX][SY] = 0
que = deque([(0, SX, SY)])
UDLR = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while que:
    d, px, py = que.popleft()
    if px == GX and py == GY:
        print(d); exit()
    if dist[px][py] < d:
        continue
    nd = d + 1
    for dx, dy in UDLR:
        nx = px + dx; ny = py + dy
        for _ in range(K):
            if not (0 <= nx < H) or not (0 <= ny < W) \
                    or dist[nx][ny] < nd or pond[nx][ny] == '@':
                break
            if dist[nx][ny] > nd:
                que.append((nd, nx, ny))
                dist[nx][ny] = nd
            nx += dx; ny += dy

print(-1)
### BUGGY CODE ###

cnt = 0
S = input()  
for left in range(len(S)-3):
    for right in range(left+3,len(S)):
        if int(S[left:right+1]) % 2019 == 0:
            cnt += 1
print(cnt)

### FIXED CODE ###

from collections import Counter

S = [int(i) for i in input()]
S.reverse()
lst = []
_sum = 0

for i in range(len(S)):
    _sum = (_sum + S[i] * pow(10,i,2019)) % 2019
    lst.append(_sum)
    
C = Counter(lst)    
ans = C[0]

for i in C:
    ans += C[i]*(C[i]-1)//2
print(ans)
### BUGGY CODE ###

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

list_cake_1 = list(map(int, input().split()))
list_cake_2 = list(map(int, input().split()))
list_cake_3 = list(map(int, input().split()))

list_cake_1 = sorted(list_cake_1, reverse=True)
list_cake_2 = sorted(list_cake_2, reverse=True)
list_cake_3 = sorted(list_cake_3, reverse=True)


list_total_sum = [list_cake_1[i]+list_cake_2[j]+list_cake_3[k] for i in range(X) for j in range(Y) for k in range(Z) if (i+1)*(j+1)*(k+1) <= K]

list_total_sum = sorted(list_total_sum, reverse=True)

for i in range(K):
	print(list_total_sum[i])

### FIXED CODE ###

import sys

input = sys.stdin.readline

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

list_cake_1 = list(map(int, input().split()))
list_cake_2 = list(map(int, input().split()))
list_cake_3 = list(map(int, input().split()))

list_cake_1 = sorted(list_cake_1, reverse=True)
list_cake_2 = sorted(list_cake_2, reverse=True)
list_cake_3 = sorted(list_cake_3, reverse=True)

list_total_sum = []

for i, cake_1 in enumerate(list_cake_1, 1):
	for j, cake_2 in enumerate(list_cake_2, 1):
		for k, cake_3 in enumerate(list_cake_3, 1):
			if i*j*k > K:
				break
			list_total_sum.append(cake_1 + cake_2 + cake_3)

for element in sorted(list_total_sum, reverse=True)[:K]:
	print(element)
### BUGGY CODE ###

a = int(input())
b = 1
c = []
for i in range(a):
    c.append(b)
    b += 1

D = 0
for I in range(a):
    if c[I]%3 == 0:
        c.remove(c[I])
        c.insert(I,'a')
    
    elif c[I]%5 == 0:
        c.remove(c[I])
        c.insert(I,'a')
        
    else:
        D = D + c[I]
print(D)

### FIXED CODE ###

a = int(input())
d = 1
D = 0
for I in range(a):
    if d%3 == 0:
        d += 1
    
    elif d%5 == 0:
        d += 1
        
    else:
        D = D + d
        d += 1
print(D)
### BUGGY CODE ###

import collections, queue, sys
n, k =  map(int, input().split())
m = 10**9+7
edges = collections.defaultdict(list)
q = []
ans = 1

for i in range(n-1):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)

j = 1
for i in edges[1]:
    q.append((i, 1))
    if k - j <= 0:
        print(0)
        sys.exit()
    ans = ans%m * (k - j)%m
    j+=1

while q:
    j = 2
    node = q[0][0]
    prenode = q[0][1]
    q.pop(0)
    for i in edges[node]:
        if not i == prenode:
            q.append((i, node))
            if k - j <= 0:
                print(0)
                sys.exit()
            ans = ans%m * (k - j)%m
            j+=1
print((ans*k)%m)

### FIXED CODE ###

import collections, queue, sys
n, k =  map(int, input().split())
m = 10**9+7
edges = collections.defaultdict(list)
q = queue.Queue()
preq = queue.Queue()
ans = 1

for i in range(n-1):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)

j = 1
for i in edges[1]:
    q.put(i)
    preq.put(1)
    if k - j <= 0:
        print(0)
        sys.exit()
    ans = ans%m * (k - j)%m
    j+=1

while not q.empty():
    j = 2
    node = q.get()
    prenode = preq.get()
    for i in edges[node]:
        if not i == prenode:
            q.put(i)
            preq.put(node)
            if k - j <= 0:
                print(0)
                sys.exit()
            ans = ans%m * (k - j)%m
            j+=1
print((ans*k)%m)
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
	l = list(map(int,input().split()))
	A.append([i-1 for i in l])
match_num = [0 for i in range(N)]
match_dict = {}
idx = 0
for i in range(N-1):
	for j in range(i+1, N):
		match_dict[(i,j)] = idx
		idx += 1
M = idx
edge = [[] for i in range(M)]
parent = [[] for i in range(M)]
for i in range(N):
	for j in range(N-2):
		a = A[i][j]
		a_nxt = A[i][j+1]
		x,y = min(i,a), max(i,a)
		z,w = min(i,a_nxt), max(i,a_nxt)
		edge[match_dict[(x,y)]].append(match_dict[(z,w)])
		parent[match_dict[(z,w)]].append(match_dict[(x,y)])
finish = [False for i in range(M)]
candidate = [i for i in range(M) if len(parent[i]) == 0]
day = 0
while len(candidate) > 0:
	new_candidate = []
	for c in candidate:
		if finish[c]:
			continue
		finish[c] = True
		for e in edge[c]:
			if finish[e]:
				continue
			if all([finish[p] for p in parent[e]]):
				new_candidate.append(e)
	day += 1
	candidate = new_candidate

all_finished = all(finish)
if all_finished:
	print(day)
else:
	print(-1)

### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
	l = list(map(int,input().split()))
	A.append([i-1 for i in l])
match_num = [0 for i in range(N)]
match_dict = {}
idx = 0
for i in range(N-1):
	for j in range(i+1, N):
		match_dict[(i,j)] = idx
		idx += 1
M = idx
edge = [[] for i in range(M)]
parent = [[] for i in range(M)]
for i in range(N):
	for j in range(N-2):
		a = A[i][j]
		a_nxt = A[i][j+1]
		x,y = min(i,a), max(i,a)
		z,w = min(i,a_nxt), max(i,a_nxt)
		m1 = match_dict[(x,y)]
		m2 = match_dict[(z,w)]
		edge[m1].append(m2)
		parent[m2].append(m1)
finish = [False for i in range(M)]
candidate = [i for i in range(M) if len(parent[i]) == 0]
depth = [-1 for i in range(M)]


day = 0
while len(candidate) > 0:
	new_candidate = []
	for c in candidate:
		finish[c] = True
		for e in edge[c]:
			parent[e].remove(c)
			if len(parent[e]) == 0:
				new_candidate.append(e)
		edge[c] = []
	candidate = new_candidate
	day += 1
print(day if all(finish) else -1)
### BUGGY CODE ###

R = [(int(input()), i) for i in range(int(input()))]
print(max([max(y-x for y, j in R[i+1:]) for x, i in R[:-1]]))

### FIXED CODE ###

R = [int(input()) for i in range(int(input()))]
maxp = R[1] - R[0]
minv = R[0]
for r in R[1:]:
    maxp = max(maxp, r-minv)
    minv = min(minv, r)
print(maxp)
### BUGGY CODE ###

import sys
import numpy as np
def input(): return sys.stdin.readline().rstrip()


def main():
    h, w = map(int, input().split())
    A = np.array([list(map(int, input().split()))
                  for i in range(h)], dtype=int)
    B = np.array([list(map(int, input().split()))
                  for i in range(h)], dtype=int)
    abss = np.abs(A-B)
    kmax = 400
    dp = np.zeros((h, w, kmax), dtype=int)
    dp[0][0][abss[0][0]] = 1
    for i in range(h):
        for j in range(w):
            for k in range(kmax):
                if dp[i][j][k] == 1:
                    if i != h-1:
                        dp[i+1][j][abs(k-abss[i+1][j])] = 1
                        if k+abss[i+1][j] < kmax:
                            dp[i+1][j][k+abss[i+1][j]] = 1
                    if j != w-1:
                        dp[i][j+1][abs(k-abss[i][j+1])] = 1
                        if k+abss[i][j+1] < kmax:
                            dp[i][j+1][k+abss[i][j+1]] = 1
    for k in range(kmax):
        if dp[-1][-1][k] == 1:
            print(k)
            break


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()


def main():
    h, w = map(int, input().split())
    A = [list(map(int, input().split()))for i in range(h)]
    B = [list(map(int, input().split()))for i in range(h)]
    abss = [[abs(A[i][j]-B[i][j])for j in range(w)] for i in range(h)]
    kmax = 6400
    dp = [[[0]*kmax for j in range(w)]for i in range(h)]
    dp[0][0][abss[0][0]] = 1
    for i in range(h):
        for j in range(w):
            for k in range(kmax):
                if dp[i][j][k] == 1:
                    if i != h-1:
                        dp[i+1][j][abs(k-abss[i+1][j])] = 1
                        if k+abss[i+1][j] < kmax:
                            dp[i+1][j][k+abss[i+1][j]] = 1
                    if j != w-1:
                        dp[i][j+1][abs(k-abss[i][j+1])] = 1
                        if k+abss[i][j+1] < kmax:
                            dp[i][j+1][k+abss[i][j+1]] = 1
    for k in range(kmax):
        if dp[-1][-1][k] == 1:
            print(k)
            break


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

n = int(input())
li = list(map(int,input().split()))
cnt = 0

def triangle(a,b,c):
    if (a < b+c) & (b < a+c) & (c < a+b):
        return True
    else:
        return False

for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            if triangle(li[i],li[j],li[k]):
                cnt += 1
print(cnt)

### FIXED CODE ###

import bisect

n = int(input())
li = list(map(int,input().split()))
li2 = sorted(li)
cnt = 0

for i in range(n-2):
    for j in range(i+1,n-1):
        cnt += bisect.bisect_left(li2,li2[i]+li2[j]) - (j+1) 
print(cnt)