Harryxun/stf_run huggingface dataset:
import itertools
N, M, Q = map(int,input().split())
List = [list(map(int, input().split())) for i in range(Q)]
l_tensu = [0]
for subset in itertools.combinations(A_full, N):
    tensu = 0

    A = list(subset)
    for i in range(Q):
        a = List[i][0] - 1
        b = List[i][1] - 1
        c = List[i][2]
        d = List[i][3]
        if (A[b] - A[a] == c):
            tensu += d
    l_tensu.append(tensu)
print(max(l_tensu))

### FIXED CODE ###

import itertools
N, M, Q = map(int,input().split())
List = [list(map(int, input().split())) for i in range(Q)]

A_full = [i for i in range(1,M+1)]

l_tensu = 0
for subset in itertools.combinations_with_replacement(A_full, N):
    tensu = 0

    A = list(subset)
    for i in range(Q):
        a = List[i][0] - 1
        b = List[i][1] - 1
        c = List[i][2]
        d = List[i][3]
        if (A[b] - A[a] == c):
            tensu += d
    if(tensu > l_tensu):
        l_tensu = tensu
    
print(l_tensu)
n = int(input())
a = list(map(int, input().split()))

a_sorted=sorted(a)
ans = 1

if a_sorted[len(a_sorted)-1] == 0:
  ans = 0
else:
  for i in range(len(a_sorted)):
    ans = ans * a_sorted[i]
    if ans > 1000000000000000000:
      ans = -1
      break

print(ans)

### FIXED CODE ###

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

print(a*b)
N = int(input())
ABn = [ list(map(int,input().split(' '))) for _ in range(N) ]
ABn.sort(key=lambda x: x[1])

count_time = 0
for AB in ABn:
    count_time += AB[0]
    if count_time <= AB[1]:
        continue
    else:
        print('No')
        exit(1)
print('Yes')

### FIXED CODE ###

N = int(input())
ABn = [ list(map(int,input().split(' '))) for _ in range(N) ]
ABn.sort(key=lambda x: x[1])

count_time = 0
for AB in ABn:
    count_time += AB[0]
    if count_time <= AB[1]:
        continue
    else:
        print('No')
        exit()
print('Yes')
def back_home(r):
    l = dict()
    for i in r:
        if i in l:
            l[i]=int(l[i])+1
        else:
            l[i]=1
    if (len(l)==1):
        return('NO')
    elif(len(l)==2):
        if (len(l['S'])>0 and len(l['N']>0)):
            return ("yes")
        elif(len(l['E'])>0 and len(l['W']>0)):
            return("yes")
        else:
            return("NO")
    elif(len(l)==3):
        return("NO")
    else:
        return("YES")
        
back_home(S):

### FIXED CODE ###

def back_home():
    S=input()
    if((('S'in S) and ('N' in S)) and not (('E' in S) or  ('W' in S))):
        print('Yes')
    elif(not (('S' in S) or ('N'  in S)) and (('E' in S) and ('W' in S))):
        print("Yes")
    elif((('S'in S) and ('N' in S)) and (('E' in S) and ('W' in S))):
        print("Yes")
    else:
        print("No")
          
back_home()
import sys
read = sys.stdin.buffer.read # 全読み込み
readline = sys.stdin.buffer.readline # 一行読み込み
readlines = sys.stdin.buffer.readlines # 一行ずつ全読み込み
sys.setrecursionlimit(10**7) # 再帰限界変更（デフォルトは1000）

"""
# 文字列（数値変換も含む）
n = readline().rstrip() # １行に１文字列のみ
lis = readline().rstrip().split() # # １行に複数の文字列

# 数値（文字変換も含む）
n = int(readline().rstrip()) # １行に数値１個のみ
a, b, c = map(int,readline().rstrip().split()) # １行に複数の数値
A = list(map(int,readline().rstrip().split()))  # １行に複数の数値（リスト受け取り）
lis = [readline().rstrip().split() for _ in range(n)] # １行に複数の数値(m個)かつ、n行続く場合（出力は二次元リスト：[['1', '2'], ['4', '5']]）

# dとAの行が交互に並んでいる場合
s = sys.stdin.readlines()
n, k=map(int, s[0].split())
d=[]
A=[]
for i in s[1:2*k:2]:
    d.append(int(i))
for i in s[2:2*k+1:2]:
    A.append(list(map(int, i.split())))
"""

