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

from collections import defaultdict, deque, Counter
import sys
import heapq
import math

# input = sys.stdin.readline

sys.setrecursionlimit(1000000000)

MIN = -10 ** 9
MOD = 10 ** 9 + 7


def main():
    N = int(input())
    # A, B = [int(a) for a in input().split()]
    # H = [int(a) for a in input().split()]
    A = [
        list(reversed([int(a) - 1 for a in input().split()]))
        for _ in range(N)
    ]

    count = 0
    while True:
        pool = []
        for i, ai in enumerate(A):
            if len(ai) == 0:
                continue
            target = ai[-1]
            if target < i:
                continue
            target_q = A[target]
            if target_q[-1] == i:
                pool.append(i)
                pool.append(target)

        if len(pool) == 0:
            if not all(len(a) == 0 for a in A):
                print(-1)
                return
        for i in pool:
            A[i].pop()
        count += 1
        if all(len(a) == 0 for a in A):
            print(count)
            return


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict, deque, Counter
import sys
import heapq
import math

# input = sys.stdin.readline

sys.setrecursionlimit(1000000000)

MIN = -10 ** 9
MOD = 10 ** 9 + 7


def main():
    N = int(input())
    # A, B = [int(a) for a in input().split()]
    # H = [int(a) for a in input().split()]
    A = {
        i: list(reversed([int(a) - 1 for a in input().split()]))
        for i in range(N)
    }

    Q = set(range(N))

    count = 0
    while True:
        pool = []
        for i in Q:
            ai = A[i]
            if len(ai) == 0:
                continue
            target = ai[-1]
            # if target < i:
            #     continue
            target_q = A[target]
            if target_q[-1] == i:
                # print(i,target)
                pool.append(i)
                pool.append(target)

        if len(pool) == 0:
            if len(Q) != 0:
                print(-1)
                return
            else:
                raise ValueError("test")

        qq = []
        for i in set(pool):
            A[i].pop()
            if len(A[i]) != 0:
                qq.append(i)
        Q = set(qq)

        count += 1
        if len(Q) == 0:
            print(count)
            return


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

X, Y, Z, K = map(int, input().split())

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

N = []
for a in A:
    for b in B:
        N.append(a + b)
N.sort(reverse=True)
N = N[:K]

M = []
for n in N:
    for c in C:
        M.append(n + c)
M.sort(reverse=True)
M = M[:K]

print(*M, sep="\n")


### FIXED CODE ###

X, Y, Z, K = map(int, input().split())

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

N = []
for a in A:
    for b in B:
        N.append(a + b)
N.sort(reverse=True)
N = N[:K]

M = []
for n in N:
    for c in C:
        M.append(n + c)
M.sort(reverse=True)
M = M[:K]

print(*M, sep="\n")
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 8)
n, q = map(int, input().split())

edges = [[] for _ in range(n)]
for _ in range(n - 1):
    frm, to = map(int, input().split())
    # 0-index
    edges[frm - 1].append(to - 1)
    edges[to - 1].append(frm - 1)

scores = [0] * n
for _ in range(q):
    v, s = map(int, input().split())
    scores[v - 1] += s


def dfs(frm, cur):
    if cur > 0:
        scores[cur] += scores[frm]
    for to in edges[cur]:
        if frm != to:
            dfs(cur, to)


dfs(-1, 0)
print(" ".join([str(w) for w in scores]))

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
n, q = map(int, input().split())

edges = [[] for _ in range(n)]
for _ in range(n - 1):
    frm, to = map(int, input().split())
    # 0-index
    edges[frm - 1].append(to - 1)
    edges[to - 1].append(frm - 1)

scores = [0] * n
for _ in range(q):
    v, s = map(int, input().split())
    scores[v - 1] += s


def dfs(frm, cur):
    if cur > 0:
        scores[cur] += scores[frm]
    for to in edges[cur]:
        if frm != to:
            dfs(cur, to)


dfs(-1, 0)
print(" ".join([str(w) for w in scores]))
### BUGGY CODE ###

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

