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:
import bisect,collections,copy,heapq,itertools,math,string
import numpy as np
import sys
from numba import njit

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

N = I()
L = LI()

def test(a,b,c):
    if a<b+c and b<c+a and c<a+b:
        return True
    return False

@ njit
def comb():
    count = 0
    for pair in itertools.combinations(L, 3):
        if test(*pair):
            count += 1
    return count

print(print(comb()))
 
# @njit
# def f(A):
#   count = 0
#   for i in range(N):
#     for j in range(i + 1, N):
#       for k in range(j + 1, N):
#         count += (A[k] < A[i] + A[j])
#   return count
 
# A = np.array(L)
# A.sort()
# print(f(A))

Submission status: Runtime Error

Solution code:
import bisect,collections,copy,heapq,itertools,math,string
import numpy as np
import sys
from numba import njit

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

N = I()
L = LI()

def test(a,b,c):
    if a<b+c and b<c+a and c<a+b:
        return True
    return False

count = 0
@ njit
for pair in itertools.combinations(L, 3):
    # print(pair)
    if test(*pair):
        count += 1
print(count)
 
# @njit
# def f(A):
#   count = 0
#   for i in range(N):
#     for j in range(i + 1, N):
#       for k in range(j + 1, N):
#         count += (A[k] < A[i] + A[j])
#   return count
 
# A = np.array(L)
# A.sort()
# print(f(A))

Submission status: Runtime Error

Solution code:
N = int(input())
L = list(map(int, input().split()))
res = 0
def dfs(A):
    global res, L
    ans = [i for i, v in enumerate(A) if v == 1]
    if len(A) == N:
        if len(ans) == 3:
            a, b, c = L[ans[0]], L[ans[1]], L[ans[2]]
            if a < (b + c) and b < (c + a) and c < (a + b):
                res += 1
        return
    elif len(ans) == 3:
        a, b, c = L[ans[0]], L[ans[1]], L[ans[2]]
        if a < (b + c) and b < (c + a) and c < (a + b):
            res += 1
        return
    else:
        for v in range(2):
            A.append(v)
            dfs(A)
            A.pop()
dfs([])
print(res)

Submission status: Runtime Error

Solution code:
N = int(input())
L = tuple(map(int, input().split()))
res = 0
def dfs(A):
    global res, L
    ans = [i for i, v in enumerate(A) if v == 1]
    if len(A) > N:
        return 
    elif len(ans) == 3:
        a, b, c = L[ans[0]], L[ans[1]], L[ans[2]]
        if a < (b + c) and b < (c + a) and c < (a + b):
            res += 1
        return
    else:
        for v in range(2):
            A.append(v)
            dfs(A)
            A.pop()
dfs([])
print(res)

Submission status: Runtime Error

Solution code:
a = list(map(int, input().split()))
 
a.sort()
count = 0
for i in range(n-1,0,-1):
    l = 0
    r = i-1
    while(l<r):
        if a[l] + a[r] > a[i]:
            count += r-l
            r -= 1
 
        else:
            l += 1
 
print(count)

Submission status: Runtime Error

Solution code:
a = list(map(int, input().split()))
 
a.sort()
count = 0
for i in range(0, n-1):
    l = 0
    r = i-1
    while(l<r):
        if a[l] + a[r] > a[i]:
            count += r-l
            r -= 1
 
        else:
            l += 1
 
print(count)

Submission status: Runtime Error

Solution code:
import sys

ri = lambda: int(sys.stdin.readline())
rl = lambda: list(map(int, sys.stdin.readline().split()))

a = ri()
li = sorted(rl(), reverse=True)
cnt = 0
for i in range(a-2):
    for j in range(i+1, a-1):
        left = j+1
        right = a
        lii = li[i]
        lij = li[j]
        while right-left > 1:
            t = (left + right)//2
            lit = li[t]
            if lii < lij + lit:
                left = t
            else:
                right = t
        if lii < lij + li[t]:
            cnt += left-j
print(cnt)

Submission status: Runtime Error

Solution code:
N = int(input())
import numpy as np
L = np.array(input().split(),np.int16)

L.sort(reverse=True)
counter = 0

for index1,c in enumerate(L):
    index2 = index1+1
    if index2>N-1:
      break
    b = L[index2]
    while b>=c/2:
        
        index3 = index2+1
        if index3>N-1:
            break
        a = L[index3]
        
        while a+b>c:
            counter += 1
            index3+=1
            if index3>N-1:
                break
            a = L[index3]

        index2+=1
        if index2>N-1:
            break
        b = L[index2]