a,b,c,d=map(int,readline().rstrip().split())

import math
f = math.gcd(a,b) # 最大公約数
f2 = a*b // f # 最小公倍数

# b以下で条件を満たす個数
shou1=b//c
shou2=b//d
shou3=b//f2
num_b=b-(shou1+shou2-shou3)

# a-1以下で条件を満たす個数
shou4=(a-1)//c
shou5=(a-1)//d
shou6=(a-1)//f2
num_a=(a-1)-(shou4+shou5-shou6)

print(num_b-num_a)

### FIXED CODE ###



import sys
read = sys.stdin.buffer.read # 全読み込み
readline = sys.stdin.buffer.readline # 一行読み込み
readlines = sys.stdin.buffer.readlines # 一行ずつ全読み込み
sys.setrecursionlimit(10**7) # 再帰限界変更（デフォルトは1000）

"""
# 文字列（数値変換も含む）
n = readline().rstrip() # １行に１文字列のみ
lis = readline().rstrip().split() # # １行に複数の文字列

# 数値（文字変換も含む）
n = int(readline().rstrip()) # １行に数値１個のみ
a, b, c = map(int,readline().rstrip().split()) # １行に複数の数値
A = list(map(int,readline().rstrip().split()))  # １行に複数の数値（リスト受け取り）
lis = [readline().rstrip().split() for _ in range(n)] # １行に複数の数値(m個)かつ、n行続く場合（出力は二次元リスト：[['1', '2'], ['4', '5']]）

# dとAの行が交互に並んでいる場合
s = sys.stdin.readlines()
n, k=map(int, s[0].split())
d=[]
A=[]
for i in s[1:2*k:2]:
    d.append(int(i))
for i in s[2:2*k+1:2]:
    A.append(list(map(int, i.split())))
"""

a,b,c,d=map(int,readline().rstrip().split())

import fractions
f = fractions.gcd(c,d) # 最大公約数
f2 = c*d // f # 最小公倍数

# b以下で条件を満たす個数
shou1=b//c
shou2=b//d
shou3=b//f2
num_b=b-(shou1+shou2-shou3)

# a-1以下で条件を満たす個数
shou4=(a-1)//c
shou5=(a-1)//d
shou6=(a-1)//f2
num_a=(a-1)-(shou4+shou5-shou6)

print(num_b-num_a)
a=int(input())
b=int(input())
print(int(a+b/2))


### FIXED CODE ###

(a,b)=input().split()
print(int(int(a)+int(b)/2))
n,x=map(int,input().split())
L=list(map(int,input().split()))
p=0
ans=1
for i in range(n):
        p+=L[i]
        ans+=1 if p<=x else continue
print(ans)

### FIXED CODE ###

import bisect
n,x=map(int,input().split())
L=list(map(int,input().split()))
a=[0]*(n+1)
for i in range(1,n+1):
    a[i]=a[i-1]+L[i-1]
for i in range(n+1):
    if x==a[i]:
        print(bisect.bisect_right(a,x))
        exit()
print(bisect.bisect_left(a,x))
import math
n,d=input().split()
n=int(n)
d=int(d)
def combinations(n, r):
    return math.factorial(n)/(math.factorial(n-r)*math.factorial(r))
x=[]
if d==1:
  count=combinations(n,2)
  int(count)
else:
  for i in range(n):
    xa=[int(s) for s in input().split()]
    x.append(xa)
  a=[]
  for i in range(n-1):
    for j in range(i+1,n):
      t=[]
      for k in range(d):
        c=(x[i][k]-x[j][k])*(x[i][k]-x[j][k])
        t.append(c)
        if k==d-1:
          a.append(sum(t))
  answer=list(map(lambda x:pow(x,1/2),a))
  count=0
  for l in range(n):
    if answer[l].is_integer()==True:
      count=count+1
      print(count)
print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys

N, D = map(int, input().split())
s_lines = sys.stdin.readlines()