ans = sum(A)
for i in range(q):
    b, c = map(int, input().split())
    if b in A:
        pos = A.index(b)
        count = A.count(b)
        ans += ((c - b) * count)
        A = A[:pos] + [c] * count + A[pos + count:]
    print(ans)

### FIXED CODE ###

from collections import Counter

n = int(input())
A = list(map(int, input().split()))
q = int(input())
cnt_A = dict(Counter(A))
ans = sum(A)
for i in range(q):
    b, c = map(int, input().split())
    if b in cnt_A and cnt_A[b] > 0:
        count = cnt_A[b]
        cnt_A[b] = 0
        if c not in cnt_A:
            cnt_A[c] = count
        else:
            cnt_A[c] += count
        ans += ((c - b) * count)
    print(ans)
### BUGGY CODE ###

def main():
    K,S = [int(x) for x in input().split()]
    cnt = 0
    for x in range(K+1):
        if x > S:
            break
        for y in range(K+1):
            if x+y > S:
                break
            for z in range(K+1):
                if x+y+z > S:
                    break
                if S == x+y+z:
                    cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    K,S = [int(x) for x in input().split()]
    cnt = 0
    for x in range(K+1):
        if x > S:
            break
        for y in range(K+1):
            if x+y > S:
                break
            z = S-(x+y)
            if z < 0 or z > K:
                continue
            # print(x,y,z)
            if S == x+y+z:
                cnt += 1
    print(cnt)

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

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

from functools import lru_cache

ans = [0]*(N+1)

@lru_cache(maxsize=1000)
def main():
    for i in range(1,N+1):
        ans[i] = A.count(i)
        print(ans[i])

main()


### FIXED CODE ###

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

import collections
c = collections.Counter(A)

for i in range(1,N+1):
    print(c[i])
### BUGGY CODE ###

n=int(input())
arr=[int(i) for i in input().split()]
def sumXOR(arr, n):
    MOD=int((1e+9)+7)
    sum = 0
    for i in range(0, 62): 
        zc = 0
        oc = 0
        idsum = 0
        for j in range(0, n): 
            if (arr[j] % 2 == 0): 
                zc = zc + 1
            else: 
                oc = oc + 1
            arr[j] = arr[j]//2
        idsum = oc * zc * (1 << i) 
        sum = (sum + idsum)%MOD
    return sum

ans = sumXOR(arr, n); 
print (ans)

### FIXED CODE ###

n=int(input())
arr=[int(i) for i in input().split()]
def sumXOR(arr, n):
    MOD=int((1e+9)+7)
    sum = 0
    for i in range(0, 62): 
        zc = 0
        oc = 0
        idsum = 0
        for j in range(0, n): 
            if (arr[j] % 2 == 0): 
                zc = zc + 1
            else: 
                oc = oc + 1
            arr[j] = arr[j]//2
        idsum = oc * zc * (1 << i) 
        sum = (sum + idsum)%MOD
    return sum

ans = sumXOR(arr, n); 
print (ans)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
for i in range(q):
    l, r = map(int, input().split())
    print(len(s[l-1:r].split('AC'))-1)

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
sl = len(s)
ac_cnts = [0]
cnt = 0
for i in range(0, sl-1):
    if s[i] == 'A' and s[i+1] == 'C':
        cnt += 1
    ac_cnts.append(cnt)
for i in range(q):
    l, r = map(int, input().split())
    print(ac_cnts[r-1]-ac_cnts[l-1])
### BUGGY CODE ###

a=int(input())
b=0
c=int(a**(1/2))
for i in range(-1500,1500):
    for j in range(-1500,1500):
        if((i**5)-(j**5)==a):
            b=1
            break
    if(b==1):
        break
print(i,j)

### FIXED CODE ###

a=int(input())
b=0
c=int(a**(1/2))
for i in range(-1000,1000):
    for j in range(-1000,1000):
        if((i**5)-(j**5)==a):
            b=1
            break
    if(b==1):
        break