print(counter)

Submission status: Runtime Error

Solution code:
N = int(input())
L = np.array(input().split(),np.int16)

L.sort(reverse=True)
counter = 0

for index1,c in enumerate(L):
    index2 = index1+1
    if index2>N-1:
      break
    b = L[index2]
    while b>=c/2:
        
        index3 = index2+1
        if index3>N-1:
            break
        a = L[index3]
        
        while a+b>c:
            counter += 1
            index3+=1
            if index3>N-1:
                break
            a = L[index3]

        index2+=1
        if index2>N-1:
            break
        b = L[index2]


print(counter)

Submission status: Runtime Error

Solution code:
n = int(input())
ll = [int(w) for w in input().split()]
ll.sort(reverse=True)

ans = 0
for ei, i in enumerate(ll):
    for ej, j in enumerate(ll[ei + 1:]):
        ans += len([w for w in ll[ei + ej + 2] if w > i - j])

print(ans)

Submission status: Runtime Error

Solution code:
def binary_search(list, item):
    low = 0
    lengyh = len(list)
    if list[lengyh - 1] < item:
        return lengyh - 1
    high = lengyh - 1

    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]

        if guess == item - 1 or (mid < lengyh - 1 and (guess < item and list[mid + 1] > item)) or (mid == lengyh - 1 and guess < item):
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1

    return None


N = int(input())
str_l = input()
num = 0
L = []
for v in str_l.split(' '):
    L.append(int(v))

L.sort()
for i in range(N):
    a = L[i]
    for j in range(i, N - 1):
        b = L[j + 1]
        index = binary_search(L[j + 2:], a + b)
        if index is None:
            continue
        else:
            for k in range(0, index + 1):
                c = (L[j + 2:])[k]
                if b + c > a and a + c > b:
                    num += 1

print(num)

Submission status: Runtime Error

Solution code:
def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        if guess == item or (list[mid - 1] < item and list[mid + 1] > item):
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1

    return None


N = int(input())
str_l = input()
num = 0
L = []
for v in str_l.split(' '):
    L.push(int(v))

L.sort()
for i in range(N):
    Ldash = L
    a = Ldash.pop(i)
    for j in range(N - 1):
        b = Ldash.pop(j)
        index = binary_search(Ldash, a + b)
        if index is None:
            continue
        else:
            for k in range(index + 1):
                c = Ldash[k]
                if b + c > a and a + c < b:
                    num += 1

print(num)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
n = int(input())
l = list(map(int, input().split()))
sort_l = sorted(l)
count = 0

for a in range(n-1):
    for b in range(i+1, n):
        c = bisect_left(sort_l, sort_l[a] + sort_l[b])
        if c > b:
            count += c - b -1
        else:
            pass     
        

print(count)

Submission status: Runtime Error

Solution code:
import math
import itertools
 
n = int(input())
a = list(map(int,input().split()))
a.sort()

ans = 0
for i in range(n-2):
    x = a[i]
    for j in range(i+1,n-1):
        y = a[j]
        for k in range(j+1,n):
            if a[k] < x+y
                ans += 1
            else:
                break

print(ans)

Submission status: Runtime Error

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

L_list = sorted(L_list)

count = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            count += L_list[i] + L_list[j] > L_list[k]:

print(count)

Submission status: Runtime Error

Solution code:
n=int(input())
L=list(map(int, input().split()))
L.sort()
count = 0
for a in range(n-2):
  for b in range(a+1,n-1):
    count += bisect_left(L, L[a]+L[b]) - b - 1

print(count)

Submission status: Runtime Error

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

ans = 0
for aix in range(N):
    for bix in range(aix, N):
        for cix in range(cix, N):
            if L[aix] < L[bix] + L[cix] and L[bix] < L[aix] + L[cix] and L[cix] < L[aix] + L[bix]:
                ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left

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

ans=0
for i in range(n):
    for j in range(i+1,n):
        ans+=bisect.bisect_left(l[j+1:], l[i]+l[j])

print(ans)

Submission status: Runtime Error

Solution code:
import bisect

