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

n = int(input())
h = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]


class SegmentTree:
    def __init__(self, a, func=max, one=-10 ** 18):
        self.logn = (len(a) - 1).bit_length()
        self.n = 1 << self.logn
        self.func = func
        self.one = one

        self.b = [self.one] * (2 * self.n - 1)
        for i, j in enumerate(a):
            self.b[i + self.n - 1] = j
        for i in reversed(range(self.n - 1)):
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_item(self, i):
        return self.b[i + self.n - 1]

    def update(self, index, x):
        i = index + self.n - 1
        self.b[i] = x
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def update_func(self, index, x):
        i = index + self.n - 1
        self.b[i] = self.func(self.b[i], x)
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_segment(self, l, r):
        l += self.n
        r += self.n
        s = self.one
        t = self.one
        while l < r:
            if l & 1:
                s = self.func(s, self.b[l - 1])
                l += 1
            if r & 1:
                r -= 1
                t = self.func(self.b[r - 1], t)
            l >>= 1
            r >>= 1
        return self.func(s, t)


seg = SegmentTree([0]*(n+1))

for i in range(n):
    j = seg.get_segment(0, h[i] + 1)
    seg.update_func(h[i], j + a[i])
print(seg.get_segment(0, n+1))


### FIXED CODE ###

n = int(input())
h = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]