print(i,j)
### BUGGY CODE ###

import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

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

m = -1

for x in range(1, N+1):
    res = math.floor(A * x / B) - A * math.floor(x / B)
    if res >= m:
        m = res
    else:
        break

print(m)


### FIXED CODE ###

import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

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

# m = -1

# for x in range(1, N+1):
#     res = math.floor(A * x / B) - A * math.floor(x / B)
#     print(res)

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

r1, c1, r2, c2 = map(int, input().split()) 

MOD = 1000000007

def pow_mod(x, y):
    if y == 0: return 1
    ans = 1
    while y > 1:
        if y % 2 != 0: 
            ans *= x
            ans %= MOD
        x *= x
        x %= MOD
        y //= 2
    return ans * x % MOD

points = {r2 + c2 + 2, r2 + 1, c2 + 1, r2 + c1 + 1, c1, r1 + c2 + 1, r1, r1 + c1}

factorial_map = {0: 1}
factorial_inv_map = {0: 1}
for i in range(1, r2 + c2 + 3):
  factorial_map[i] = (factorial_map[i - 1] * i) % MOD
  factorial_inv_map[i] = (factorial_inv_map[i - 1] * pow_mod(i, MOD - 2)) % MOD
  if i > 1 and (i - 2) not in points:
    del factorial_map[i-2]
    del factorial_inv_map[i-2]


a = 1
a *= factorial_map[r2 + c2 + 2]
a %= MOD
a *= factorial_inv_map[r2 + 1]
a %= MOD
a *= factorial_inv_map[c2 + 1]
a %= MOD

b = 1
b *= factorial_map[r2 + c1 + 1]
b %= MOD
b *= factorial_inv_map[r2 + 1]
b %= MOD
b *= factorial_inv_map[c1]
b %= MOD

c = 1
c *= factorial_map[r1 + c2 + 1]
c %= MOD
c *= factorial_inv_map[r1]
c %= MOD
c *= factorial_inv_map[c2 + 1]
c %= MOD

d = 1
d *= factorial_map[r1 + c1]
d %= MOD
d *= factorial_inv_map[r1]
d %= MOD
d *= factorial_inv_map[c1]
d %= MOD

ans = a
ans -= b
ans %= MOD
ans -= c 
ans %= MOD
ans += d
ans %= MOD

print(ans)

### FIXED CODE ###



def pow_mod(x, y):
    MOD = 1000000007
    if y == 0: return 1
    ans = 1
    while y > 1:
        if y % 2 != 0: 
            ans *= x
            ans %= MOD
        x *= x
        x %= MOD
        y //= 2
    return ans * x % MOD

def main():
  MOD = 1000000007
  r1, c1, r2, c2 = map(int, input().split()) 

  points = {r2 + c2 + 2, r2 + 1, c2 + 1, r2 + c1 + 1, c1, r1 + c2 + 1, r1, r1 + c1}

  factorial_map = {0: 1}
  for i in range(1, r2 + c2 + 3):
    factorial_map[i] = (factorial_map[i - 1] * i) % MOD
    if i > 1 and (i - 2) not in points:
      del factorial_map[i-2]

  a = 1
  a *= factorial_map[r2 + c2 + 2]
  a %= MOD
  a *= pow_mod(factorial_map[r2 + 1], MOD - 2)
  a %= MOD
  a *= pow_mod(factorial_map[c2 + 1], MOD - 2)
  a %= MOD

  b = 1
  b *= factorial_map[r2 + c1 + 1]
  b %= MOD
  b *= pow_mod(factorial_map[r2 + 1], MOD - 2)
  b %= MOD
  b *= pow_mod(factorial_map[c1], MOD - 2)
  b %= MOD

  c = 1
  c *= factorial_map[r1 + c2 + 1]
  c %= MOD
  c *= pow_mod(factorial_map[r1], MOD - 2)
  c %= MOD
  c *= pow_mod(factorial_map[c2 + 1], MOD - 2)
  c %= MOD

  d = 1
  d *= factorial_map[r1 + c1]
  d %= MOD
  d *= pow_mod(factorial_map[r1], MOD - 2)
  d %= MOD
  d *= pow_mod(factorial_map[c1], MOD - 2)
  d %= MOD

  ans = a
  ans -= b
  ans %= MOD
  ans -= c 
  ans %= MOD
  ans += d
  ans %= MOD

  print(ans)


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