ans = 0
X_list_list = []
for s in s_lines:
    new_list = list(map(int, s.split()))
    for i in range(len(X_list_list)):
        sum_num = float(0)
        for idx, ite in enumerate(X_list_list[i]):
            sum_num += (new_list[idx] - ite) ** 2
        if pow(sum_num, 0.5).is_integer():
            ans += 1
    X_list_list.append(new_list)

print(ans)
a,b=map(int,input().split())
s=str(input())
s[b-1]=s[b-1].lower()
print(s)

### FIXED CODE ###

a,b=map(int,input().split())
s=list(input())
s[b-1]=(s[b-1]).lower()
print("".join(s))
a,b,c = map(str,input(),split())
A = a[0].upper()
B = b[0].upper()
C = c[0].upper()
X = A+B+C
X = X.strip()
print(X)

### FIXED CODE ###

l = list(input().split())
print(l[0][0].upper() + l[1][0].upper() + l[2][0].upper())
import numpy as np

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

cranes = np.arange(X) * 2
turtles = (np.arange(X)*4).reshape(-1,1)

total = cranes + turtles

if np.any(total == Y):
  print('Yes')
else:
  print('No)
                    
 

### FIXED CODE ###

import numpy as np

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

cranes = np.arange(X+1) * 2
turtles = (np.arange(X+1)*4).reshape(-1,1)

total = np.diag(np.fliplr(cranes + turtles))


if np.any(total == Y):
  print('Yes')
else:
  print('No')
N,Q = map(int,input().split())
S = input()
count_l=[]
for i in range(Q):
    a,b = map(int,input().split())
    flag=False
    counting=0
    if b==N:
        l=S[a-1:]
    else:
        l=S[a-1:b]
    #print(l)
    counting = l.count("AC")
    """for ii in l:
        #print(ii)
        if ii=="A":
            flag=True
        elif ii=="C" and flag==True:
            counting+=1
            flag=False"""
    count_l.append(counting)
for i in count_l:
    print(i)


### FIXED CODE ###

b = input()
if b=="A":
    print("T")
elif b=="T":
    print("A")
elif b=="G":
    print("C")
elif b=="C":
    print("G")
N = int(input())
if N%2 == 1: print("No")
else:
    n=int(N/2)
    S = input()
    if S[:n]==s[n:] :print("Yes")
    else:print("No")

### FIXED CODE ###

N = int(input())
S = input()
if N%2 == 1: print("No")
else:
    n=int(N/2)
    if S[:n]==S[n:] :print("Yes")
    else:print("No")
import sys
import math
import collections
from collections import deque
#n = int(input())
n, m = map(int, sys.stdin.readline().split())
#s = input()
#x = list(map(int, sys.stdin.readline().split()))

a = math.factorial(n) // (math.factorial(n - 2) * 2)
b = math.factorial(m) // (math.factorial(m - 2) * 2)

print(a+b)


### FIXED CODE ###

import sys
import math
import collections
from collections import deque
#n = int(input())
n, m = map(int, sys.stdin.readline().split())
#s = input()
#x = list(map(int, sys.stdin.readline().split()))

if n <= 1:
    a = 0
else:
    a = math.factorial(n) // (math.factorial(n - 2) * 2)

if m <= 1:
    b = 0
else:
    b = math.factorial(m) // (math.factorial(m - 2) * 2)

print(a+b)
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)