class Bucket:
    def __init__(self, a, k, func=max, one=-10**18):
        self.n = len(a)
        self.k = k
        self.func = func
        self.one = one

        self.a = a[:]
        self.b = []
        for i in range(self.n // self.k):
            s = self.one
            for j in range(i * self.k, i * self.k + self.k):
                s = func(s, self.a[j])
            self.b.append(s)
        s = self.one
        for i in range(self.n // self.k * self.k, self.n):
            s = self.func(s, self.a[i])
        self.b.append(s)

    def get(self, index):
        s = self.one
        j = index // self.k
        for i in range(j):
            s = self.func(s, self.b[i])
        for i in range(j * self.k, index + 1):
            s = self.func(s, self.a[i])
        return s

    def update(self, index, x):
        self.a[index] = self.func(x, self.a[index])
        self.b[index//self.k] = self.func(self.b[index//self.k], x)


buc = Bucket([0] * (n+1), max(10, int(n**0.5)))

for i in range(n):
    j = buc.get(h[i])
    buc.update(h[i], j + a[i])

print(buc.get(n))
### BUGGY CODE ###

import math
n,a=int(input()),list(map(int,input().split()))
b=[0]*n
ba=set()
for i in range(n):
  if a[n-i-1]==(b[n-i-1]+1)%2:
    b[n-i-1]+=1
    ba.add(n-i)
    for j in range(2,n-i+1):
      if (n-i)%j==0:b[(n-i)//j-1]+=1
l=len(ba)
c=[ba.pop()for i in range(l)]
print(l)
print(*c)

### FIXED CODE ###

n,a,d,l=int(input()),list(map(int,input().split())),set(),0;b=[0]*n
for i in range(n-1,-1,-1):
  c=0
  for j in range(2*i+1,n,i+1):c=(c+b[j])%2
  if a[i]!=c:b[i]+=1;d.add(i+1);l+=1
print(l)
print(*[d.pop()for _ in range(l)])
### BUGGY CODE ###

n=int(input())
s=tuple(input())

pin=set()
for i in range(0,1000):
    yn=""
    stri=format(i,"03d")
    for ii in range(n-2):
        if stri[0]==s[ii]:
            yn="yes1"
            break
    if yn!="yes1":
        continue
    for iii in range(ii+1,n-1):
        if stri[1]==s[iii]:
            yn="yes2"
            break
    if yn!="yes2":
        continue
    for iiii in range(iii+1,n):
        if stri[2]==s[iiii]:
            yn="yes3"
            break
    if yn=="yes3":
        pin.add(stri)

print(len(pin))        
    

### FIXED CODE ###

n=int(input())
s=list(input())

pin=set()
for i in range(0,1000):
    yn=""
    stri=format(i,"03d")
    for ii in range(n-2):
        if stri[0]!=s[ii]:
            continue
        else:
            yn="yes1"
            break
    if yn!="yes1":
        yn="no"
        continue
    for iii in range(ii+1,n-1):
        if stri[1]!=s[iii]:
            continue
        else:
            yn="yes2"
            break
    if yn!="yes2":
        yn="no"
        continue
    for iiii in range(iii+1,n):
        if stri[2]!=s[iiii]:
            continue
        else:
            yn="yes3"
            break
    if yn=="yes3":
        pin.add(stri)
    else:
        continue

print(len(pin))
### BUGGY CODE ###

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

s = " " + ns()
t = " " + ns()

lens = len(s)
lent = len(t)

lcs = [[""]*lent for _ in range(lens)]

for i in range(1,lens):
    for j in range(1,lent):
        if s[i] == t[j]:
            lcs[i][j] = lcs[i-1][j-1] + s[i]
            
        else:
            if len(lcs[i-1][j]) > len(lcs[i][j-1]):
                lcs[i][j] = lcs[i-1][j]
            else:
                lcs[i][j] = lcs[i][j-1]
                
print(lcs[-1][-1])

### FIXED CODE ###

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def print_lcs (a, b, lcs, i, j, cur):
    if i==0 or j==0:
        return cur
    
    elif a[i] == b[j]:
        ans = print_lcs(a,b,lcs,i-1,j-1,cur+a[i])
        return ans
    
    else:
        if lcs[i-1][j] >= lcs[i][j-1]:
            return print_lcs(a,b,lcs,i-1,j,cur)
        else:
            return print_lcs(a,b,lcs,i,j-1,cur)
        


s = " " + ns()
t = " " + ns()

lens = len(s)
lent = len(t)

lcs = [[0]*lent for _ in range(lens)]
ans = ""
for i in range(1,lens):
    for j in range(1,lent):
        if s[i] == t[j]:
            lcs[i][j] = lcs[i-1][j-1] + 1

            
        else:
            if lcs[i-1][j] > lcs[i][j-1]:
                lcs[i][j] = lcs[i-1][j]
            else:
                lcs[i][j] = lcs[i][j-1]
                
print(print_lcs(s,t,lcs,lens-1,lent-1,"")[::-1])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    for j in range(n):
        if i+1 == a[j]:
            print(j+1, end=" ")

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans = []
for i in range(n):
    ans.append(0)
for i in range(n):
    ans[a[i]-1] = i +1
for i in range(len(ans)):
    print(ans[i], end=" ")
### BUGGY CODE ###

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,m = map(int,input().split())

def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        count=0
        while n % i==0:
            count+=1
            n = n//i
        if count!=0:
            ass.append((i,count))
    if n != 1:
        ass.append((n,1))
    return ass


ass = prime_factor(m)
ans = 1
for i, amount in ass:
  ans = ans * len(tuple(itertools.combinations_with_replacement(range(n),amount))) % mod
print(ans)
# print(ass)


### FIXED CODE ###

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,m = map(int,input().split())
class InverseTable:
    __slots__ = ['In', 'fac', 'Ifac']

    def __init__(self, mod, maxnum):
        self.In = [0, 1]; self.fac = [1, 1]; self.Ifac = [1, 1]
        for i in range( 2, maxnum + 1 ):
            self.In.append( ( -self.In[mod % i] * (mod//i) ) % mod )
            self.fac.append( ( self.fac[-1] * i ) % mod )
            self.Ifac.append( (self.Ifac[-1] * self.In[-1]) % mod )
        
    def cmb(self, n, r):
        if ( r<0 or r>n ): return 0
        r = min(r, n-r)
        return self.fac[n] * self.Ifac[r] * self.Ifac[n-r] % mod
    
    def per(self, n, r):
        if ( r<0 or r>n ): return 0
        return self.fac[n] * self.Ifac[n-r] % mod

invt = InverseTable(mod, 10**6)
# maxnum=10**6だとテーブル生成に200ms程かかるので（Pythonだと1000msほど）
# 最大生成領域は問題ごとに要検討

def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        count=0
        while n % i==0:
            count+=1
            n = n//i
        if count!=0:
            ass.append((i,count))
    if n != 1:
        ass.append((n,1))
    return ass


ass = prime_factor(m)
ans = 1
for i, amount in ass:
  ans = ans * invt.cmb(amount+n-1,amount) % mod
print(ans)
# print(ass)
### BUGGY CODE ###

from math import sqrt
def main():
    n, p = map(int, input().split())
    if n == 1:
        print(p)
    else:
        ans = 1
        cnt = 0
        while p % 2 == 0:
            p //= 2
            cnt += 1
        if cnt >= n:
            ans *= 2**(cnt//n)
        x = 3
        while x**n <= p:
            cnt = 0
            while p % x == 0:
                p //= x
                cnt += 1
            if cnt >= n:
                ans *= x**(cnt//n)
            x += 2
        print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from math import log
def main():
    n, p = map(int, input().split())
    if n == 1:
        print(p)
    else:
        ans = 1
        if n > int(log(p, 2))+2:
            print("1")
            sys.exit()
        if p % (2**n) == 0:
            while p % (2**n) == 0:
                ans *= 2
                p //= (2**n)
        for i in range(3, 10**6+1, 2):
            while p % (i**n) == 0:
                ans *= i
                p //= (i**n)
        print(ans)

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

s = input()

while len(s) > 0:
  if s == "":
    print('YES')
    break
  s.replace('dreamer','')
  s.replace('eraser','')
  s.replace('dream','')
  s.replace('erase','')
  
print('NO')
      


### FIXED CODE ###

s = input()

while True:
  if s == "":
    print('YES')
    break
  elif s[-7:] == 'dreamer':
    s = s[:-7]
  elif s[-6:] == 'eraser':
    s = s[:-6]
  elif s[-5:] == 'dream' or s[-5:] == 'erase':
    s = s[:-5]
  else:
    print('NO')
    break
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()
l.reverse()
count=0
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]:
        count+=1
      else:
        break
print(count)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()
l.reverse()
count=0
for i in range(n-2):
  j=i+1
  k=n-1
  while j<k:
    if l[i]<l[j]+l[k]:
      count+=k-j
      j+=1
    else:
      k-=1
print(count)
### BUGGY CODE ###

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

dp = [0]*(10**6)
dp[0] = 0
for i in range(1, n):
    dp[i] = 10**9
    for j in range(1, k+1):
        if i-j >= 0:
            dp[i] = min(dp[i], dp[i-j]+abs(h[i]-h[i-j]))

print(dp[n-1])


### FIXED CODE ###

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

dp = [0]*(10**6)
dp[0] = 0
for i in range(1, n):
    dp[i] = 10**9
    for j in range(1, k+1):
        if i-j >= 0:
            dp[i] = min(dp[i], dp[i-j]+abs(h[i]-h[i-j]))

print(dp[n-1])
### BUGGY CODE ###

n,m,*L=map(int,open(0).read().split())
con=[[] for _ in range(n)]
c=[True]*n
for s,t in zip(*[iter(L)]*2):
	con[s-1]+=[t-1]
	c[t-1]=False
for i in range(n):
	if c[i]:
		root=i
		break
q=[(None,root)]
ans=[0]*n
while q:
	bef,cur=q.pop(0)
	for nxt in con[cur]:
		if nxt==bef:
			pass
		ans[nxt]=cur+1
		q.append((cur,nxt))
print("\n".join(map(str,ans)))

### FIXED CODE ###

def topologicalSort(g: list, deg: list):
	ret = []
	q = []
	for i, d in enumerate(deg):
		if not d:
			ret.append(i)
			q.append(i)
	while q:
		cur = q.pop(0)
		for nxt in g[cur]:
			deg[nxt] -= 1
			if not deg[nxt]:
				ret.append(nxt)
				q.append(nxt)
	return ret

def main():
	v, e, *L = map(int, open(0).read().split())
	g = [[] for _ in range(v)]
	rev = [[] for _ in range(v)]
	deg = [0] * v
	for s, t in zip(*[iter(L)] * 2):
		g[s - 1].append(t - 1)
		rev[t - 1].append(s - 1)
		deg[t - 1] += 1
	order = topologicalSort(g, deg)
	idx = [None] * v
	for i, o in enumerate(order):
		idx[o] = i
	ans = [0] * v
	for i in range(v):
		if rev[i]:
			ans[i] = max(rev[i], key=lambda x: idx[x]) + 1
	print("\n".join(map(str, ans)))

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

import math

k = int(input())
count = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            count += math.gcd(i,math.gcd(j,l))
print(count)

### FIXED CODE ###

from math import gcd
K=int(input())
ans=0 
 
for i in range(1,K+1):
  for j in range(1,K+1):
    for l in range(1,K+1):
      ans+= gcd(gcd(l,j),i)
 
print(ans)
### BUGGY CODE ###

import math
A,B,N=map(int,input().split())

ans=[]

for i in range(1,N+1):
  num= math.floor((A*i)/B)-(A*(math.floor(i/B)))
  ans.append(num)
 

ans.sort()

print(ans[-1])

### FIXED CODE ###

import math
A,B,N=map(int,input().split())

if B >N:
  print(math.floor((A*N)/B))
else:
  print(math.floor((A*(B-1)/B)))
### BUGGY CODE ###

import numpy as np

H, W = [int(item) for item in input().split()]
grid = np.array([[item for item in input()] for _ in range(H)])

dp = np.zeros((H+1, W+1), dtype='int32')
max_num = 10**9 +7

def main():
    dp[0][1] = 1

    for i in range(H):
        for j in range(W):
            if grid[i][j] != '#':
                dp[i+1][j+1] = (dp[i][j+1] + dp[i+1][j]) % max_num
            

    # print(dp)
    print(dp[H][W])

if __name__ == "__main__":
    main()

### FIXED CODE ###

H, W = [int(item) for item in input().split()]
grid = [[item for item in input()] for _ in range(H)]

dp = [[0 for _ in range(W+1)] for _ in range(H+1)]
max_num = 10**9 +7

def main():
    dp[0][1] = 1

    for i in range(H):
        for j in range(W):
            if grid[i][j] != '#':
                dp[i+1][j+1] = (dp[i][j+1] + dp[i+1][j]) % max_num
            

    # print(dp)
    print(dp[H][W])

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

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = [INT() for _ in range(N)]

# tmp = 0
# ans = 0
# for i in range(1, N):
# 	print(A[i-1], A[i])
# 	if A[i] < A[i-1]:
# 		ans += 1
# print(ans)
# seq = A

ans = 0
LIS = [[A[0]]]
for i in range(1, len(A)):
	for j in range(len(LIS)):
		if A[i] > LIS[j][-1]:
			LIS[j].append(A[i])
			break
	else:
		LIS.append([])
		LIS[-1].append(A[i])
# print(LIS)
print(len(LIS))


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = [INT() for _ in range(N)]


seq = A[::-1]
LIS = [seq[0]]
for i in range(1, len(seq)):
	if seq[i] >= LIS[-1]:
		LIS.append(seq[i])
	else:
		LIS[bisect.bisect(LIS, seq[i])] = seq[i]

print(len(LIS))
### BUGGY CODE ###

n = int(input())

def calc(b, e):
    # 等差数列の和
    cnt = e // b
    ans_tmp = (b + e) * cnt // 2
    return ans_tmp

ans = 0

for i in range(1, n+1):
    ans += calc(i, n//i * i)

print(ans)

### FIXED CODE ###

n=int(input())

ans_tmp = sum(range(n+1)) * 2 -1

from itertools import accumulate
sum_list = list(accumulate(range(1, n)))

ans_tmp_2 = 0

for i in range(2, n+1//2+1):
    if n // i > 1:
        count_tmp = n // i
        ans_tmp_2 += i * sum_list[count_tmp - 1] - i

print(ans_tmp + ans_tmp_2)
### BUGGY CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

n = INT()
a = LIST()

k = 1
flag = 1
for i in range(1, n):
    k *= a[i-1]
    if gcd(k, a[i]) > 1:
        flag = 0

if flag == 1:
    print("pairwise coprime")
    exit()

else:
    g = a[0]
    for i in range(1, n):
        g = gcd(g, a[i])
    if g == 1:
        print("setwise coprime")
    else:
        print("not coprime")

### FIXED CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

n = INT()
a = LIST()
m = max(a)

primes = [0]*(m+1)
primes[1] = 1
for i in range(2, m+1):
    if primes[i] == 0:
        for j in range(1, m//i+1):
            primes[i*j] = i

count = [0]*(m+1)
for x in a:
    y = x
    while primes[y] != y:
        count[primes[y]] += 1
        p = primes[y]
        while y % p == 0:
            y //= p
    if primes[y] >= 2:
        count[primes[y]] += 1

if max(count) <= 1:
    print("pairwise coprime")
else:
    g = 0
    for x in a:
        g = gcd(g, x)
    if g == 1:
        print("setwise coprime")
    else:
        print("not coprime")
### BUGGY CODE ###

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

a.sort()
b.sort()
c.sort()

ans = 0
dict_a = dict()
dict_b = dict()
for i in range(n):
    if a[i] in dict_a.keys():
        b_mid = dict_a[a[i]]
    else:
        left = n - 1
        right = 0
        b_mid = n // 2
        while left >= right:
            if b[b_mid] > a[i]:
                left = b_mid - 1
            else:
                right = b_mid + 1
            b_mid = (left + right) // 2
        b_mid += 1
        dict_a[a[i]] = b_mid

    for j in range(b_mid, n):
        if b[j] in dict_b.keys():
            c_mid = dict_b[b[j]]
        else:
            left = n - 1
            right = 0
            c_mid = n // 2
            while left >= right:
                if c[c_mid] > b[j]:
                    left = c_mid - 1
                else:
                    right = c_mid + 1
                c_mid = (left + right) // 2
            dict_b[b[j]] = c_mid
        ans += n - c_mid - 1
print(ans)

### FIXED CODE ###

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

a.sort()
b.sort()
c.sort()

ans = 0
i = []
k = []
for j in range(n):
    left = n - 1
    right = 0
    a_mid = n // 2
    while left >= right:
        if a[a_mid] >= b[j]:
            left = a_mid - 1
        else:
            right = a_mid + 1
        a_mid = (left + right) // 2
    i.append(a_mid + 1)
    
for j in range(n):
    left = n - 1
    right = 0
    c_mid = n // 2
    while left >= right:
        if c[c_mid] > b[j]:
            left = c_mid - 1
        else:
            right = c_mid + 1
        c_mid = (left + right) // 2
    k.append(n - c_mid - 1)

ans = sum(x * y for x, y in zip(i, k))
print(ans)
### BUGGY CODE ###

n , s = map(int,input().split())
a = list(map(int,input().split()))
dp = [[0 for j in range(s+1)] for i in range(n+1)]
mod = 998244353
for i in range(1,n+1):
    if 0 <= a[i-1] <= s:
        if dp[i][a[i-1]] == 0:
            dp[i][a[i-1]] += pow(2,i-1,mod)
    for j in range(0,s+1):
        dp[i][j] += dp[i-1][j]*2
        if j - a[i-1] >= 0:
            dp[i][j] += dp[i-1][j-a[i-1]]
        dp[i][j] %= mod

print(dp[n][s])

### FIXED CODE ###

n , s = map(int,input().split())
a = list(map(int,input().split()))
dp = [[0 for j in range(s+1)] for i in range(n+1)]
mod = 998244353
for i in range(1,n+1):
    if 0 <= a[i-1] <= s:
        if dp[i][a[i-1]] == 0:
            dp[i][a[i-1]] += pow(2,i-1,mod)
    for j in range(0,s+1):
        dp[i][j] += (dp[i-1][j]*2)%mod
        if j - a[i-1] >= 0:
            dp[i][j] += dp[i-1][j-a[i-1]]
        dp[i][j] %= mod

print(dp[n][s])
### BUGGY CODE ###

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

def heihou_hantei(n):
    m = int(n**0.5)
    return m if abs(m*m - n) < 1e-6 else 0

def kouyaku(n,p):
    if n==2:
        for i in range(round(((p**(1/n))/(2**n)+1))): 
            a=heihou_hantei(n)
            if a!=0:
                return a
    
            
    for i in range(round((p**(1/n)+1)),0,-1):        
        if p%i==0:
            if p%(i**n)==0:
                return i
            
print(kouyaku(n,p))

### FIXED CODE ###

N, P = map(int, input().split())
ans = 1
 
if N >= 45:
  print(ans)
elif N == 1:
  print(P)
  
 
  
else:
  i = 1
  while(i**N <= P):
    if P % (i**N) == 0:
      ans = i
    i += 1
  print(ans)
### BUGGY CODE ###

n = int(input())
L = list(map(int, input().split()))
cnt = n * (n - 1) * (n - 2) / 6
jud = []

for i in range(n):
    for j in range(n):
        if i > j:
            jud.append(L[i] + L[j])

for m in range(n):
    for p in range(len(jud)):
        if L[m] >= jud[p]:
            cnt -= 1

if cnt < 0:
    print(0)
else:
    print(int(cnt))


### FIXED CODE ###

from _bisect import bisect_left
from _bisect import bisect_right

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

cnt = 0

for a in range(n):
    for b in range(n):
        if a < b:
            c = bisect_left(L, L[a] + L[b], b)
            cnt += c - b - 1
print(cnt)