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

N = int(input())
A = list(map(int, input().split()))
IND = list(set(A))
CNT = [A.count(x) for x in IND]
# print(IND)
# print(CNT)
CONB = [x*(x-1)//2 for x in CNT]
# print(CONB)
SUM = sum(CONB)
# for i in A:
#     n = CNT[IND.index(i)]
#     ans = SUM - CONB[IND.index(i)] + (n-1)*(n-2)//2
#     print(ans)
ans = [print(SUM - CONB[IND.index(i)] + (CNT[IND.index(i)]-1) * (CNT[IND.index(i)]-2)//2) for i in A ]

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
CNT = [0]*(N+1)
# IND = list(set(A))
# CNT = [A.count(x) for x in IND]
for i in A:
    CNT[i] += 1
# print(IND)
# print(CNT)
# CONB = [A.count(x)*(A.count(x)-1)//2 for x in IND]
CONB = [CNT[x]*(CNT[x]-1)//2 for x in range(len(CNT))]
# print(CONB)
SUM = sum(CONB)
for i in A:
    ans = SUM - CNT[i] + 1
    print(ans)
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
k = [0] * N
for i in range(1,N):
  v = 1 if S[i-1]+S[i] == 'AC' else 0
  k[i-1] = v
for _ in range(Q):
  f,l = map(int,input().split())
  print(sum(k[f-1:l-1]))

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
k = [0] * (N+1)

for i in range(1,N):
  v = 1 if S[i-1]+S[i] == 'AC' else 0
  k[i] = k[i-1] + v
k[-1]=k[-2]
for _ in range(Q):
  f,l = map(int,input().split())
  print(k[l-1] - k[f-1])
### BUGGY CODE ###

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

# print(N,K,A)

target = 1
l = [1]
lorp_on = False
for i in range(1,K+1):
    target = A[target-1]
    # print([target])

    if target in l:
        idx = l.index(target)
        lorp_on = True
        break
    l.append(target)
# print(l)

if lorp_on:

    lorp_length = len(l)-idx
    lorp = l[idx:]

    # print(lorp,lorp_length)

    ans_idx = (K-idx)%lorp_length
    # print(ans_idx)
    print(lorp[ans_idx])

else:

    print(l[K])


### FIXED CODE ###

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

town = [False]*(N+1)
visited_town = []
p = 1
while True:
    if town[p]:
        break
    visited_town.append(p)
    town[p] = True
    p = A[p-1]
#ループに入るまでに訪れた街
m = visited_town.index(p)

#ループ内の街
c = len(visited_town)-m

# print(m,c)
# print(visited_town,town)

if K <= m:
    print(visited_town[K])
else:
    print(visited_town[m+(K-m) % c])
### BUGGY CODE ###

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

d = 'YES'

for i in range(n):
  if a[i:].count(a[i]) > 1:
    d = 'NO'
    break

print(d)

### FIXED CODE ###

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

b = set(a)

if len(a) == len(b):
  print('YES')
else:
  print('NO')
### BUGGY CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq

N, W = list(map(int, input().split()))
INF = 10**10

dp = [[0]*(W+1) for i in range(N+1)]

for i in range(1,N+1):
    w, v = list(map(int, input().split()))
    for j in range(1,W+1):
        if j-w < 0:
            p = -INF
        else:
            p = dp[i-1][j - w]

        dp[i][j] = max(p + v, dp[i-1][j])

print(dp[N][W])


### FIXED CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq

N, W = list(map(int, input().split()))
INF = 10**10

dp = [[0]*(W+1) for i in range(N+1)]

for i in range(1,N+1):
    w, v = list(map(int, input().split()))
    for j in range(1,W+1):
        if j-w < 0:
            p = -INF
        else:
            p = dp[i-1][j - w]

        dp[i][j] = max(p + v, dp[i-1][j])

print(dp[N][W])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log,gcd
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')

#Pythonを用いる場合
#numpy 1.18.0, scipy 1.4.1, scikit-learn 0.22, numba 0.47.0, networkx 2.4
 
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=ii()

ans=0

for i in range(1,n+1):
    
    q=(n//i)*(2*i+i*(n//i -1))//2
    ans+=q
print(ans)



### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')

#Pythonを用いる場合
#numpy 1.18.0, scipy 1.4.1, scikit-learn 0.22, numba 0.47.0, networkx 2.4

#import numpy as np
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix

 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=ii()

ans=0

for i in range(1,n+1):
    
    q=(n//i)*(2*i+i*(n//i -1))//2
    ans+=q
print(ans)
### BUGGY CODE ###

MOD = 10 ** 9 + 7
s = input()
n = len(s)
dp = [[0 for j in range(13)] for i in range(n + 1)]
dp[0][0] = 1
for i, si in enumerate(s):
    if si == '?':
        k_list = range(10)
    else:
        k_list = [int(si)]
    for j in range(13):
        xij = dp[i][j]
        for k in k_list:
            dp[i + 1][(j * 10 + k) % 13] += dp[i][j]
    for j in range(13):
        dp[i + 1][j] %= MOD
print(dp[-1][5])


### FIXED CODE ###

MOD = 10 ** 9 + 7
s = input()
n = len(s)
dp = [[0 for j in range(13)] for i in range(n + 1)]
dp[0][0] = 1
dpi = dp[0]
for i, si in enumerate(s):
    dpi1 = dp[i + 1]
    if si == '?':
        k_list = range(10)
    else:
        k_list = [int(si)]
    for j in range(13):
        xij = dpi[j]
        for k in k_list:
            dpi1[(j * 10 + k) % 13] += xij
    for j in range(13):
        dpi1[j] %= MOD
    dpi = dpi1
print(dp[-1][5])
### BUGGY CODE ###

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

MOD = 10 ** 9 + 7

A.sort()

ans = A[K-1] - A[-K]

tmp = 1

a = 1

for i, Ak in enumerate(A[K:]):
    a = a * (tmp+K-1) // tmp
    ans += a * (Ak - A[N-(K+i)-1])
    if ans > MOD:
        ans %= MOD
    tmp += 1

print(int(ans))


### FIXED CODE ###

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()

mod = 10 ** 9 + 7

f = [i for i in range(N+1)]
for i in range(2, N+1):
    f[i] *= f[i-1]
    f[i] %= mod
f[0] = 1

q = K - 1
fk = pow(f[q], mod - 2, mod)

total = 0

for i in range(N - K + 1):
    p = N - i - 1

    c = (f[p] * fk * pow(f[p-q], mod-2, mod)) % mod
    total += c * (A[-1 - i] - A[i])
    total %= mod

print(total)
### BUGGY CODE ###

N=int(input())
A=sorted(list(map(int,input().split())))
cnt=0
for i in range(N-1):
    l=A[i]
    for j in range(i+1,N):
        m=A[j]
        for a in A[:i]:
            if a<l+m and l<a+m and m<a+l:
                cnt+=1
print(cnt)

### FIXED CODE ###

from bisect import bisect_left
N=int(input())
A=sorted(list(map(int,input().split())))
cnt=0
for i in range(N-1):
    for j in range(i+1,N):
        a=bisect_left(A,A[i]+A[j])
        if j<a:
            cnt+=a-j-1
print(cnt)
### BUGGY CODE ###

s = input()
t = input()

ans = 0
i = 0
while i < len(s):
	if s[i] == t[i]:
		ans += 1

print(ans)

### FIXED CODE ###

s = input()
t = input()

ans = 0
i = 0
while i < len(s):
	if s[i] != t[i]:
		ans += 1
	i += 1

print(ans)
### BUGGY CODE ###

import copy

n,m = map(int,input().split())
h = [int(i) for i in input().split()]
ab = [input().split() for i in range(m)]
tmp=[]
for i in ab:
    tmp.append([int(i[0]),int(i[1])])
ab=tmp

ans = 0

for num,i in enumerate(h):
    flag=0
    for j in ab:
        if j[0]==num+1 and h[j[0]-1]<=h[j[1]-1]:
            flag=1
        elif j[1]==num+1 and h[j[0]-1]>=h[j[1]-1]:
            flag=1
    if flag==0:
        ans+=1
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
h = [int(i) for i in input().split()]
ab = [input().split() for i in range(m)]
tmp=[]
for i in ab:
    tmp.append([int(i[0]),int(i[1])])
ab=tmp

ans = [0 for i in h]

for j in ab:
    if h[j[0]-1]<=h[j[1]-1]:
        ans[j[0]-1]=-1
    if h[j[0]-1]>=h[j[1]-1]:
        ans[j[1]-1]=-1

ans1=0
for i in ans:
    if i>-1:
        ans1+=1
print(ans1)
### BUGGY 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):
        num=l[i]+l[j]
        for k in range(j+1,n):
            if num<=l[k]:
                break
            else:
                ans+=1
print(ans)


### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()
num=[0]*(max(l)+2)
for i in range(n):
    num[l[i]]=i
for i in range(1,len(num)):
    if num[i]==0:
        num[i]=num[i-1]
ans=0
num3=l[n-1]
for i in range(n-2):
    for j in range(i+1,n-1):
        ans+=max(0,num[min(num3,l[i]+l[j]-1)]-j)
print(ans)
### BUGGY CODE ###

N, M = list(map(int, input().split()))
jobs = [[] for _ in range(M)]
for i in range(N):
    d, r = list(map(int, input().split()))
    if d-1 < M:
        jobs[d-1].append(r)

m = 0
li = []
for i in range(M):
    li.extend(jobs[i])
    if len(li) > 0:
        m += max(li)
        li.remove(max(li))
print(m)

### FIXED CODE ###

import heapq
N, M = list(map(int, input().split()))
jobs = [[] for _ in range(M)]
for i in range(N):
    d, r = list(map(int, input().split()))
    if d-1 < M:
        jobs[d-1].append(-r)

m = 0
heap = []
for i in range(M):
    for a in jobs[i]:
        heapq.heappush(heap, a)
    if len(heap) > 0:
        b = heapq.heappop(heap)
        m += -b
print(m)
### BUGGY CODE ###

n,m = map(int,input().split())
from collections import deque
a = []
for _ in range(n):
    a.append(list(input()))

count = 0
for x in a:
    count += x.count("#")
#print(count)

b = [[100000 for i in range(m)] for i in range(n)]
#print(a)

x = [0, 0, -1, 1]
y = [-1, 1, 0, 0]

queue = deque([[0,0]])
b[0][0] = 1
while queue:
    now = queue.popleft()

    for i in range(4):
        if 0 <= now[0] + y[i] < n and 0 <= now[1] + x[i] < m:
            if a[now[0]+y[i]][now[1]+x[i]] == '.':
                queue.append([now[0]+y[i],now[1]+x[i]])
                b[now[0]+y[i]][now[1]+x[i]] = min(b[now[0]][now[1]] + 1, b[now[0]+y[i]][now[1]+x[i]])
    a[now[0]][now[1]] = "#"

if b[n-1][m-1] == 100000:
    print(-1)
    exit()

ans = n * m - (b[n-1][m-1] + count)
print(ans)



### FIXED CODE ###

n,m = map(int,input().split())
from collections import deque
a = []
for _ in range(n):
    a.append(list(input()))

count = 0
for x in a:
    count += x.count("#")
#print(count)

b = [[-1 for i in range(m)] for i in range(n)]
#print(a)

x = [0, 0, -1, 1]
y = [-1, 1, 0, 0]
queue = deque([[0,0]])
b[0][0] = 1
while queue:
    now = queue.popleft()
    if now == [n-1,m-1]:
        print(n * m - (b[n-1][m-1] + count))
        exit()
    a[now[0]][now[1]] = "#"
    for i in range(4):
        if 0 <= now[0] + y[i] < n and 0 <= now[1] + x[i] < m and b[now[0]+y[i]][now[1]+x[i]] == -1:
            if a[now[0]+y[i]][now[1]+x[i]] == '.':
                queue.append([now[0]+y[i],now[1]+x[i]])
                b[now[0]+y[i]][now[1]+x[i]] = b[now[0]][now[1]] + 1

print(-1)
### BUGGY CODE ###

n=int(input())
A=[int(_) for _ in input().split()]
ans=1
for i in range(n):
  ans=ans*A[i]
if ans>10**18:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

n=int(input())
A=[int(_) for _ in input().split()]
ans=1
if A.count(0)>0:
  print(0)
else:
  for i in range(n):
    ans=ans*A[i]
    if ans>10**18:
      print(-1)
      exit()
  print(ans)
### BUGGY CODE ###

def main():
    N, M = map(int, input().split())
    ab = [[int(i) for i in input().split()] for _ in range(M)]
    ab = sorted(ab, key=lambda x: x[1])
    bd = ['0'] * (N - 1)
    for a, b in ab:
        if bd[a-1:b-1].count('1') == 0:
            bd[b - 2] = '1'
    print(bd.count('1'))


main()


### FIXED CODE ###

def main():
    N, M = map(int, input().split())
    ab = [[int(i) for i in input().split()] for _ in range(M)]
    ab = sorted(ab, key=lambda x: x[1])
    last = ab[0][1] - 1
    ans = 1
    for a, b in ab[1:]:
        if last >= a:
            continue
        ans += 1
        last = b - 1
    print(ans)


main()
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque()
d.append((Ch, Cw))
flag = True
ans = 0

while True:
  while flag:
    flag = False
    for _ in range(len(d)):
      Th, Tw = d.popleft()
      for i,j in [(1,0),(-1,0),(0,1),(0,-1),(0,0)]:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        temp = (Th + i, Tw + i)
        if (not (_p) in d) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
          d.append(_p)
          # print(_p)
          if not(i == 0 and j == 0):
            flag = True
  if (Dh,Dw) in d:
    print(ans)
    exit()
  else:
    l = list(d)
    d = deque()
    for Th,Tw in l:
      for i in [-2,-1,0,1,2]:
        for j in [-2,-1,0,1,2]:
          _h = Th + i
          _w = Tw + j
          _p = (_h, _w)
          temp = (Th + i, Tw + i)
          if (not (_p) in l) and (not (_p) in d) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
            d.append(_p)
    if len(d) == 0:
      print('-1')
      exit()
    ans += 1

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    visited[Th][Tw] = 1
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
        visited[_h][_w] = 1
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()
### BUGGY CODE ###

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


for i in range(n-1):
  print(a.count(i+1))

print("0")

### FIXED CODE ###

import collections
n = int(input())
a = list(map(int, input().split()))
c = collections.Counter(a)

for i in range(n-1):
  print(c[i+1])

print("0")
### BUGGY CODE ###

from sys import stdin
from collections import Counter


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    len_S = len(S)
    cnt = 0
    for i in range(len_S):
        for j in range(i+3,len_S):
            if j == i+3:
                mod = int(S[len_S-j-1:len_S-i])%3
            else:
                mod = (mod+int(S[len_S-j-1]))%3
            if mod == 0:
                _ = int(S[len_S-j-1:len_S-i])
                if _%673==0:
                    cnt += 1
                    break
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


def ans():
    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    len_S = len(S)
    cnt = 0
    mod_arr = []
    for i in range(0,len_S+1):
        if len(S[len_S-i:])==0: 
            mod_arr.append(0)
        else:
            _ = int(S[len_S-i:])
            if i==1: mod = _%2019
            else: mod = (mod+int(S[len_S-i])*10**(i-1))%2019
            mod_arr.append(mod)
    mod_count = Counter(mod_arr)
    for value in mod_count.values():
        if value>1:
            cnt += value*(value-1)//2
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


if __name__ == "__main__":
    #main()
    ans()


### FIXED CODE ###

from sys import stdin


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    len_S = len(S)
    cnt = 0
    for i in range(len_S):
        for j in range(i+3,len_S):
            if j == i+3:
                mod = int(S[len_S-j-1:len_S-i])%3
            else:
                mod = (mod+int(S[len_S-j-1]))%3
            if mod == 0:
                _ = int(S[len_S-j-1:len_S-i])
                if _%673==0:
                    cnt += 1
                    break
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


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

    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cnt = 0
    mod_arr = [0] * 2019
    mod_arr[0] += 1

    num, dec = 0, 1
    for s in S[::-1]:
        num += int(s)*dec
        num %= 2019
        dec *= 10
        dec %= 2019
        mod_arr[num] += 1

    for i in range(2019):
        if mod_arr[i] > 0:
            cnt += mod_arr[i]*(mod_arr[i]-1)//2
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)
### BUGGY CODE ###

# -*- coding: utf-8 -*-


def CountingSort(A, k, n):
    B = [None]*(n+1)
    C = [A.count(i) for i in range(k)]
    for i in range(1, k):
        C[i] = C[i] + C[i-1]
    
    for j in range(n, 0, -1):
        B[C[A[j]]] = A[j]
        C[A[j]] -= 1
    
    return B


if __name__ == '__main__':
    k = 10000
    n = int(input())
    A = [None] + [int(a) for a in input().split(" ")]
    
    B = CountingSort(A, k, n)
    print(" ".join(map(str, B[1:])))



### FIXED CODE ###

# -*- coding: utf-8 -*-


def CountingSort(A, k, n):
    B = [None]*(n+1)
    C = [0]*k
    for j in range(1, n+1):
        C[A[j]] += 1

    for i in range(1, k):
        C[i] = C[i] + C[i-1]
    
    for j in range(n, 0, -1):
        B[C[A[j]]] = A[j]
        C[A[j]] -= 1
    
    return B


if __name__ == '__main__':
    k = 10000
    n = int(input())
    A = [None] + [int(a) for a in input().split(" ")]
    
    B = CountingSort(A, k, n)
    print(" ".join(map(str, B[1:])))
### BUGGY CODE ###

n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
x.sort()
y.sort()
ans=10**18*4
def upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
    global n,k,xy
    z=[0]*n
    for i in range(n):
        if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
            z[i]=1
    return sum(z)>=k

for i1 in range(n):
    i1_sub=n-i1
    x_sub1=x[i1][0]
    for l1 in range(i1_sub,1,-1):
        x_sub2=x[i1+l1-1][0]
        for i2 in range(n):
            i2_sub=n-i2
            y_sub1=y[i2][0]
            l,r=2,i2_sub
            if r<l:
                break
            while l+1<r:
                t=(l+r)//2
                y_sub2=y[i2+t-1][0]
                if upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
                    r=t
                else:
                    l=t
                #print(str(l)+" "+str(r))
            #print(i2+l-1)
            y_sub2=y[i2+l-1][0]
            if upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
                ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
            y_sub2=y[i2+r-1][0]
            if upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
                ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)
### BUGGY CODE ###

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

ruiseki = [[0]*20 for i in range(n+1)]

for i in range(n):
    for j in range(20):
        ruiseki[i+1][j] = ruiseki[i][j] + a[i] % 2
        a[i] = a[i] >> 1

s = 0
t = 1
ans = 0
while s < n + 1:
    while t < n + 1: 
        flag = False
        for i in range(20):
            if ruiseki[t][i] - ruiseki[s][i] > 1:
                flag = True
        if flag:
            break
        t += 1
    ans += (t - s - 1)
    s += 1
print(ans)

### FIXED CODE ###

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

ruiseki = [[0]*20 for i in range(n+1)]

for i in range(n):
    for j in range(20):
        ruiseki[i+1][j] = ruiseki[i][j] + a[i] % 2
        a[i] = a[i] >> 1

s = 0
t = 1
ans = 0
while s < n + 1:
    while t < n + 1: 
        flag = False
        for i in range(20):
            if ruiseki[t][i] - ruiseki[s][i] > 1:
                flag = True
        if flag:
            break
        t += 1
    ans += (t - s - 1)
    s += 1
print(ans)