tmp = 0
num = 0
for i in range(1, n):
    if(a[i] >= a[0]//2):
        aa = a[0]-a[i]
        if(aa >= tmp):
            tmp = aa
            num = a[i]
            
    else:
        if(a[i] >= tmp):
            tmp = aa
            num = a[i]

print(a[0], num)

### FIXED CODE ###

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

tmp = a[0]//2
s = 10**18
num = 0
for i in range(1, n):
    if(abs(tmp-a[i]) < s):
        s = abs(tmp-a[i])
        num = a[i]

print(a[0], num)
print((sum(int(input()))+1)//2)

### FIXED CODE ###

print((sum(map(int,input().split()))+1)//2)
def f(j,k):
  tmp=j-C[k]
  if tmp>M[k]: M[k]=tmp
  return

while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  M = [0]*(h+1)
  a=[0]*w
  for i in range(h):
    x = raw_input()
    b=[0]*w
    sp=-1
    C = [-1]*(h+1)
    for j in range(w):
      if x[j]=="*": c=0
      else: c=a[j]+1
      b[j]=c
      dw=c-sp
      if dw>0: C[sp+1:c+1]=[j]*dw
      elif dw<0:
        for k in range(c+1,sp+1): f(j,k)
        C[c+1:sp+1]=[-1]*(-dw)
      sp=c
    for k in range(1,sp+1):
      if C[k]>=0: M[k]=max(M[k],w-C[k])
    a=b
  s=max([M[i]*i for i in range(h+1) if M[i]>0])
  print s

### FIXED CODE ###

while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  M = [0]*(h+1)
  a=[0]*w
  for i in range(h):
    x = raw_input()
    b=[0]*w
    sp=-1
    C = [-1]*(h+1)
    for j in range(w):
      if x[j]=="*": c=0
      else: c=a[j]+1
      b[j]=c
      dw=c-sp
      if dw>0: C[sp+1:c+1]=[j]*dw
      elif dw<0:
        for k in range(c+1,sp+1): M[k]=max(M[k],j-C[k])
        C[c+1:sp+1]=[-1]*(-dw)
      sp=c
    for k in range(1,sp+1):
      if C[k]>=0: M[k]=max(M[k],w-C[k])
    a=b
  s=max([a*b for a,b in zip(M, range(h+1))])
  print s
n,x= input().split()
b_list= list(map(int, input().split()))
temp = 0
counter = 0
for i in range(n):
    if (temp<=int(x)):
        counter +=1
    temp += b_list[i]

print(counter)

### FIXED CODE ###

n,x= input().split()
b_list= list(map(int, input().split()))
temp = 0
counter = 1
for i in range(int(n)):
    temp += b_list[i]
    if (temp<=int(x)):
        counter +=1
    else:
        break

print(counter)
n = input()
for i in n:
    a = list(map(int,input().split()))
a.sort(reverse = True)
Bob = sum(a[1::2])
Alice = sum(a[0::2])
print(Alice - Bob)



### FIXED CODE ###

input()
a = list(map(int,input().split()))
a.sort(reverse = True)
print(sum(a[0::2]) - sum(a[1::2]))
import itertools 
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]

l = 0
c = 0

for v in itertools.permutations(xy):
  for i in range(len(v)-1):
    l += ((v[i][0] - v[i+1][0])**2 + v[i][1] - v[i+1][1])**2)**0.5
  c += 1
  
print(l/c)

### FIXED CODE ###

import itertools 
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]

l = 0
c = 0

for v in itertools.permutations(xy):
  for i in range(len(v)-1):
    l += ((v[i][0] - v[i+1][0])**2 + (v[i][1] - v[i+1][1])**2)**0.5
  c += 1

print(l/c)
# 入力
N, M = [int(i) for i in input().split()]

# カウント用の配列
count = [0] * (M-1)

for i in range(N):  # 入力しながら
    _, *A = [int(i)-1 for i in input().split()]
    for j in A:     # 数える
        count[j] += 1

res = 0
for i in count:
    if i == N: res += 1

print(res)

### FIXED CODE ###

# 入力
N, M = [int(i) for i in input().split()]

# カウント用の配列
count = [0] * M

for i in range(N):  # 入力しながら
    _, *A = [int(i)-1 for i in input().split()]
    for j in A:     # 数える
        count[j] += 1

res = 0
for i in count:
    if i == N: res += 1

