Problem:


Score : 400 points

Problem Statement

Takahashi has N sticks that are distinguishable from each other. The length of the i-th stick is L_i.

He is going to form a triangle using three of these sticks. Let a, b, and c be the lengths of the three sticks used. Here, all of the following conditions must be satisfied:

a < b + c

b < c + a

c < a + b

How many different triangles can be formed? Two triangles are considered different when there is a stick used in only one of them.

Constraints

All values in input are integers.

3 \leq N \leq 2 \times 10^3

1 \leq L_i \leq 10^3

Input

Input is given from Standard Input in the following format:

N
L_1 L_2 ... L_N

Constraints

Print the number of different triangles that can be formed.

Sample Input 1

4
3 4 2 1

Sample Output 1

1

Only one triangle can be formed: the triangle formed by the first, second, and third sticks.

Sample Input 2

3
1 1000 1

Sample Output 2

0

No triangles can be formed.

Sample Input 3

7
218 786 704 233 645 728 389

Sample Output 3

23



Sample input:
4
3 4 2 1


Sample output:
1

Submission status: Runtime Error

Solution code:
k = 31
K = 1<<k
nu = lambda L: int("".join([bin(K+a)[-k:] for a in L[::-1]]), 2)
st = lambda n: bin(n)[2:] + "0"
li = lambda s: [int(a, 2) if len(a) else 0 for a in [s[-(i+1)*k-1:-i*k-1] for i in range(1001)]]

N = int(input())
A = [int(a) for a in input().split()]
C = [0] * 1001
for a in A:
    C[a] += 1
B = li(st(nu(C) ** 2))
for a in A:
    if a <= 500: B[2*a] -= 1
for i in range(1001):
    B[i] //= 2
for i in range(1, 1001):
    C[i] += C[i-1]
for i in range(N):
    B[i] += B[i-1]
ans = N*(N-1)*(N-2)//6
for i in range(1, 1001):
    ans -= (N-C[i-1]) * B[i]
print(ans)

Submission status: Runtime Error

Solution code:
k = 31
K = 1<<k
nu = lambda L: int("".join([bin(K+a)[-k:] for a in L[::-1]]), 2)
st = lambda n: bin(n)[2:] + "0"
li = lambda s: [int(a, 2) if len(a) else 0 for a in [s[-(i+1)*k-1:-i*k-1] for i in range(1001)]]

N = int(input())
A = [int(a) for a in input().split()]
C = [0] * 1001
for a in A:
    C[a] += 1
B = li(st(nu(C) ** 2))
for a in A:
    if a <= 500: B[2*a] -= 1
for i in range(1001):
    B[i] //= 2
for i in range(1, 1001):
    C[i] += C[i-1]
for i in range(N):
    B[i] += B[i-1]
ans = N*(N-1)*(N-2)//6
for i in range(1, 1001):
    ans -= (N-CC[i-1]) * B[i]
print(ans)

Submission status: Runtime Error

Solution code:
k = 31
K = 1<<k
nu = lambda L: int("".join([bin(K+a)[-k:] for a in L[::-1]]), 2)
st = lambda n: bin(n)[2:] + "0"
li = lambda s: [int(a, 2) if len(a) else 0 for a in [s[-(i+1)*k-1:-i*k-1] for i in range(1001)]]

N = int(input())
A = [int(a) for a in input().split()]
C = [0] * 1001
for a in A:
    C[a] += 1
B = li(st(nu(C) ** 2))
for a in A:
    if a <= 500: B[2*a] -= 1
for i in range(1001):
    B[i] //= 2
for i in range(1, 1001):
    C[i] += C[i-1]
for i in range(N):
    B[i] += B[i-1]
ans = N*(N-1)*(N-2)//6
for i in range(1001):
    ans -= (N-C[i-1]) * B[i]
print(ans)

Submission status: Runtime Error

Solution code:
k = 31
K = 1<<k
nu = lambda L: int("".join([bin(K+a)[-k:] for a in L[::-1]]), 2)
st = lambda n: bin(n)[2:] + "0"
li = lambda s: [int(a, 2) if len(a) else 0 for a in [s[-(i+1)*k-1:-i*k-1] for i in range(1001)]]

