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

import sys
sys.setrecursionlimit(10 ** 6)

N,M = map(int,input().split())
P = list(map(int,input().split()))
XY = []
for i in range(M):
  XY.append(list(map(int,input().split())))
#print(XY)

E = [set() for _ in range(N+1)]
for x,y in XY:
  E[x].add(y)
  E[y].add(x)
#print(E)

def dfs(v,mark):
  visited[v] = mark
  for u in E[v]:
    if visited[u] == 0:
      dfs(u,mark)

visited = [0 for _ in range(N+1)]
mark = 1
for i in range(1,N+1):
  if visited[i] == 0:
    dfs(i,mark)
    mark += 1
#print(visited)

G = [set() for _ in range(max(visited))]
for i in range(1,N+1):
  G[visited[i]-1].add(i)
#print(G)

ans = 0
for g in G:
  Pset = set()
  for idx in g:
    Pset.add(P[idx-1])
  ans += len(Pset & g)
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

N,M = map(int,input().split())
P = list(map(int,input().split()))
XY = []
for i in range(M):
  XY.append(list(map(int,input().split())))
#print(XY)

E = [set() for _ in range(N+1)]
for x,y in XY:
  E[x].add(y)
  E[y].add(x)
#print(E)

def dfs(v,mark):
  visited[v] = mark
  for u in E[v]:
    if visited[u] == 0:
      dfs(u,mark)

visited = [0 for _ in range(N+1)]
mark = 1
for i in range(1,N+1):
  if visited[i] == 0:
    dfs(i,mark)
    mark += 1
#print(visited)

G = [set() for _ in range(max(visited))]
for i in range(1,N+1):
  G[visited[i]-1].add(i)
#print(G)

ans = 0
for g in G:
  Pset = set()
  for idx in g:
    Pset.add(P[idx-1])
  ans += len(Pset & g)
print(ans)
### BUGGY CODE ###

from collections import defaultdict
import sys
from functools import lru_cache

sys.setrecursionlimit(4100000)

@lru_cache(maxsize=None)
def f(x):
    if x == 0:
        return 0
    
    mod = x % (bin(x).count('1'))
    return f(mod) + 1


def main():
    N = int(input())
    X = input()
    O = int(X, 2)
    pc = X.count('1')
    Y = list(X)
    ans = [0] * N
    pre = 1
    for i in range(N-1,-1,-1):
        if pc - 1 <= 0:
            break
        if Y[i] == '1':
            tmp = (O - pre + pc - 1) % (pc - 1)
            ans[i] = f(tmp) + 1
        pre *= 2
        pre %= (pc - 1)
    pre = 1
    for i in range(N-1,-1,-1):
        if Y[i] == '0':
            tmp = (O + pre) % (pc + 1)
            ans[i] = f(tmp) + 1
        pre *= 2
        pre %= (pc + 1)

    for i in range(N):
        print(ans[i])


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from functools import lru_cache
 
sys.setrecursionlimit(4100000)
 
@lru_cache(maxsize=None)
def f(n):
    if n == 0:
        return 0

    return f(n % bin(n).count('1')) + 1

def main():
    N = int(input())
    X = list(input())
    pc = X.count('1')
    now = 0
    for i in range(N):
        if X[i] == '1':
            now += pow(2,N-i-1)

    ac = pc + 1
    dc = pc - 1
    ac_now = now % ac
    if dc:
        dc_now = now % dc
    for i in range(N):
        cnt = 0
        if X[i] == '1' and dc:
            tmp = (dc_now - pow(2, N-i-1, dc)) % dc
            cnt = 1 + f(tmp)
        elif X[i] == '0':
            tmp = (ac_now + pow(2, N-i-1, ac)) % ac
            cnt = 1 + f(tmp)

        print(cnt)



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

import sys
import bisect
input = sys.stdin.readline