import sys
input = sys.stdin.readline
import heapq

def main():
    N, K = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    F = [int(x) for x in input().split()]

    A_s = sorted(A, reverse=True)
    F_s = sorted(F)
    C = []
    C_h = []
    for i in range(N):
        x = A_s[i] * F_s[i]
        C.append(x)
        heapq.heappush(C_h, -x)

    for _ in range(K):
        x = -heapq.heappop(C_h)
        i = C.index(x)
        A_s[i] -= 1
        y = A_s[i] * F_s[i]
        C[i] = y
        heapq.heappush(C_h, -y)

    x = -heapq.heappop(C_h)
    print(x)











if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
input = sys.stdin.readline

def check(A, F, mid, k):
    for i in range(len(A)):
        if A[i] * F[i] > mid:
            x = A[i] - mid // F[i]
            k -= x
        if k < 0:
            return False
    return True



def main():
    N, K = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    F = [int(x) for x in input().split()]

    A_s = sorted(A, reverse=True)
    F_s = sorted(F)

    l = -1
    r = 10 ** 13
    while r - l != 1:
        mid = (r + l) // 2
        if check(A_s, F_s, mid, K):
            r = mid
        else:
            l = mid

    print(r)











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

import time
start = time.time()

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

if n==1:
  print(p)
else:
  ans=1
  for i in range(1,100000000):
    tmp=i**n
    if (p>=tmp) and (p%tmp == 0):
     ans=i
    if(p<tmp):
      break
    now = time.time()
    if(now-start>1.5):
      break
  print(ans)


### FIXED CODE ###

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

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

kekka=factorize(p)

ans=1
for i in range(len(kekka)):
    ans=ans* kekka[i][0] ** (kekka[i][1]//n)
print(ans)
### BUGGY CODE ###

N = int(input())
L = []
from bisect import bisect_left
for _ in range(N):
    u = int(input())
    index = bisect_left(L,u)
    if index == 0:
        L = [u] + L
    else:
        L[index - 1] = u
print(len(L))


### FIXED CODE ###

N = int(input())
L = []
from bisect import bisect_right
for _ in range(N):
    u = -int(input())
    index = bisect_right(L,u)
#    print(index)
    if index == len(L):
        L.append(u)
    else:
        L[index ] = u
print(len(L))
### BUGGY CODE ###

def mergeSort(A, left, right, n):
    if left + 1 < right:
        mid = int((right + left ) / 2 )
        mergeSort(A, left, mid, n)
        mergeSort(A, mid, right, n)
        return (merge(A, left, mid, right, n))

def merge(A, left, mid, right, n):
    n1 = mid - left
    n2 = right - mid
    L = []
    R = []
    for i in range(n1):
        L.append(A[left + i])
    for i in range(n2):
        R.append(A[mid + i])
    L.append(100000000001)
    R.append(100000000001)
    i = j = 0
    for k in range(left, right):
        A[n] += 1
        if L[i] <= R[j]:
            key = L[i]
            A[k] = key
            i += 1
        else:
            key = R[j]
            A[k] = key
            j += 1
    return A

n = int(input())
A = list(map(int, input().split()))
A.append(0)
S = mergeSort(A, 0, len(A) - 1, n)
print(" ".join(list(map(str, S[:n])))+'\n'+str(S[n]))


### FIXED CODE ###

def mergeSort(A, left, right, n):
    if left + 1 < right:
        mid = int((right + left ) / 2 )
        mergeSort(A, left, mid, n)
        mergeSort(A, mid, right, n)
        return (merge(A, left, mid, right, n))

def merge(A, left, mid, right, n):
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid]  + [10 ** 9 + 1]
    R = A[mid:right] + [10 ** 9 + 1]
    i , j = 0, 0
    for k in range(left, right):
        A[n] += 1
        if L[i] <= R[j]:
            key = L[i]
            A[k] = key
            i += 1
        else:
            key = R[j]
            A[k] = key
            j += 1
    return A