def solve():
  n = int(input())
  L = [int(i) for i in input().split()]
  L.sort()
  total = 0
  for s in range(n-2):
    for m in range(s+1, n-1):
      #二分探索モジュールbisect
      l = bisect.bisect_left(l,l[s]+l[m], 0, n)
      if l>m: total += l-m-1
  print(total)

  return 0

if __name__ == "__main__":
  solve()

Submission status: Runtime Error

Solution code:
import bisect

def solve():
  n = int(input())
  L = [int(i) for i in input().split()]
  L.sort()
  total = 0
  for s in range(n-2):
    for m in range(s+1, n-1):
      l = bisect.bisect_left(l,l[s]+l[m], 0, n)
      if l>m: total += l-m-1
  print(total)

  return 0

if __name__ == "__main__":
  solve()

Submission status: Runtime Error

Solution code:
import bisect

def solve():
  n = int(input())
  l = [int(i) for i in input().split()]
  l.sort()
  total = 0
  for s in range(n-2):
    for m in range(s+1, n-1):
      l = bisect.bisect_left(l,l[s]+l[m], 0, n)
      if l>m: total += l-m-1
  print(total)

  return 0

if __name__ == "__main__":
  solve()

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    l = list(map(int, input().split()))
    l.sort()

    l_c = [0] * 1001

    for li in l:
        l_c[li] += 1
    for i in range(1000):
        l_c[i + 1] += l_c[i]

    ans = 0

    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            ans += l_c[l[i] + l[j] - 1] - j - 1

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Runtime Error

Solution code:
from bisect import bisect_right
from itertools import combinations_with_replacement

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

li = list(combinations_with_replacement(l, 2))
li = [x for x in li if x[0] != x[1] and x[1] != max(l)]

ans = 0
for small, mid in li:
    right = bisect_right(l, small + mid - 1)
    left = bisect_left(l, mid)
    ans += max(right - left - 1, 0)

print(ans)

Submission status: Runtime Error

Solution code:
"""
keyword: 二分探索

初めにLをソートして、a<b<cとしてa,bを決めたとき、a+b>cとなるようなcの個数を計算する
cの最大値を求めるには二分探索が高速
さらに、二分探索の探索範囲の左端は、前のループで求めたcの最大値で十分である（∵前のループのa+b <= 今ループのa+b）ことを考慮すれば、さらに高速化できる

pythonでTLE, pypyでAC
"""

import sys
sys.setrecursionlimit(10**6)

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

L.sort()
ans = 0

for i in range(n-2):
    l_prev = 0 # 前のループで求めたcの最大値を覚えておく
    for j in range(i+1,n-1):
        ab = L[i]+L[j]
        if not l_prev:
            l = j; r = n
        else:
            l = l_prev; r = n
        while l+1 < r:
            c = (l+r)//2
            if L[c] < ab:
                l = c
            else:
                r = c
        ans += l-j
        l_prev = l
        
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
import numpy as np
l = np.array(list(map(int, input().split())))