n = int(input().rstrip('\n'))
s = input().rstrip('\n')
l = [c for c in s]
q = int(input().rstrip('\n'))
Q = [input().rstrip('\n').split() for _ in range(q)]

class SegTree():
    def __init__(self, n_):
        self.n = 1
        while self.n < n_:
            self.n *= 2
        self.tree = [float('inf') for _ in range(2 * self.n - 1)]
    def update(self, k, a):
        k += self.n - 1
        self.tree[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.tree[k] = min(self.tree[k * 2 + 1], self.tree[k * 2 + 2])
    def query(self, l, r):
        l += self.n - 1
        r += self.n - 2
        res = float('inf')
        while r-l>1:
            if l&1 == 0:
                res = min(res,self.tree[l])
            if r&1 == 1:
                res = min(res,self.tree[r])
                r -= 1
            l = l//2
            r = (r-1)//2
        if l == r:
            res = min(res,self.tree[l])
        else:
            res = min(min(res,self.tree[l]),self.tree[r])
        return res

d = { c: SegTree(n) for c in "abcdefghijklmnopqrstuvwxyz"}

for i, c in enumerate(s):
    d[c].update(i, 1)


for a, b, c in Q:
    if a == "1":
        b = int(b) - 1
        # c = c.rstrip('\n')
        d[l[b]].update(b, float('inf'))
        d[c].update(b, 1)
        l[b] = c
    else:
        res = 0
        b, c = int(b), int(c)
        for key in d:
            if d[key].query(b-1, c) == 1:
                res += 1
        print(res)
# for key in d:
#     print(key)
#     print(d[key].tree[7:])


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input().rstrip('\n'))
s = input().rstrip('\n')
l = [c for c in s]
q = int(input().rstrip('\n'))
Q = [input().rstrip('\n').split() for _ in range(q)]

class SegTree():
    def __init__(self, n_):
        self.n = 1
        while self.n < n_:
            self.n *= 2
        self.tree = [2 for _ in range(2 * self.n - 1)]
    def update(self, k, a):
        k += self.n - 1
        self.tree[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.tree[k] = min(self.tree[k * 2 + 1], self.tree[k * 2 + 2])
    def query(self, l, r):
        l += self.n - 1
        r += self.n - 2
        res = 2
        while r-l>1:
            if l&1 == 0:
                res = min(res,self.tree[l])
            if r&1 == 1:
                res = min(res,self.tree[r])
                r -= 1
            l = l//2
            r = (r-1)//2
        if l == r:
            res = min(res,self.tree[l])
        else:
            res = min(min(res,self.tree[l]),self.tree[r])
        return res

d = { c: SegTree(n) for c in "abcdefghijklmnopqrstuvwxyz"}

for i, c in enumerate(s):
    d[c].update(i, 1)


for a, b, c in Q:
    if a == "1":
        b = int(b) - 1
        d[l[b]].update(b, 2)
        d[c].update(b, 1)
        l[b] = c
    else:
        res = 0
        b, c = int(b), int(c)
        for key in d:
            if d[key].query(b-1, c) == 1:
                res += 1
        print(res)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
for i in range(1,N+1):
    count = 0
    for j in range(i-1, N-1):
        if A[j] == i:
            count += 1
    print(count)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = [0] * (N+1)
for i in A:
    ans[i] += 1
for a in ans[1:]:
    print(a)
### BUGGY CODE ###

n,k=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))
d=[0]*5001
score_max=min(C)
for L in range(n):
  score=0
  for i in range(k):
    score+=C[P[L]-1]
    score_max=max(score,score_max)
    L=P[L]-1
print(score_max)


### FIXED CODE ###