n = int(input())
A = list(map(int, input().split()))
A.append(0)
S = mergeSort(A, 0, len(A) - 1, n)
print(" ".join(list(map(str, S[:n]))))
print(S[n])
### BUGGY CODE ###

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

count = 0
for i in range(0,n-3):
  ii = s[i]
  for j in range(i+1, n-1):
    jj = s[j]
    for k in range(j+1,n):
      if ii == jj:
        break
      kk=s[k]
      if j-i == k-j:
        continue
      if jj != kk and kk!=ii:
        count = count + 1
print(count)


### FIXED CODE ###

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

count = 0
r=0
g=0
b=0
for i in range(0,n):
  if s[i] == 'R':
    r = r + 1
  if s[i]=='G':
    g = g+1
  if s[i]=='B':
    b = b+1
    
for i in range(0,n):
  ii = s[i]
  for j in range(i+1, n):
    jj = s[j]
    if ii==jj:
      continue
    if (2*j-i)<=(n-1):
      if ii!=s[2*j-i] and jj!=s[2*j-i]:
        count = count + 1
print(r*g*b-count)
### BUGGY CODE ###

import  fractions
from functools import reduce

def main():
    n=int(input())
    a=list(map(int,input().split()))
    tmp = lcm(*a)
    mod=10**9 + 7
    m=0
    ans=0
    for i, v in enumerate(a):
        m=tmp//v
        ans+=m%mod
    ans = ans % mod
    print(ans)

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


if __name__=='__main__':
    main()


### FIXED CODE ###

import  fractions
from functools import reduce
import sys
input = sys.stdin.readline
def main():
    n=int(input())
    a=list(map(int,input().split()))
    # tmp = lcm(*a)
    mod=pow(10,9) + 7
    m=0
    ans=0
    tmp = a[0]
    for i in range(1,len(a)):
        tmp = (tmp*a[i]) // fractions.gcd(tmp,a[i])
    
    for i,v in enumerate(a):
        m=tmp//v
        ans+=m
    ans = ans % mod
    print(ans)


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

def main():
    import sys
    input = sys.stdin.readline
    N, W = (int(i) for i in input().split())
    weight = [0] * (N+1)
    value = [0] * (N+1)
    for i in range(1, N+1):
        w, v = (int(i) for i in input().split())
        weight[i] = w
        value[i] = v
    memo = [[-1] * (W + 1) for _ in range(N + 1)]

    def rec(i, w):
        if i == 0:
            return 0
        if memo[i][w] != -1:
            return memo[i][w]
        res = 0
        if w - weight[i] >= 0:
            res = max(rec(i-1, w), rec(i-1, w-weight[i])+value[i])
        else:
            res = rec(i-1, w)
        memo[i][w] = res
        return res

    print(rec(N, W))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, W = (int(i) for i in input().split())
    weight = [0] * (N+1)
    value = [0] * (N+1)
    for i in range(1, N+1):
        w, v = (int(i) for i in input().split())
        weight[i] = w
        value[i] = v
    dp = [[0 for i in range(W + 1)] for j in range(N + 1)]

    for i in range(1, N+1):
        for w in range(W+1):
            if w - weight[i] >= 0:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])
            else:
                dp[i][w] = dp[i-1][w]

    print(dp[N][W])


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

import sys
from bisect import bisect_left

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


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    color = [A[0]]

    for i in range(1, N):
        idx = bisect_left(color, A[i])
        if idx == 0:
            color = [A[i]] + color
        else:
            color[idx - 1] = A[i]

    print(len(color))


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from bisect import bisect_left
from collections import deque

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


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    color = deque([A[0]])

    for i in range(1, N):
        idx = bisect_left(color, A[i])
        if idx == 0:
            color.appendleft(A[i])
        else:
            color[idx - 1] = A[i]

    print(len(color))


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