l = np.sort(l)
s = 0
def bin_search(target, lower, upper):
  if lower == upper:
    return lower
  elif l[(lower+upper)//2] >= target:
    if lower+1 == upper and l[lower] != l[upper]:
      return lower
    return bin_search(target, lower, (lower+upper)//2)
  elif l[(lower+upper)//2] < target:
    if lower+1 == upper:
      if l[lower] != l[upper]:
        return upper
    return bin_search(target, (lower+upper)//2, upper)
c = 0
for i in range(2, n):
  for j in range(1, i):
    target = l[i] - l[j]
    ans = bin_search(target, 0, j-1)
    #print(ans, l[ans], target)
    if ans == 0:
      if l[ans] > target:
        c += 1
      elif ans + 1 != j:
        c += j - 1
    elif l[ans] <= target:
      c += j - ans - 1
    elif l[ans] > target:
      c += j - ans
print(c)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left

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

for i in range(len(L)-2):
  for j in range(i+1, len(L)-1):
    k = j + 1
    while L[k-1] == L[k]:
      k += 1
    cnt += bisect_left(L,L[i]+L[j]) - k

print(cnt)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left

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

for i in range(len(L)-2):
  for j in range(i+1, len(L)-1):
    k = j + 1
    while L[k-1] == L[k]:
      k += 1
    T = L[k:]
    cnt += bisect_left(T,L[i]+L[j])

print(cnt)

Submission status: Runtime Error

Solution code:

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

L.sort()
#print(L)

count = 0
for i in range(N-1):
    for j in range(i+1, N-1):
        L_ = L[j+1:]
        #print(L[i] + L[j], ">", L_, "?")
        key = len(L_) // 2
        #print("init key", key)
        past_key = 0
        n = 2
        while key and N > key:
            n *= 2
            if L[i] + L[j] > L_[key]:
                key += round(len(L_) / n)
            elif L[i] + L[j] <= L_[key]:
                #print(n, round(key / n))
                key -= round(len(L_) / n)
            
            if past_key == key:
                break
            else:
                past_key = key
            #print("next key", key)
            
        if L[i] + L[j] > L_[key]:
            count += key + 1
            

print(count)

Submission status: Runtime Error

Solution code:

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

L.sort()
#print(L)

import sys

sys.setrecursionlimit(10**8)

count = 0
for i in range(N-1):
    for j in range(i+1, N-1):
        L_ = L[j+1:]
        #print(L[i] + L[j], ">", L_, "?")
        key = len(L_) // 2
        #print("init key", key)
        past_key = 0
        n = 2
        while key:
            n *= 2
            if L[i] + L[j] > L_[key]:
                key += round(len(L_) / n)
            elif L[i] + L[j] <= L_[key]:
                #print(n, round(key / n))
                key -= round(len(L_) / n)
            
            if past_key == key:
                break
            else:
                past_key = key
            #print("next key", key)
            
        if L[i] + L[j] > L_[key]:
            count += key + 1
            

print(count)

Submission status: Runtime Error

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

L.sort()
#print(L)

import sys

sys.setrecursionlimit(10**6)

count = 0
for i in range(N-1):
    for j in range(i+1, N-1):
        L_ = L[j+1:]
        #print(L[i] + L[j], ">", L_, "?")
        key = len(L_) // 2
        #print("init key", key)
        past_key = 0
        n = 2
        while key:
            n *= 2
            if L[i] + L[j] > L_[key]:
                key += round(len(L_) / n)
            elif L[i] + L[j] <= L_[key]:
                #print(n, round(key / n))
                key -= round(len(L_) / n)
            
            if past_key == key:
                break
            else:
                past_key = key
            #print("next key", key)
            
        if L[i] + L[j] > L_[key]:
            count += key + 1
            

print(count)

Submission status: Runtime Error

Solution code:

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

L.sort()
#print(L)

count = 0
for i in range(N-1):
    for j in range(i+1, N-1):
        L_ = L[j+1:]
        #print(L[i] + L[j], ">", L_, "?")
        key = len(L_) // 2
        #print("init key", key)
        past_key = 0
        n = 2
        while key:
            n *= 2
            if L[i] + L[j] > L_[key]:
                key = key + round(len(L_) / n)
            elif L[i] + L[j] <= L_[key]:
                #print(n, round(key / n))
                key = key - round(len(L_) / n)
            
            if past_key == key:
                break
            else:
                past_key = key
            #print("next key", key)
            
        if L[i] + L[j] > L_[key]:
            count += key + 1
            

print(count)

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit
 
@njit
def count(l,n):
  ct = 0
  for i in range(n):
    for j in range(i + 1, n):
      for k in range(j + 1, n):
        ct += (l[k] < l[i] + l[j])
  return ct

         
n = int(input())
l = np.int32(input().split())
l.sort()

ans = count(l,n)

print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
#  = input()
n  = int(input())
#  = map(int, input().split())
l  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

l = sorted(l)[::-1]

ans = 0
for i1 in range(len(l-2)):
    a = l[i1]
    for i2 in range(i1+1, len(l-1)):
        b = l[i2]
        l_ = [l[i3] for i3 in l[i2+1:]]

print(ans)

Submission status: Runtime Error

Solution code:
def bis_right(lis,dev):
    a=0
    b=len(lis)
    while a<b:
        c=(a+b)//2
        if lis[c]>dev:
            b=c
        else:
            a=c+1
    if lis[a]<=dev:
        return a
    return a-1



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

Submission status: Runtime Error

Solution code:
from bisect import bisect, bisect_left
 
N= int(input())
L= list(map(int,input().split()))
L.sort()
 
ans = 0
for i in range(N-2):
  a=L[i]
  for k in range(i+1,n-1):
    b=s[k]
    t=bisect_left(L,a+b)
    ans+=t-k-1
print(ans)

Submission status: Runtime Error

Solution code:
import math
N=int(input())
listL=list(map(int,input().split()))
listL.sort()
ans=0
for i in range(N-1,2,-1):
  for k in range(i-1,1,-1):
    t=math.ceil(k/2)
    d=listL[i]-listL[k]
    half=math.ceil((k-t)/4)
    while (d-listL[t]<=0 or d-listL[t+1]>0) and t!=0 and t!=k-1:
      third=listL[t]
      if d-third>=0:
        t=t-half
      else:
        t=t+half
      half=half//2+1
      print(half,t) 
    ans+=k-t+1
print(ans)

Submission status: Runtime Error

Solution code:
N = 7
l=[218,786,704,233,645,728,389]
m=[]

#N>2なら
L.sort()
for a in range(N-2):
    for b in range(a+1,N-1):
        n = 0
        for c in range(b+1,N):
            if L[c] < L[a] + L[b]:
                n = n + 1
            else:break
        m.append(n)
print(sum(m),m)

Submission status: Runtime Error

Solution code:
N = int(input())
L = list(map(int, input().split()))
L.sort()
from itertools import combinations
from numba import njit


@njit
def solve():
    ans = 0
    for a, b, c in combinations(L, r=3):
        ans += a + b > c
    return ans


print(solve())

Submission status: Runtime Error

Solution code:
def binary_search(x, li, value):
  l = []
  left = x+1
  y = x
  right = len(li) - 1
  while left <= right:
    mid = (left + right) // 2
    if li[mid] > value - 1:
      right = mid - 1
    elif li[mid] < value - 1:
      y = mid
      left = mid + 1
    else:
      for i in range(1, 1000):
        if li[mid] == li[mid + i]:
          y = mid + i
        else:
          y = mid
          break
  return y
  
N = int(input())
L = list(map(int, input().split()))
L.sort()
cnt = 0
for i in range(N-2):
  for j in range(i+1, N-1):
    cnt += binary_search(j, L, L[i]+L[j]) - j
print(cnt)

Submission status: Runtime Error

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
n = int(input())
l = sorted(list(map(int, input().split())))
ans = 0
for i in range(n - 2):
    for j in range(i + 1, n - 1):
        a = l[i]
        b = l[j]
        ans += bisect_left(l, a + b) - j - 1
print(ans)

Submission status: Runtime Error

Solution code:
import bisect

N = int(input())

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

A.sort()

ans = 0
for a in range(N-2):
    for b in range(a+1, N-1):
        ans += bisect.bisect_left(A, A[a]+A[b])-j-1

print(ans)

Submission status: Runtime Error

Solution code:
N = input()

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

A.sort()

ans = 0
for a in range(N-2):
    for b in range(a+1, N-1):
        for c in range(b+1, N):
            if A[c] < (A[a] + A[b]):
                ans += 1
            else:
                break

print(ans)

Submission status: Runtime Error

Solution code:
N = input()

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

A.sort()

ans = 0
for a in range(N-2):
    for b in range(a+1, N-1):
        for c in range(b+1, N):
            if A[c] < (A[a] + A[b]):
                ans += 1
                print(a, b, c)
            else:
                break

print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np

def solve(N: int, L: "List[int]"):
    L = np.array(sorted(L))
    ct = 0
    for a in range(len(L)-2):
        for b in range(a, len(L)-1):
            ct+=((L[b] < L) & (L < L[a+b])).sum() 
    print(ct)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    L = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, L)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

l.sort()


print(cnt)

Submission status: Runtime Error

Solution code:
from numpy import gcd, sqrt
m = gcd(a,b)
cnt = 1
print(1)
for i in range(2, int(sqrt(m))+1):
    div = False
    while m%i == 0:
        div = True
        m = m//i
    if div:
        cnt += 1
        print(i)
    if m == 1:
        break
if m > 1:
    cnt += 1
    print(m)
print(cnt)

Submission status: Runtime Error

Solution code:
import bisect
N=int(input())
L=list(map(int,input().split()))
L=sorted(L)
ans=0
for a in range(N):
  for b in range(a+1,N)):
    c=bisect.bisect_left(L,L[a]+L[b])
    if c>b:
      ans+=c-b-1
    else:
      ans=ans
print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
L=list(map(int,input().split()))
i=0
L=sorted(L)
for a in range(N):
  for b in range(a+1,N):
    c=bisect.bisect_left(L,L[a]+L[b])
    if c>b:
      i+=c-b
    else:
      i=i
print(i)