N = int(input())
A = [int(a) for a in input().split()]
C = [0] * 1001
for a in A:
    C[a] += 1
B = li(st(nu(C) ** 2))
for a in A:
    if a <= 500: B[2*a] -= 1
for i in range(1001):
    B[i] //= 2
for i in range(1, 1001):
    C[i] += C[i-1]
for i in range(N):
    B[i] += B[i-1]
ans = N*(N-1)*(N-2)//6
for i in range(1001):
    ans -= (N-CC[i-1]) * B[i]
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
cnt=0
sort(a)
for i in range(n):
  for j in range(i+1,n):
    for k in range(j+1,n):
      if a[k] >= a[i] + a[j]:
        cnt += k-j-1
        break
        
print(cnt)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
cnt=0
for i in range(n):
  for j in range(i+1,n):
    for k in range(j+1,m):
      if a[k] >= a[i] + a[j]:
        cnt += k-j-1
        break
        
print(cnt)

Submission status: Runtime Error

Solution code:
n=int(input())
l=[int(x) for x in input().split()]
l.sort()
s=0
for a in range(0,n-2):
    for b in range(a+1,n-1):
        c=b+1
        while l[c]<l[a]+l[b]:
            s=s+1
            c=c+1
print(s)

Submission status: Runtime Error

Solution code:
n=int(input())
l=[int(x) for x in input().split()]
l.sort()
s=0
for a in range(0,n-2):
    for b in range(a+1,n-1):
        c=b+1
        while l[c]<l[a]+l[b]:
            s=s+1
            b=b+1
print(s)

Submission status: Runtime Error

Solution code:
from _bisect import bisect_right


def d():
    n = int(input())
    ls = list(map(int, input().split()))
    ls.sort()
    count = 0
    for i in range(n-1, -1, -1):
        for j in range(i-1, -1, -1):
            k = bisect_right(ls, ls[i]-ls[j])
            if j >= k:
                count += j - k

    print(count)
    

if __name__ == '__main__':
    d()

Submission status: Runtime Error

Solution code:

def triangle_check(a, b, c):
  if a>b+c:
    return False
  elif b>a+c:
    return False
  elif c>a+b:
    return False
  else:
    return True

def count_triangles(n, sticks):
  assert len(sticks) == n, "lenght of sticks does not match `n`"
  count = 0

  for i in range(len(sticks)):
    for j in range(i+1, len(sticks)):
      for k in range(j+1, len(sticks)):
        count += triangle_check(sticks[i], sticks[j] , sticks[k])

  return count




if __name__ == "__main__":

  n = int(input())
  sticks = sorted(list(set(map(int, input().split(" ")))))
  num_triangles = count_triangles(n, sticks)
  print(num_triangles)

Submission status: Runtime Error

Solution code:

def triangle_check(a, b, c):
  if a>b+c:
    return False
  elif b>a+c:
    return False
  elif c>a+b:
    return False
  else:
    return True

def count_triangles(n, sticks):
  assert len(sticks) == n, "lenght of sticks does not match `n`"
  count = 0

  for i in range(len(sticks)):
    for j in range(i+1, len(sticks)):
      for k in range(j+1, len(sticks)):
        count += triangle_check(sticks[i], sticks[j] , sticks[k])

  return count




if __name__ == "__main__":

  n = int(input())
  sticks = list(set(map(int, input().split(" "))))
  num_triangles = count_triangles(n, sticks)
  print(num_triangles)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    int n;
    cin >> n;
    int l[n];
    for (int i=0;i<n;i++) {
        cin >> l[i];
    }
    sort(l,l+n);
    int cnt = 0;
    for (int i=0;i<n-2;i++) {
        for (int j=i+1;j<n-1;j++) {
            for (int k=j+1;k<n;k++) {
                if (l[k] < l[i] + l[j])
                    cnt++;
            }
        }
    }

    cout << cnt << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <algorithm>
using namespace std;