n,k=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))
score_max=max(C)
#スタート地点＝L
for L in range(n):
  score=0
  d=[0]*n
  r=0
  d[L]=1
  #k回移動する
  for _ in range(k):
    r+=1#移動回数をカウント
    L=P[L]-1#移動先の位置
    score+=C[L]
    score_max=max(score,score_max)
    #もしも移動した場所に未到達なら...
    if d[L]==0:
      d[L]=1
    #Cの最小値未満ならスコアは減り続けるのでbreak
    elif score<0:
      break
    else:
      roop=(k//r)-1
      #最後の1周と端数は一個ずつ見る
      h=(k%r)+r
      score*=roop
      score_max=max(score,score_max)

      #あまりの移動回数の処理
      for _ in range(h):
        L=P[L]-1
        score+=C[L]
        score_max=max(score,score_max)
      break
print(score_max)
### BUGGY CODE ###

N=int(input())
ans=0
for i in range(1,N+1):
  Y=int(N//i)
  ans+=int(Y*(Y+1)*i/2)
print(ans)

### FIXED CODE ###

N=int(input())
ans=0
for i in range(1,N+1):
  Y=N//i
  ans+=Y*(Y+1)*i//2
print(int(ans))
### BUGGY CODE ###

import sys

n = int(sys.stdin.readline())
ms = []
for i in range(n):
    ms += [int(sys.stdin.readline())]

total=sum(ms)
dp=[0]*(total+1)
dp[0]=1

for m in ms:
    for i in range(total,m-1,-1):
        dp[i]=dp[i]*2+dp[i-m]
    for i in range(m):
        dp[i]*=2

border = (total + 1) // 2
yo=sum(dp[border:])*3

if total%2==0:
    dp2 = [0] * (total // 2 + 1)
    dp2[0] = 1
    for m in ms:
        for i in range(-1, m - total // 2 - 2, -1):
            dp2[i] += dp2[i - m]
    yo-=dp2[-1]*3

print((3**n-yo)%998244353)

### FIXED CODE ###

import numpy as np
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    md = 998244353
    n = int(input())
    mx = 90005
    dp = np.zeros(mx, dtype="i8")
    dp2 = np.zeros(mx, dtype="i8")
    dp[0] = 1
    dp2[0] = 1
    sum_a = 0
    for _ in range(n):
        a = int(input())
        sum_a += a
        dp[mx - 1:a - 1:-1] = dp[mx - 1:a - 1:-1] * 2 + dp[mx - a - 1::-1]
        dp[:a] *= 2
        dp %= md
        dp2[mx - 1:a - 1:-1] += dp2[mx - a - 1::-1]
        dp2 %= md
    ng = np.sum(dp[(sum_a + 1) // 2:]) - np.sum(dp2[(sum_a + 1) // 2:]) * 2 + 1
    ng %= md
    total = (pow(3, n, md) - 3 * pow(2, n, md) + 3) % md
    print((total - ng * 3) % md)
    # ALL-NG（NG…最大辺が周の半分以上になる）で求める
    # 最大辺を赤として、dp[r] 赤の和がrのパターンを求める
    # 「赤だけ」、「赤と他一色だけ」(両方dp2に含まれる)のパターンは除く必要がある
    # 赤の和が総和の半分以上になるパターンを考えるので、
    # 赤以外の色だけになるパターンは除く必要がない
    # その後、緑、青が最大の辺になる場合も考えて3倍

main()
### BUGGY CODE ###

import heapq
INF = 10**10
n = int(input())
a = [[int(item) for item in input().split()] for _ in range(n)]
b = [[INF for _ in range(n)] for _ in range(n)]

for k in range(n):
    for i in range(n):
        for j in range(n):
            b[i][j] = min(b[i][j], a[i][k] + a[k][j])

ans = sum(map(sum, a)) // 2
for k in range(n):
    for i in range(n):
        for j in range(i+1, n):
            if b[i][j] == a[i][k] + a[k][j] and j != k and i != k:
                ans -= b[i][j]
if a == b:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

import heapq
INF = 10**10
n = int(input())
a = [[int(item) for item in input().split()] for _ in range(n)]
b = [[INF for _ in range(n)] for _ in range(n)]

ans = 0
for i in range(n):
    ans += sum(a[i])
    a[i][i] = INF
ans //= 2

for i in range(n):
    for j in range(i):
        bipas = min(map(sum, zip(a[i], a[j])))
        if a[i][j] > bipas:
            print(-1)
            exit()
        if a[i][j] == bipas:
            ans -= a[i][j]
print(ans)
### BUGGY CODE ###

# エラトステネスの篩
def make_prime_table(n):
    sieve = list(range(n + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(2, int(n ** 0.5) + 1):
        if sieve[i] != i:
            continue
        for j in range(i * i, n + 1, i):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


def prime_factorize(n):
    result = []
    while n != 1:
        p = prime_table[n]
        c = 0
        while n % p == 0:
            n //= p
            c += 1
        result.append(c)
    return result


def f(X):
    result = 1
    for c in prime_factorize(X):
        result *= c + 1
    return result


N = int(input())

prime_table = make_prime_table(N)
result = 0
for K in range(1, N + 1):
    result += K * f(K)
print(result)


### FIXED CODE ###

# エラトステネスの篩
N = int(input())

sieve = [0] * (N + 1)
sieve[0] = -1
sieve[1] = -1
for i in range(2, N + 1):
    if sieve[i] != 0:
        continue
    sieve[i] = i
    for j in range(i * i, N + 1, i):
        if sieve[j] == 0:
            sieve[j] = i


def f(K):
    t = []
    a = K
    while a != 1:
        if len(t) != 0 and t[-1][0] == sieve[a]:
            t[-1][1] += 1
        else:
            t.append([sieve[a], 1])
        a //= sieve[a]
    result = 1
    for _, n in t:
        result *= (n + 1)
    return result


result = 0
for K in range(1, N + 1):
    result += K * f(K)
print(result)
### BUGGY CODE ###

from collections import deque
INFTY = 1000
N = int(input())
S = [list(map(int,list(input()))) for _ in range(N)]
G = {i:[] for i in range(1,N+1)}
for i in range(N-1):
    for j in range(i+1,N):
        if S[i][j]==1:
            G[i+1].append(j+1)
            G[j+1].append(i+1)
heap = deque([(1,0)])
hist = [-1 for _ in range(N+1)]
hist[1] = 0
flag = 0
while heap:
    x,c = heap.popleft()
    for y in G[x]:
        if hist[y]==-1:
            hist[y] = 1-c
            heap.append((y,1-c))
        else:
            if hist[y]!=1-c:
                flag = 1
                break
    if flag==1:break
if flag==1:
    print(-1)
else:
    dist = [[INFTY for _ in range(N+1)] for _ in range(N+1)]
    for i in range(N):
        for j in range(N):
            if i==j:
                dist[i+1][j+1]=0
            if S[i][j]==1:
                dist[i+1][j+1]=1
    for k in range(1,N+1):
        for i in range(1,N+1):
            for j in range(1,N+1):
                dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])
    dmax = 0
    for i in range(1,N+1):
        for j in range(1,N+1):
            dmax = max(dmax,dist[i][j])
    print(dmax+1)

### FIXED CODE ###

from collections import deque
N = int(input())
G = {i:[] for i in range(N)}
for i in range(N):
    S = input().strip()
    for j in range(N):
        if S[j]=="1":
            G[i].append(j)
cmax = 0
for i in range(N):
    hist = [0 for _ in range(N)]
    hist[i]=1
    num = 0
    heap = deque([(i,1)])
    ind = 0
    while ind==0 and num<N:
        cur = heap.popleft()
        num += 1
        y = cur[0]
        g = cur[1]
        cmax = max(cmax,g)
        for x in G[y]:
            if hist[x]==0:
                heap.append((x,g+1))
                hist[x]=g+1
            elif hist[x]==hist[y]:
                ind = 1
                break
    if ind==1:break
if ind==1:
    print(-1)
else:
    print(cmax)
### BUGGY CODE ###


import sys
from collections import defaultdict

# ----------

sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7


def combination(n, k):
    if k > n - k:
        return combination(n, n - k)
    return fact[n] * ifact[k] * ifact[n - k]


def permitation(n, k):
    # nPk = nCk * k!
    res = combination(n, k) * fact[k]
    return res % MOD


N, K = map(int, input().split())
to = defaultdict(list)
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)

# nまでの階乗を前処理
n = 200005
fact = defaultdict(int)
fact[0] = 1
for i in range(1, n + 1):
    fact[i] = fact[i - 1] * i
    fact[i] %= MOD
# nまでの階乗の逆元を前処理
ifact = defaultdict(int)
ifact[n] = pow(fact[n], MOD - 2, MOD)
for i in reversed(range(1, n + 1)):
    ifact[i - 1] = ifact[i] * i
    ifact[i - 1] %= MOD


def dfs(v, p=-1):
    global ans
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    if p == -1:
        nk = K
        c = len(to[v]) + 1
    else:
        nk = K - 2
        c = len(to[v]) - 1
    ans *= permitation(nk, c)
    ans %= MOD


ans = 1
dfs(0)
print(ans)


### FIXED CODE ###

import sys
from collections import defaultdict

# ----------

sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7


def combination(n, k):
    if k > n - k:
        return combination(n, n - k)
    return fact[n] * ifact[k] * ifact[n - k]


def permitation(n, k):
    # nPk = nCk * k!
    if n < 0:
        return 0
    res = combination(n, k) * fact[k]
    return res % MOD


N, K = map(int, input().split())
to = defaultdict(list)
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)

# nまでの階乗を前処理
n = 200005
fact = defaultdict(int)
fact[0] = 1
for i in range(1, n + 1):
    fact[i] = fact[i - 1] * i
    fact[i] %= MOD
# nまでの階乗の逆元を前処理
ifact = defaultdict(int)
ifact[n] = pow(fact[n], MOD - 2, MOD)
for i in reversed(range(1, n + 1)):
    ifact[i - 1] = ifact[i] * i
    ifact[i - 1] %= MOD


def dfs(v, p=-1):
    global ans
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    if p == -1:
        nk = K
        c = len(to[v]) + 1
    else:
        nk = K - 2
        c = len(to[v]) - 1
    ans *= permitation(nk, c)
    ans %= MOD


ans = 1
dfs(0)
print(ans)
### BUGGY CODE ###

H, W = map(int, input().split())
ch, cw =  map(int, input().split())
gh, gw =  map(int, input().split())

f = [[s=="." for s in input()] for h in range(H)]
ans = [[-1 for w in range(W)]for h in range(H)]

Q = [[ch-1, cw-1]]
ans[ch-1][cw-1] = 0
while len(Q)>0:
  nh, nw = Q.pop(0)
  for dh in range(0-min(nh,2), 3):
    if nh+dh>=H:
      break
    for dw in range(0-min(nw,2), 3):
      if nw + dw>=W:
        break
      if dh==0 and dw==0:
        continue
      if dh*dw==0 and (abs(dh)==1 or abs(dw)==1):
        if ans[nh+dh][nw+dw]==-1:
          if f[nh+dh][nw+dw]:
            Q.insert(0, [nh+dh,nw+dw])
            ans[nh+dh][nw+dw]=ans[nh][nw]
          else:
            ans[nh+dh][nw+dw]=-2
        elif ans[nh+dh][nw+dw]>ans[nh][nw]:
          Q.insert(0, [nh+dh,nw+dw])
          ans[nh+dh][nw+dw]=ans[nh][nw]
      else:
        if ans[nh+dh][nw+dw]==-1:
          if f[nh+dh][nw+dw]:
            Q.append([nh+dh,nw+dw])
            ans[nh+dh][nw+dw]=ans[nh][nw]+1
          else:
            ans[nh+dh][nw+dw]=-2
        elif ans[nh+dh][nw+dw]>ans[nh][nw]:
          Q.append([nh+dh,nw+dw])
          ans[nh+dh][nw+dw]=ans[nh][nw]+1
print(ans[gh-1][gw-1])
      


### FIXED CODE ###

H, W = map(int, input().split())
ch, cw =  map(int, input().split())
gh, gw =  map(int, input().split())

f = [[s=="." for s in input()] for h in range(H)]
ans = [[-1 for w in range(W)]for h in range(H)]

nextQ = [(ch-1)*1000 + cw-1]
ans[ch-1][cw-1] = 0
while len(nextQ)>0:
  Q = list(nextQ)
  nextQ = set()
  visited = set()
  while len(Q):
    nh = Q.pop(0)
    nw = nh%1000
    nh = nh//1000
    for dh in range(0-min(nh,2), 3):
      if nh+dh>=H:
        break
      for dw in range(0-min(nw,2), 3):
        if nw + dw>=W:
          break
        if dh==0 and dw==0:
          continue
        if dh*dw==0 and (abs(dh)==1 or abs(dw)==1):
          if ans[nh+dh][nw+dw]==-1:
            if f[nh+dh][nw+dw]:
              Q.append((nh+dh)*1000 + nw+dw)
              visited.add((nh+dh)*1000 + nw+dw)
              ans[nh+dh][nw+dw]=ans[nh][nw]
            else:
              ans[nh+dh][nw+dw]=-2
          elif ans[nh+dh][nw+dw]>ans[nh][nw]:
            Q.append((nh+dh)*1000 + nw+dw)
            visited.add((nh+dh)*1000 + nw+dw)
            ans[nh+dh][nw+dw]=ans[nh][nw]
        else:
          if ans[nh+dh][nw+dw]==-1:
            if f[nh+dh][nw+dw]:
              nextQ.add((nh+dh)*1000 + nw+dw)
              ans[nh+dh][nw+dw]=ans[nh][nw]+1
            else:
              ans[nh+dh][nw+dw]=-2
          elif ans[nh+dh][nw+dw]>ans[nh][nw]:
            nextQ.add((nh+dh)*1000 + nw+dw)
            ans[nh+dh][nw+dw]=ans[nh][nw]+1
  nextQ -= visited
print(ans[gh-1][gw-1])
### BUGGY CODE ###

from bisect import bisect_left


def main():
    def isOK(score):
        count = 0
        for a in reversed(A):
            border_score = score - a
            index = bleft(A, border_score)
            count += N - index
            if count >= M:
                return True
        return False

    N, M = map(int, input().split())
    A = sorted(map(int, input().split()))
    ans = 0

    ng = A[-1] + A[-1] + 1
    ok = A[0] + A[0]
    bleft = bisect_left

    while(abs(ok-ng) > 1):
        #print(ok, ng)
        mid = (ok+ng) // 2
        f = isOK(mid)
        if f:
            ok = mid
        else:
            ng = mid
        #print(f)
        #print(ok, ng)

    min_score = float('inf')
    count = 0
    for a in A:
        index = bleft(A, ok-a)
        if index < N:
            min_score = min(a+A[index], min_score)
            ans += sum(A[index:]) + (N-index) * a
            count += N-index
    ans -= min_score * (count-M)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from bisect import bisect_left
import numpy


def main():
    def isOK(score):
        count = 0
        for a in reversed(A):
            border_score = score - a
            index = bleft(A, border_score)
            count += N - index
            if count >= M:
                return True
        return False

    N, M = map(int, input().split())
    A = sorted(map(int, input().split()))
    ans = 0

    ng = A[-1] + A[-1] + 1
    ok = A[0] + A[0]
    bleft = bisect_left

    while(abs(ok-ng) > 1):
        #print(ok, ng)
        mid = (ok+ng) // 2
        f = isOK(mid)
        if f:
            ok = mid
        else:
            ng = mid
        #print(f)
        #print(ok, ng)
    C = [0,] + A
    C = numpy.cumsum(C[::-1])
    #print(C)
    min_score = float('inf')
    count = 0
    for a in reversed(A):
        index = bleft(A, ok-a)
        if index < N:
            min_score = min(a+A[index], min_score)
            ans += C[N-index-1] + (N-index) * a
            count += N-index

    ans -= min_score * (count-M)
    print(ans)


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

N,K=map(int,input().split())
lmnk=(2*N//K)
ans=0
for h in range(1,lmnk+1):
    a=h*K//2
    if 1<=a<=N:
        for i in range((1+a)//K,(N+a)//K+1):
            b=i*K-a
            if 1<=b<=N:
                for j in range((1+b)//K,(N+b)//K+1):
                    c=j*K-b
                    if 1<=c<=N and (c+a)%K==0:
                            ans+=1
print(ans)


### FIXED CODE ###

N,K=map(int,input().split())
if K%2==1:
    print((N//K)**3)
else:
    print((N//K)**3+(2*N//K-N//K)**3)
### BUGGY CODE ###

#input = raw_input
#import numpy as np

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

values = [[] for i in range(M+1)]
for i in range(N):
    A, B = map(int, input().split())
    if M >= A:
        values[A].append(B)

#print(values)
out = 0
elms = []
for i in range(1, M+1):
    elms += values[i]
    if len(elms) >= 1:
        max_val = max(elms)
        out += max_val
        elms.remove(max_val)

print(out)

### FIXED CODE ###

#input = raw_input
#import numpy as np

from heapq import heappush, heappop

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

values = [[] for i in range(M+1)]
for i in range(N):
    A, B = map(int, input().split())
    if M >= A:
        values[A].append(-B)

#print(values)
out = 0
elms = []
for i in range(1, M+1):
    #print("values[i]", values[i])
    for elm in values[i]:
        heappush(elms, elm)
        
    if len(elms) >= 1:
        max_val = - heappop(elms)
        #print("mval", max_val)
        out += max_val

print(out)
### BUGGY CODE ###

from itertools import combinations
n = int(input())
l = [int(x) for x in input().split()]
l1 = list(combinations(l, 3))
c = 0
for i in l1:
	if i[0] < i[1] + i[2] and i[1] < i[0] + i[2] and i[2] < i[0] + i[1]:
		c += 1
print(c)

### FIXED CODE ###

def findnumberofTriangles(arr): 
  
    # Sort array and initialize count as 0 
    n = len(arr) 
    arr.sort() 
    count = 0
  
    # Fix the first element. We need to run till n-3 as 
    # the other two elements are selected from arr[i+1...n-1] 
    for i in range(0,n-2): 
  
        # Initialize index of the rightmost third element 
        k = i + 2
  
        # Fix the second element 
        for j in range(i+1,n): 
  
            # Find the rightmost element which is smaller 
            # than the sum of two fixed elements 
            # The important thing to note here is, we use 
            # the previous value of k. If value of arr[i] + 
            # arr[j-1] was greater than arr[k], then arr[i] + 
            # arr[j] must be greater than k, because the array 
            # is sorted. 
            while (k < n and arr[i] + arr[j] > arr[k]): 
                k += 1
  
            # Total number of possible triangles that can be 
            # formed with the two fixed elements is k - j - 1. 
            # The two fixed elements are arr[i] and arr[j]. All 
            # elements between arr[j+1] to arr[k-1] can form a 
            # triangle with arr[i] and arr[j]. One is subtracted 
            # from k because k is incremented one extra in above 
            # while loop. k will always be greater than j. If j 
            # becomes equal to k, then above loop will increment k, 
            # because arr[k] + arr[i] is always greater than arr[k] 
            if(k>j): 
                count += k - j - 1
  
    return count
n = int(input())
l = [int(x) for x in input().split()]
print(findnumberofTriangles(l))