print(res)
n = int(input())
a = list(map(int,input().split()))
memo = [0 for i in range(1000001)]
def f(i):
    if memo[i]:
        return memo[i]
    if i==0 or i%2==1:
        return 0
    else:
        memo[i] = 1+f(i//2)
        return memo[i]
ans = 0
for a_ in a:
    ans += f(a_)
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
memo = {}
def f(i):
    if i in memo.keys():
        return memo[i]
    if i==0 or i%2==1:
        return 0
    else:
        memo[i] = 1+f(i//2)
        return memo[i]
ans = 0
for a_ in a:
    ans += f(a_)
print(ans)
n,t=input().split()
n=int(n)
t=int(t)
res=10000
for i in range(n):
  s=input().split()
  if int(s[1])<=T:
    res=min(res,int(s[0]))
if res==10000:
  print("TLE")
else:
  print(res)

### FIXED CODE ###

n,t=input().split()
n=int(n)
t=int(t)
res=10000
for i in range(n):
  s=input().split()
  if int(s[1])<=t:
    res=min(res,int(s[0]))
if res==10000:
  print("TLE")
else:
  print(res)
S=int(input())

def f(n): 
      
    # single line to find factorial 
    return 1 if (n==1 or n==0) else n * factorial(n - 1);

possibles=0
biggest_sub=S//3
for i in range(1,biggest_sub+1):
	left=S-3*i
	possibles+=(f(left+i-1)/(f(i-1)*f(left)))
n=10**9+7
print(possibles%n)

### FIXED CODE ###

#import sys
#input = sys.stdin.readline
Q = 10**9+7
def cmb(n,r):
    if n-r < r: r = n-r
    if r == 0: return 1
    denominator = 1                       #分母
    numerator = 1                         #分子
    for i in range(r):
        numerator *= n-i
        numerator %= Q
        denominator *= i+1
        denominator %= Q
    return numerator*pow(denominator, Q-2, Q)%Q
 
def main():
    S = int( input())
    ans = 0
    for i in range(1, S//3+1):
        t = S - i*3
        ans += cmb(t+i-1,i-1)
        ans %= Q
    print(ans)
        
if __name__ == '__main__':
    main()
import itertools
import math
import sys

n = int(input())
v = list(map(int, input().split()))
if len(set(v)) == 1:
    print(n // 2)
else:
    odd_cnt = [0] * 10 ** 5
    even_cnt = [0] * 10 ** 5
    for i in range(len(v)):
        if i % 2 == 0:
            even_cnt[v[i]] += 1
        else:
            odd_cnt[v[i]] += 1
    odd = odd_cnt.index(max(odd_cnt))
    even = even_cnt.index(max(even_cnt))
    ans = 0
    for i in range(len(v)):
        if i % 2 == 0:
            if v[i] != even:
                ans += 1
        else:
            if v[i] != odd:
                ans += 1
    print(ans)


### FIXED CODE ###

import itertools
import math
import sys
from collections import Counter

n = int(input())
v = list(map(int, input().split()))
e = Counter(v[0::2]).most_common()
o = Counter(v[1::2]).most_common()
if len(e) == 1 and len(o) == 1:
    if e[0][0] == o[0][0]:
        print(n // 2)
    else:
        print(0)
elif len(e) == 1:
    if e[0][0] != o[0][0]:
        print(n - e[0][1] - o[0][1])
    else:
        print(n - max(e[0][1] + o[0][1], o[1][1]))
elif len(o) == 1:
    if e[0][0] != o[0][0]:
        print(n - e[0][1] - o[0][1])
    else:
        print(n - max(e[0][1] + o[0][1], e[1][1]))
else:
    if e[0][0] != o[0][0]:
        print(n - e[0][1] - o[0][1])
    else:
        print(n - max(e[0][1] + o[1][1], e[1][1] + o[0][1]))
def dfs_v(u):
  color[u] = 1
  t += 1
  d[u] = t
  for v in range(n):
    if M[u][v] == 0 and color[v] == 0:
      dfs_v(v)
  color[u] = 2
  t += 1
  f[u] = t

def dfs():
  color = [0 for i in range(n)]
  t = 0
  for u in range(n):
    if color[u] == 0:
      dfs_v(u)
  for u in range(n):
    print u+1, d[u], f[u]

n = input()

color = [0 for i in range(100)]
d = [0 for i in range(100)]
f = [0 for i in range(100)]
M = [0 for i in range(n)]0 for j in range(n)]

for i in range(n):
  u, k = map(int, raw_input().split())
  for j in range(k):
   v = input()
   M[u-1][v-1] = 1

dfs()
    

### FIXED CODE ###

n = int(raw_input())
 
d = [0 for i in range(n)]
f = [0 for i in range(n)]
G = [0 for i in range(n)]
M = [[0 for i in range(n)] for j in range(n)]
col = [0 for i in range(n)]
t = [0]
 
def DFS_visit(u):
    col[u] = 1
    t[0] += 1
    d[u] = t[0]
    for v in range(n):
        if M[u][v] == 1 and col[v] == 0:
            DFS_visit(v)
    col[u] = 2
    t[0] += 1
    f[u] = t[0]
 
def DFS():
    for u in range(n):
        if col[u] == 0:
            DFS_visit(u)
    for u in range(n):
        print'{0} {1} {2}'.format(u+1, d[u], f[u])
     
for i in range(n):
    X = map(int, raw_input().split())
    for j in range(X[1]):
        M[X[0]-1][X[2+j]-1] = 1
 
DFS()
while True:
    n = int(input())
    if n == 0:
        exit()
    score = []
    for i in range(n):
        score.append(int(input()))
    print((sorted(score)[1:-1])//(n-2))

### FIXED CODE ###

while True:
    n = int(input())
    if n == 0:
        exit()
    score = []
    for i in range(n):
        score.append(int(input()))
    print(sum(sorted(score)[1:-1])//(n-2))
print(oteagedesita)

### FIXED CODE ###

n,ma,mb = map(int,input().split())
a = []
b = []
c = []
for i in range(n):
    aa,bb,cc = map(int,input().split())
    a.append(aa)
    b.append(bb)
    c.append(cc)

inf = 10**18
dp = [[[inf]*(411) for j in range(411)] for i in range(n+1)]
for i in range(n+1):
    dp[i][0][0] = 0
for i in range(n):
    for j in range(400):
        for k in range(400):
            if dp[i][j][k] == inf:continue
            dp[i+1][j][k] = min(dp[i+1][j][k],dp[i][j][k])
            dp[i+1][j+a[i]][k+b[i]] = min(dp[i+1][j+a[i]][k+b[i]],dp[i][j][k]+c[i])

ans = 10**18
for j in range(1,401):
    for k in range(1,401):
        if ma*k == mb*j:
            ans = min(ans,dp[n][j][k]) 
if ans == 10**18:
    print(-1)
else:
    print(ans)
a,b=map(int,input().split())
print(a*b9)

### FIXED CODE ###

a,b=map(int,input().split())
print(a*b)
n = int(input())
lists = list(int(input()) for i in range(n))
number = 1
for j in lists:
  if number == 0:
    number = 0
    break
  number = number * j
  if number > 10**18:
    number = -1
    break
print(number)

### FIXED CODE ###

n = int(input())
lists = list(map(int, input().split()))
number = 1
if 0 in lists:
  number = 0
else:
  for j in lists:
    number = number * j
    if number > 10 ** 18:
      number = -1
      break
print(str(number))
def f(a,b):
    if b:return f(b,a%b)
    return a
n,k=map(int,input().split())
a=list(map(int,input().split()))
p=f(a[0],a[1])
for i in a[1:]:
    p=f(p,i)
print('POSSIBLE' if p==f(p,k) and k<=max(a) else 'IMPOSSIBLE')

### FIXED CODE ###

def f(a,b):
    if b:return f(b,a%b)
    return a
n,k=map(int,input().split())
a=list(map(int,input().split()))
if n==1:
    print('POSSIBLE' if k==a[0] else 'IMPOSSIBLE')
    exit()
p=f(a[0],a[1])
for i in a[1:]:
    p=f(p,i)
print('POSSIBLE' if p==f(p,k) and k<=max(a) else 'IMPOSSIBLE')
import numpy as np
import math
import sys
sys.setrecursionlimit(10000000)
from bisect import bisect_left, bisect_right
 
def main():
    N = int(input())
    L = [int(c) for c in input().split()]
    L = sorted(L)
    num = 0
    for ai in range(N):
        for bi in range(ai+1, N):
            if bi - ai == 1:
                continue
            a = L[ai]
            b = L[bi]
            ci_left = bisect_right(L, abs(L[ai] - L[bi]))
            ci_right = bisect_left(L, L[ai] + L[bi])
            if ci_left == ci_right:
                continue
            else:
                ci_left = max(ci_left, ai + 1)
                ci_right = min(ci_right, bi)
            # print(a, b, ci_left, min(ci_right, bi) - max(ci_left, ai) - 1)
            # num += min(ci_right, bi) - max(ci_left, ai) - 1
                num += ci_right - ci_left
            # print(a, b, ci_right, ci_left, num)
 
    print(num)
 
 
if __name__ == '__main__':
    main()

### FIXED CODE ###

import bisect

def main():
    N = int(input())
    L = [int(i) for i in input().split()]
    L.sort()
    count = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            k = bisect.bisect_left(L, L[i] + L[j])
            k -= 1
            count += k - j
    print(count)


if __name__ == "__main__":
    main()
import bisect
MOD = 10**9 + 7
 
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
  
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
  
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
n, k = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]
bit = Bit(n*2)
ans = 0
 
for i, p in enumerate(a):
    bit.add(p, 1)
    ans += i + 1 - bit.sum(p)
 
a.sort()
big = 0
for item in a:
    big += n - bisect.bisect_right(a, item)
 
times = (k * (k - 1) // 2) % MOD
ans2 = (ans * k) % MOD + (big * times) % MOD
ans2 %= MOD
print(ans2)

### FIXED CODE ###

import bisect
MOD = 10**9 + 7
 
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
  
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
  
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
n, k = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]
bit = Bit(2010 * 2)
ans = 0
 
for i, p in enumerate(a):
    bit.add(p, 1)
    ans += i + 1 - bit.sum(p)
 
a.sort()
big = 0
for item in a:
    big += n - bisect.bisect_right(a, item)
 
times = (k * (k - 1) // 2) % MOD
ans2 = (ans * k) % MOD + (big * times) % MOD
ans2 %= MOD
print(ans2)
import math
from typing import List, Any

N: int = 44852

def nsin(N, base):
    if N == 0: return [0]
    Nsin: List[Any] = []
    for i in range((int(math.log(N,base)//1)+1)):
        ithdigit = N%(base**(i+1)) // (base ** i)
        Nsin.append(ithdigit)
    Nsin.reverse()
    return Nsin

ans = N
for i in range(N):
    coins: int = sum(nsin(i,6)) + sum(nsin(N-i,9))
    if coins < ans: ans = coins

print(ans)

### FIXED CODE ###

import math
N = int(input())
 
def Nsinpou(x, base):
    #配列を返す Nsin[0]が上位桁
    if x == 0: return [0]
    Nsin = []
    for i in range((round(math.log(x,base))+1)):
        ithdigit = x%(base**(i+1)) // (base ** i)
        Nsin.append(ithdigit)
    Nsin.reverse()
    return Nsin
 
ans = N
for i in range(N+1):
    coins = sum(Nsinpou(i,6)) + sum(Nsinpou(N-i,9))
    if coins < ans:
        ans = coins
    
print(ans)
N, K = map(int, input().split())

s = N % K

print(min(abs(s), abs(K-s))

### FIXED CODE ###

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

s = N % K

print(min(s, K-s))
import math
N = int(input())
T = []
for i in range(N):
    T.append(int(input()))

def lcm(a, b):
    return int(a*b/math.gcd(a,b))

def lcm_li(li):
    if len(li) == 2:
        return lcm(li[0], li[1])
    else:
        x = lcm(li[0], li[1])
        x = [x] + li[2:]
        return lcm_li(x)

print(lcm_li(T))

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

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

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

lcm = 1
for i in T:
    lcm = int(lcm * i // gcd(lcm, i))

print(lcm)
d,n = map(int,input()split())
 
if d == 0:
  if n == 100:
    print(101)
  else:
    print(n)
elif d == 1:
  if n == 100:
    print(10001)
  else:
    print(100*n)
elif d == 2:
  if n == 100:
    print(1000001)
  else:
    print(10000*n)

### FIXED CODE ###

d,n = map(int,input().split())
 
if d == 0:
  if n == 100:
    print(101)
  else:
    print(n)
elif d == 1:
  if n == 100:
    print(10100)
  else:
    print(100*n)
elif d == 2:
  if n == 100:
    print(1010000)
  else:
    print(10000*n)