int main(void){
    int n;
    cin >> n;
    int l[n];
    for (int i=0;i<n;i++) {
        cin >> l[i];
    }
    //sort(l,l+n);
    int cnt = 0;
    for (int i=0;i<n-2;i++) {
        for (int j=i+1;j<n-1;j++) {
            for (int k=j+1;k<n;k++) {
                if (l[k] < l[i] + l[j])
                    cnt++;
            }
        }
    }

    cout << cnt << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <algorithm>
using namespace std;

int main(void){
    int n;
    cin >> n;
    int l[n];
    for (int i=0;i<n;i++) {
        cin >> l[i];
    }
    sort(l,l+n);
    int cnt = 0;
    for (int i=0;i<n-2;i++) {
        for (int j=i+1;j<n-1;j++) {
            for (int k=j+1;k<n;k++) {
                if (l[k] < l[i] + l[j])
                    cnt++;
            }
        }
    }

    cout << cnt << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
L = input().split()
L = [int(i) for i in L ]
total = 0

L_sort = sorted(L)


def test(total):
	for i in range(N-2):
		for j in range(i+1,N - 1):
							temp_L = L_sort[j + 1:]
							
							#total += len(temp_L[temp_L < L_sort[i]+ L_sort[j]])
							temp_L = [k for k in temp_L if k < L_sort[i]+ L_sort[j]]
							total += len(temp_L)

	return total
						
				  	
print(test(total))

Submission status: Runtime Error

Solution code:
from bisect import bisect_left

N = int(input())
L = list(map(int, input().split()))
 
L.sort()
 
ans = 0

for b in range(n):
  for a in range(b):
    ab = L[a] + L[b]
    r = bisect_left(L, ab)
    l = b + 1
    
    ans += r-l

print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
def main():
  n = int(input())
  l = list(map(int, input().split()))
  n = 2000
  l = []
  l.sort()
  l.append(99999999)
  c = 0
  for i in range(n - 2):
      t = i + 2
      for j in range(i + 1, n - 1):
          for k in range(t, n + 1):
              if l[i] + l[j] <= l[k]:
                  t = k
                  break
          if t > j: c += t - j - 1
          if j + 1 == t: t += 1
  print(c)
if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
import sys
import bisect

input = sys.stdin.readline


def main():
    n = int(input())
    l = map(int, input().split())
    # 種類組み合わせ・条件
    l = sorted(l)
    hoge = 0
    for i, a in enumerate(l[:-2], start=1):
        for j, b in enumerate(l[i:-1], start=i):
            index = bisect.bisect_left(l, a + b)
            print(l, a, b, j, index, index - j - 1)
            hoge += index - j - 1
    print(hoge)
    # sum([str(i) for i in


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin
import itertools
import bisect
N = int(stdin.readline().rstrip())
L = [int(x) for x in stdin.readline().rstrip().split()]
L.sort()
ans = 0

for i in range(N-2):
    a = L[i]
    for j in range(i+1, N-1):
        b = l[j]
        k = bisect.bisect_left(L, a+b)
        ans += (k-j-1)
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
l=sorted(list(map(int,input().split())))
count=0
def nibutan(s,g,num):
  while True:
    low=s
    high=g-1
    mid=(low+high)/2
    num1=l[mid]
    if num<=l[mid] and l[mid-1]<num:
      return mid
    elif l[mid-1]>num:
      low=mid+1
    elif l[mid]<num:
      high=mid-1
    else:
      return mid-1    
for i in range(n-2):
  for j in range(i+1,n-1):
    if l[i]+l[j]<=l[n-1]:
      pass
    else:

Submission status: Runtime Error

Solution code:
import bisect
n = int(input())
h = list(map(int, input().split()))
h.sort()
x = 0
def triangle(n,h):
    for i in range(0,n-2):
        for j in range(i+1,n-1):
            for k in range(j+1, n):
                if h[k] <= h[j] + h[i] :
                    x = x + 1
    return x
print(triangle(n,h))

Submission status: Runtime Error

Solution code:
N = int(input())

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

count = 0 
L.sort()

for i in range(N-2):
    k = i + 2
    for j in range(i+1,n):
        while (k<n and L[i] + L[j]):
            k += 1

        if k > j:
            count += k - j - 1


print(count)

Submission status: Runtime Error

Solution code:
import bisect
n = int(input())
length = list(map(int, input().split()))
length = sorted(length)
count = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        insert_index = bisect.bisect_left(length, length[i]+length[j])
                   count += insert_index-j               
print(count)

Submission status: Runtime Error

Solution code:
import bisect
N = int(input())
L = [int(i) for i in input().split()]

SL = sorted(L)
ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        right = bisect.bisect_left(SL, SL[i] + SL[j])
        left = j + 1
        ans += max(right - left)

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(n):
    for j in range(i+1 n):
        for k in range(j+1,n):
            if l[k]<l[j]+l[i]:
                ans += 1

            
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
# L = map(int, input().split())
L = [int(i) for i in input().split()]
# SL = sorted(list(L))
SL = L.sort()
# print('SL', SL)
import bisect

ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        ab = SL[i] + SL[j]
        # print(i, j)
        # print(SL[i], SL[j])
        r = bisect.bisect_left(SL, ab)
        l = j + 1
        # print('r', r)
        # print('l', l)
        # print('---')
        ans += max(0, r - l)

print(ans)

Submission status: Runtime Error

Solution code:
def judge(a, b, c):
    if(a < b + c):
        if(b < c + a):
            if(c < a + b):
                return 1
    return 0

n = int(input())
l = [int(e) for e in input().split(" ")]
i = 0; j = 1; k = 0; ans = 0;
while(i < n):
    j = i + 1
    k = j + 1
    while(j < n):
        while(k < n):
            ans += judge(l[i], l[j], l[k])
            print(f"ans={ans}, l[{i}]={l[i]}, l[{j}]={l[j]}, l[{k}]={l[k]}")
            k += 1
        j += 1
    i += 1
print(ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left

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

l.sort()
count = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    print(bisect_left(l,l[j]+l[i]),i,j,l)
    count+=bisect_left(l,l[j]+l[i])-j-1
print(count)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random  # randome is not available at Codeforces
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
#eps=10**(-10)
#ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n=I()
a=sorted(LI())[::-1]

s=set()
for i in a:
    s.add(i)
s=sorted(list(s))[::-1]
L=1080
#L=10000
k=[0]*(L)
ak=[0]
ans=0

for i in a:
    k[i]+=1
for i in range(L):
    ak.append(ak[-1]+k[i])

un=len(s)
for i in range(un):
    c=s[i]
    if k[c]>=3:
        ans+=k[c]*(k[c]-1)*(k[c]-2)//6
    if k[c]>=2:
        ans+=ak[c]*k[c]*(k[c]-1)//2
    for j in range(i+1,un):
        #show('i,j,s[i],s[j],mm',i,j,'|',s[i],s[j],s[i]-s[j]+1,'|',ak[s[i]-s[j]],ans)
        
        sc=s[j]
        if ak[sc]==0:
            break
        mm=c-sc+1
        if mm<0:
            continue
        elif mm>sc:
            continue # break
        else:
            ans+=k[c]*k[sc]*((1 if 2*k[sc]>k[c] 0)*(k[sc]-1)//2+ak[sc]-ak[mm])
        #show('ans+=',k[sc]*(k[sc]-1)//2+ak[sc]-ak[mm])
    
print(ans)

Submission status: Runtime Error

Solution code:
import bisect
N=int(input())
L=sorted(list(map(int,input().split())))
count=0
for d1 in range(N-2):
    for d2 in range(d1+1,N-1):
        m=bisect.bisect_right(L[d1]+L[d2],l)
        if m>d2:count+=m-d2
print(count)

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
L = np.array([int(l) for l in input().split(' ')])
counts =0
 
for i in range(N):
    for j in range(i+1,N):
        B2  = L[j+1:][(L[j+1:]<L[i]+L[j]) & (L[j+1:]>abs(L[i]-L[j]))]
        counts +=len(B2)
print(counts)

Submission status: Runtime Error

Solution code:
N=int(input())
L=sorted(list(map(int,input().split())))
count=0
for d1 in range(N-2):
    for d2 in range(d1+1,N-1):
        m=bisect.bisect_right(L[d1]+L[d2],l)
        if:m>d2:count+=m-d2
print(count)

Submission status: Runtime Error

Solution code:
import sys
inputs = sys.stdin.readlines()
n = int(inputs[0])
L = list(map(int, inputs[1].split())
A = sorted(L)

ans = 0
for i in range(n-1, 0, -1):
    l, r = 0, i-1
    while l < r:
        if A[i] < A[l] + A[r]:
            ans += r-l
            r -= 1
        else:
            l += 1

print(ans)

Submission status: Runtime Error

Solution code:
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

func main() {
	N := readInt()
	L := make([]int, N)
	for i := 0; i < N; i++ {
		L[i] = readInt()
	}

	sort.Sort(sort.IntSlice(L))
	result := 0
	for i := 0; i < N-2; i++ {
		for j := i + 1; j < N-1; j++ {
			result += sort.SearchInts(L, L[i]+L[j]) - j - 1
		}
	}
	fmt.Println(result)
}

const (
	ioBufferSize = 1 * 1024 * 1024 // 1 MB
)

var stdinScanner = func() *bufio.Scanner {
	result := bufio.NewScanner(os.Stdin)
	result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
	result.Split(bufio.ScanWords)
	return result
}()

func readString() string {
	stdinScanner.Scan()
	return stdinScanner.Text()
}

func readInt() int {
	result, err := strconv.Atoi(readString())
	if err != nil {
		panic(err)
	}
	return result
}

Submission status: Runtime Error

Solution code:
N=int(input())
L=sorted(list(map(int,input().split())))
L=list(set(L))
count=0
d2breakFlag=False
for d1 in range(N-2):
    for d2 in range(d1+1,N-1):
        Temp=L[d1]+L[d2]

        """for d3 in range(d2+1,N):
            if L[d1]+L[d2]>L[d3]:count+=1
            else:break
print(count)"""

Submission status: Runtime Error

Solution code:
from bisect import bisect_right
 
N = int(input())
L = sorted(list(map(int, input().split())))
 
ans = 0
for i in range(1, N-1):
    for j in range(i+1, N):
        ans += max(0, i - bisect_right(L, L[j] - L[i]))
print(ans)
from bisect import bisect_right

N = int(input())
L = sorted(list(map(int, input().split())))

ans = 0
for i in range(1, N-1):
    for j in range(i+1, N):
        ans += max(0, i - bisect_right(L, L[j] - L[i]))
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
l = list(map(int,input().split()))
l.sort()
for i in range(N - 2):
    for j in range(i + 1,N - 1):
        for k in range(j + 1, N ):
            if l[i] < l[j] + l[k]:
                ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt


def LI(): return list(map(int, input().split()))


def LF(): return list(map(float, input().split()))


def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def LS(): return list(map(list, input().split()))


def S(): return list(input().rstrip())


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]


def sosu(x):
    for i in range(2, int(sqrt(x)+1)):
        if x % i == 0:
            return False
    return True


mod = 1000000007
inf = float('INF')


def A():
    A, B = LI()
    ans = A-2*B
    if ans > 0:
        print(ans)
    else:
        print(0)
    return

# B


def B():
    N = II()
    d = LI()
    ans = 0
    for i in range(N):
        for x in range(i+1, N):
            ans += d[i]*d[x]
    print(ans)

    return

# C


def C():
    N = II()
    S = input()
    c = 0
    count = 0
    for i in S:
        if i != c:
            count += 1
        c = i
    print(count-1)

    return

# D


def D():
    N = II()
    L = LI()
    L2 = L.copy()
    L2 = deque(L2)
    count = 0
    for i in range(N-1):
        L2.popleft()
        L3 = L2.copy()
        for j in range(i+1, N):
            L3.popleft()
            if L3 == deque([]):
                break
            p = L[i]+L[j]

            if min(L3) >= p:
                continue
            #Lk = filter(lambda x: x % 2 == 1, L2)
            Lk = [x for x in L3 if p > x]

            for k in Lk:
                if k+L[i] > L[j] and k+L[j] > L[i]:
                    #print(k,L[i] , L[j])
                    count += 1
        if len(L2) == 2:
            break
    print(count)

    return

# E


def E():
    N, M = LI()
    bit_max = 1 << N
    dp = [[inf for i in range(bit_max)] for j in range(M+1)]
    dp[0][0] = 0

    for i in range(M):
        a, b = LI()

        c = LI()
        bit = 0

        for d in c:
            bit |= 1 << (d-1)

        for w in range(bit_max):

            t = w | bit
            cost = dp[i][w] + a

            dp[i+1][t] = min(dp[i+1][t], cost)

            dp[i+1][w] = min(dp[i][w], dp[i+1][w])

    print(-1) if dp[-1][-1] == inf else print(dp[-1][-1])

    return

# F


def F():
    N, M = LI()

    value = [0] * M
    power = [0] * M
    for i in range(M):
        a, b = LI()
        value[i] = a
        c = LI()
        L = ['0'] * N
        for k in c:
            L[k - 1] = '1'
        bint = ''.join(L)
        power[i] = int(bint, 2)
    bint = ''.join(list(['1'] * N))
    dp = [inf] * (int(bint, 2)+1)
    t = 0
    cost = 0

    dp[0] = 0
    for s in range(int(bint, 2) + 1):
        for i in range(M):
            t = s | power[i]
            cost = dp[s] + value[i]
            dp[t] = min(dp[t], cost)
    print(-1) if(dp[-1] == inf) else print(dp[-1])

    return

    # you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")


def solution(S):
    # write your code in Python 3.6
    import math

    vowels = "AIUEO"
    count = 0
    consonants = 0
    newC = []
    newV = []

    for i in S[:-1]:
        if i in vowels:
            count += 1
            newV.append(i)
        else:
            consonants += 1
            newC.append(i)

    if consonants < count or consonants - 2 > count:
        return 0

    a = math.factorial(len(set(newC))) * math.factorial(len(set(newV)))
    return a

    pass


# Solve
if __name__ == '__main__':
    D()

Submission status: Runtime Error

Solution code:
N = int(input())
Lines = list(map(int, input().split(" ")))
Lines.sort()
answer = 0

import bisect

for lineI in range(N):
    for lineJ in range(lineI+1,N):
    	answer += bisect.bisect_left(Lines,Lines[lineI]+Lines[lineJ])-j-1
print(answer)

Submission status: Runtime Error

Solution code:
N = int(input())
L = sorted(list(map(int, input().split())))

ind_list = [-1] * 1001

last_ind = -1
for i in range(1001):
    if i in L:
        last_ind = L.index(i)
        ind_list[i] = last_ind
    else:
        ind_list[i] = last_ind + 0.5

ans = 0

for i in range(N-1):
    for j in range(i+1, N):
        a = L[i]
        b = L[j]
        min_c = max(abs(a - b) + 1, b + 1)
        max_c = min(a + b - 1, 1000)

        min_ind = ind_list[min_c]
        if isinstance(min_ind, float):
            min_ind = int(min_ind + 1)
        max_ind = int(ind_list[max_c])

        ans += max_ind - min_ind + 1

print(ans)

Submission status: Runtime Error

Solution code:
from itertools import accumulate
from collections import Counter
N = int(input())
L = sorted(list(map(int, input().split())))


acc = [0] * 1001
for l in L:
    acc[l] += 1
acc = list(accumulate(acc))


ans = 0
for i in range(N):
    for j in range(i + 1, N):
        l1, l2 = L[i], L[j]
        if l1 == l2:
            continue
        ans += acc[min(1000, l1 + l2 - 1)] - acc[l2]

C = Counter(L)
for k, v in C.items():
    if v >= 3:
        ans += v * (v - 1) * (v - 2) // 6

for k, v in C.items():
    if v >= 2:
        ans += v * (v - 1) // 2 * (acc[min(1000, 2 * v - 1)] - acc[v])

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
l = list(map(int,input().split()))
m = list()
ans = 0
for i in range(n):
    m = list(j for j in l if j != l[i])
    for k in range(n-2):
        for k1 in range(n-k-2):
            if l[i] < m[k]+m[k+k1+1] and m[k] < l[i]+m[k+k1+1] and m[k+k1+1] < l[i]+m[k]:
                ans += 1
print(int(ans/3))

Submission status: Runtime Error

Solution code:
n = int(input())
l = list(map(int,input().split()))
m = list()
ans = 0
for i in range(n):
    m = list(j for j in l if j != l[i])
    for k in range(n-2):
        for k1 in range(n-k-2):
            if l[i] < m[k]+m[k+k1+1] and m[k] < l[i]+m[k+k1+1] and m[k+k1+1] < l[i]+m[k]:
                ans += 1
print(int(ans/3)

Submission status: Runtime Error

Solution code:
n = int(input())
l = list(map(int,input().split()))
m = list()
ans = 0
for i in range(n):
    m = list(j for j in l if j != l[i])
    for k in range(n-2):
        for k1 in range(n-k-2):
            if l[i] < m[k]+m[k+k1+1] and m[k] < l[i]+m[k+k1+1] and m[k+k1+1] < l[i]+m[k]:
                ans += 1
print(ans/3)

Submission status: Runtime Error

Solution code:
import bisect
N = input()
L_list = list(map(int,input().split()))
L_list.sort()
ans = 0

for i in range(N-1):
  for j in range(i+1,N-1):
    x = bisect.bisect_left(L_list,L_list[i]+L_list[j])
    ans += x-j-1
print(ans)

Submission status: Runtime Error

Solution code:
import scipy.misc.comb
n = int(input())
h = list(map(int, input().split()))
def triangle(n,h):
    x = comb(n, 3, exact = True)
    for i in range(0,n-2):
        for j in range(i+1,n-1):
            for k in range(j+1, n):
                if h[i] >= h[j] + h[k] or h[j] >= h[i] + h[k] or h[k] >= h[j] + h[i]:
                    x = x - 1
    return x
print(triangle(n,h))

Submission status: Runtime Error

Solution code:
import bisect
N = input()
L_list = list(map(int,input().split()))
ans = 0

for i in range(N-1):
  for j in range(i+1,N-1):
    x = bisect.bisect_left(L_list,L_list[i]+L_list[j])
    ans += x-j-1
print(ans)

Submission status: Runtime Error

Solution code:
from bisect import*
_,l=open(0)
*e,=enumerate(sorted(map(int,l.split())))
print(sum(j-bisect(l,a-b,0,j)for i,a in e for j,b in e[:i]))

Submission status: Runtime Error

Solution code:
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        s = L[i] + L[j]
        ans += bs.bisect_left(L,s) - j - 1
        # bisect.bisect_left(list, x)
        # はリストにxを挿入できる点を返す
        # すなわち、
        # (val < x for val in list[0:i]) + (val >= x for val in list[i:len(list)])
print(ans)

Submission status: Runtime Error

Solution code:
import bisect
n =int(input())
l =list(map(int, input().split()))
l.sort()
total = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    tmp = bisect.bisect_left(l,l[i]+L[j])
    total += tmp - j - 1
print(total)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

from itertools import accumulate

fact = [1]

for i in range(1, 2 * 10 ** 3 + 1):
    fact.append(fact[-1] * i)


def comb(n, r):
    return int(fact[n] / fact[r] / fact[n-r])


def main():
    n = int(input())
    l = list(map(int, input().split()))

    nums = [0] * 1001

    for e in l:
        nums[e] += 1

    acm = list(accumulate(nums))

    l.sort()
    ans = 0
    tmp = [0] * 1001
    tmp2 = [[0] * 1001 for _ in range(1001)]
    for i in range(n-2):
        for j in range(i+1, n-1):
            a = l[i]
            b = l[j]
            k = min(1000, a+b-1)

            # b < c のときの数
            cnt = acm[k] - acm[b]

            # b == c のときの補正
            if nums[b] >= 3 and a == b and tmp[b] == 0:
                cnt += comb(nums[b], 3)
                tmp[b] = 1

            if nums[b] >= 2 and a != b and tmp2[a][b] == 0:
                cnt += comb(nums[b], 2) * nums[a]
                tmp2[a][b] = 1

            ans += cnt

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from itertools import accumulate

fact = [1]

for i in range(1, 2 * 10 ** 3 + 1):
    fact.append(fact[-1] * i)


def comb(n, r):
    return int(fact[n] / fact[r] / fact[n-r])


def main():
    n = int(input())
    l = list(map(int, input().split()))

    nums = [0] * 1001

    for e in l:
        nums[e] += 1

    acm = list(accumulate(nums))

    l.sort()
    ans = 0
    tmp = [0] * 1001
    tmp2 = [[0] * 1001 for _ in range(1001)]
    for i in range(n-2):
        for j in range(i+1, n-1):
            a = l[i]
            b = l[j]
            k = min(1000, a+b-1)

            # b < c のときの数
            cnt = acm[k] - acm[b]

            # b == c のときの補正
            if nums[b] >= 3 and a == b and tmp[b] == 0:
                cnt += comb(nums[b], 3)
                tmp[b] = 1

            if nums[b] >= 2 and a != b and tmp2[a][b] == 0:
                cnt += comb(nums[b], 2) * nums[a]
                tmp2[a][b] = 1

            ans += cnt

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import bisect

N=[int(x)for x in input().split()]
D=[int(x) for x in input().split()]

D.sort()
total=0

for i in range(N-2):
    for j in range(i+1,N-1):
        total+= bisect.bisect_left(D[j+1:],D[i]+D[j])

print(total)

Submission status: Runtime Error

Solution code:
n=int(input())
cnt=0
l= list(map(int, input().split()))
l.sort(reverse=True)
k=[[0 for i in range(n-2)] for j in range(n-2)]
for i in range(n-2):
    for j in range(i,n-2):
        k[i][j-i]=-l[i+1]-l[j+2]
#print(k)
for i in range(n-1):
    x=i
    while x<n-2:
        cnt+=bisect.bisect_left(k[x],-l[i])
        #print(l[i],bisect.bisect_left(k[x],-l[i]))
        x+=1
print(cnt)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from itertools import accumulate

fact = [1]

for i in range(1, 1001):
    fact.append(fact[-1] * i)


def comb(n, r):
    return int(fact[n] / fact[r] / fact[n-r])


def main():
    n = int(input())
    l = list(map(int, input().split()))

    nums = [0] * 1001

    for e in l:
        nums[e] += 1

    acm = list(accumulate(nums))

    l.sort()
    ans = 0
    tmp = [0] * 1001
    tmp2 = [[0] * 1001 for _ in range(1001)]
    for i in range(n-2):
        for j in range(i+1, n-1):
            a = l[i]
            b = l[j]
            k = min(1000, a+b-1)

            # b < c のときの数
            cnt = acm[k] - acm[b]

            # b == c のときの補正
            if nums[b] >= 3 and a == b and tmp[b] == 0:
                cnt += comb(nums[b], 3)
                tmp[b] = 1

            # if nums[b] >= 2 and a != b and tmp2[a][b] == 0:
            #     cnt += comb(nums[b], 2) * nums[a]
            #     tmp2[a][b] = 1

            ans += cnt

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# D

import itertools
n = int(input())
l = list(map(int, input().split()))
l.sort()
 
from bisect import bisect_left
ans = 0

for i, j in itertools.combinations(len(l),2):
    t = l[i]+l[j]
    idx = bisect_left(l, t)
    ans += max(0, idx-j-1)
print(ans)

Submission status: Runtime Error

Solution code:
# D

import itertools
n = int(input())
l = list(map(int, input().split()))
l.sort()
 
from bisect import bisect_left
ans = 0

for i, j in itertools.combinations(len(n),2):
    t = l[i]+l[j]
    idx = bisect_left(l, t)
    ans += max(0, idx-j-1)
print(ans)

Submission status: Runtime Error

Solution code:
# D

import itertools
n = int(input())
l = list(map(int, input().split()))
l.sort()
 
from bisect import bisect_left
ans = 0

for i, j in itertools.combination(len(n),2):
    t = l[i]+l[j]
    idx = bisect_left(l, t)
    ans += max(0, idx-j-1)
print(ans)