def main():

    N, K = map(int, input().split())
    XY = [list(map(int, input().split())) for _ in range(N)]
    XY.sort()

    def count(x_min, x_max, y_min, y_max, i, j):
        OK = 0
        NG = 0
        a = j - i + 1 - K
        for m in range(i, j + 1):
            if y_min <= XY[m][1] <= y_max:
                OK += 1
            else:
                NG += 1
            if OK >= K:
                return True
            if NG > a:
                return False

    ans = 10 ** 20
    for i in range(N - 1):
        for j in range(i + K - 1, N):
            for k in range(N):
                for l in range(N):
                    if XY[k][1] < XY[l][1]:
                        if count(XY[i][0], XY[j][0], XY[k][1], XY[l][1], i, j):
                            # print ('A')
                            ans = min(ans, (XY[j][0] - XY[i][0]) * (XY[l][1] - XY[k][1]))
    print (ans)
    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

#PythonだとTLEする
N, K = map(int, input().split())
X = [0] * N
Y = [0] * N
for i in range(N):
    x, y = map(int, input().split())
    X[i] = x
    Y[i] = y

def count(x_min, x_max, y_min, y_max):
    cnt = 0
    for i in range(N):
        if x_min <= X[i] <= x_max and y_min <= Y[i] <= y_max:
            cnt += 1
    return cnt

ans = 10 ** 20
for i in range(N):
    for j in range(N):
        for k in range(N):
            for l in range(N):
                # print ('i, j , k, l = ', i, j, k, l)
                if X[i] < X[j] and Y[k] < Y[l]:
                    if count(X[i], X[j], Y[k], Y[l]) >= K:
                        # print ('A')
                        ans = min(ans, (X[j] - X[i]) * (Y[l] - Y[k]))
print (ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
total = 0
for i in range(N):
  for k in range(N):
    if i!=k and i<k:
      total+=A[i]*A[k]
  
print(total%(10**9+7)) 

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
total = 0
mod = 10**9+7
an = sum(A)

for i in range(N):
  total+=(an-A[i])*A[i]
s = total//2
print(s%mod)
### BUGGY CODE ###

def Judge(x,y):
    sum=1
    for i in range(y):
        sum*=x[i]
        #print(sum)
    if sum>10**18:
        return -1
    else:
        return sum

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

c=Judge(a,n)
print(c)

### FIXED CODE ###

def Judge(x,y):
    sum=1
    for i in range(y):
        if x[i]==0:
            return 0
    for i in range(y):
        sum*=x[i]
        #print(sum)
        if sum>10**18:
            return -1
    return sum

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

c=Judge(a,n)
print(c)
### BUGGY CODE ###

def main():
    N = int(input()) # 5人
    An = list(map(int, input().split(' '))) # A2, A3,...
    
    # N = 5
    # An = [1, 1, 2, 2]
    
    # N = 7
    # An = [1, 2, 3, 4, 5, 6]

    NUM = An.copy()
    out = []
    counter = []
    
    start_index = 0
    
    for n in range(1, N+1):
        count = 0
        # for an_i in range(start_index, len(An)):
        for an in An[start_index:]:
            if n >= an:
                if len(NUM) > 0:
                    count += 1
                    start_index += 1
                    NUM = An[start_index:]
                # print(n, an, NUM)
        counter.append(count)
        # out.append(count)
        
        # print('counter:', counter, 'out:', out)
        
    # print('counter:', counter)
    for i in counter:
        print(i)
            
    
main()

### FIXED CODE ###

from collections import Counter


def main():
    N = int(input()) # 5人
    An = list(map(int, input().split(' '))) # A2, A3,...
    
    # N = 10
    # An = [1,1, 1, 1, 1, 1, 1, 1, 1]
    
    # out = [0] *
    
    an = Counter(An)
    for n in range(1, N+1):  
        print(an[n])
            


    
main()