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

N, K = map(int, input().split())
inputs = [int(i) for i in input().split()]

dp = [10 ** 9 for _ in range(N)]
dp[0] = 0
for i in range(1, N):
    if i == 1:
        dp[i] = abs(inputs[i] - inputs[i-1])
    else:
        tmp = 10 ** 9
        start = max(0, i-K)
        dp[i] = min(dp[j] + abs(inputs[j] - inputs[i]) for j in range(start, i))

print(dp[-1])


### FIXED CODE ###

import numpy as np


N, K = map(int, input().split())
inputs = np.array([int(i) for i in input().split()])

dp = np.zeros(N, dtype=int)
for i in range(1, N):
    start = max(0, i-K)
    dp[i] = (dp[start:i] + abs(inputs[i] - inputs[start:i])).min()

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

# -*- coding:utf-8 -*-
n,m = map(int, input().split())

res = []
for i in range(m):
  res.append(input().split())

que = []
for a1,a2 in res:
  if a2 == 'AC':
    que.append(a1)
  
num = set(que)

ac = 0
wa = 0
c = ''
for b in num:
  for c1,c2 in res:
    if c1 == b and c2 == 'AC':
      #print(b,c1,c2)
      ac += 1
      break
    elif c1 == b and c2 =='WA':
      #print(b,c1,c2)
      wa += 1

print(ac,wa)

### FIXED CODE ###

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

ac = [False] * N
wa = [0] * N
for _ in range(M):
    p, S = input().split()
    p = int(p) - 1
    if S == 'AC':
        ac[p] = True
    else:
        if not ac[p]:
            wa[p] += 1

a = 0
b = 0
for i in range(N):
    if ac[i]:
        a += 1
        b += wa[i]
print(*[a, b])
### BUGGY CODE ###

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

res = 0
asum = [0]
axor = [0]

for i in A:
    asum.append(asum[-1] + i)
    axor.append(axor[-1] ^ i)

for l in range(N):
    ok = l+1
    ng = N+1
    while(ng - ok > 1):
        r = (ok + ng) // 2
        s = (axor[r] ^ axor[l])
        t = (asum[r] - asum[l])
        if s == t:
            ok = r
        else:
            ng = r
    
    res += ok - l
         
print(res)

### FIXED CODE ###

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

res = 0
asum = [0]
axor = [0]

for i in A:
    asum.append(asum[-1] + i)
    axor.append(axor[-1] ^ i)

for l in range(N):
    ok = l+1
    ng = N+1
    while(ng - ok > 1):
        r = (ok + ng) // 2
        s = (axor[r] ^ axor[l])
        t = (asum[r] - asum[l])
        if s == t:
            ok = r
        else:
            ng = r
    
    res += ok - l
         
print(res)
### BUGGY CODE ###

n, q = map(int, input().split())
queue = []
for i in range(n):
    name, time = input().split()
    queue.append({"name": name, "time": int(time)})
t = 0
while len(queue) != 0:
    #print([queue[i]["time"] for i in range(len(queue))])
    if queue[0]["time"] <= q:
        t += queue[0]["time"]
        name = queue[0]["name"]
        queue.remove(queue[0])
        print("{} {}".format(name, t))
    else:
        queue = queue[1:] + \
            [{"name": queue[0]["name"], "time":queue[0]["time"] - q}]
        t += q



### FIXED CODE ###

from collections import deque
n, q = map(int, input().split())
queue = deque()
for i in range(n):
    name, time = input().split()
    queue.append({"name": name, "time": int(time)})
t = 0
while len(queue) != 0:
    #print([queue[i]["time"] for i in range(len(queue))])
    head = queue.popleft()
    if head["time"] <= q:
        t += head["time"]
        name = head["name"]
        print("{} {}".format(name, t))
    else:
        queue.append({"name": head["name"], "time": head["time"] - q})
        t += q
### BUGGY CODE ###

import sys

def solve():
    n = int(input())
    a = [int(input()) for i in range(n)]
    dp = [1] * n

    for i in range(n):
        for j in range(i):
            if a[j] < a[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    ans = max(dp)

    print(ans)

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()

### FIXED CODE ###

from sys import stdin

def solve():
    n = int(stdin.readline())
    A = [int(stdin.readline()) for i in range(n)]

    inf = 10**9 + 1
    dp = [inf] * n

    for a in A:
        j = nibutan(dp, a)
        dp[j] = a

    for i, v in enumerate(dp):
        if v == inf:
            print(i)
            return

    print(n)

def nibutan(dp, a):
    btm = -1
    top = len(dp)

    while top - btm > 1:
        mid = (top + btm) // 2
        if dp[mid] >= a:
            top = mid
        else:
            btm = mid

    assert 0 <= top < len(dp)
    return top

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

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

from statistics import median

N, K = [int(x) for x in input().split()]
line_in_dice = list([int(x) for x in input().split()])

max_value = 0

for i in range(N):
    if i + K > N:
        break

    check = 0
    for x in range(K):
        check += median(range(1, line_in_dice[i + x] + 1))

    if check > max_value:
        max_value = check

print(max_value)


### FIXED CODE ###

from statistics import median
from time import time

t = time()

N, K = [int(x) for x in input().split()]
line_in_dice = list([int(x) for x in input().split()])

result = [0] * (N + K)

result[0] = line_in_dice[0]
result[K] -= line_in_dice[0]

max_point = 0
max_value = 0

for i in range(1, N):
    result[i] += (result[i - 1] + line_in_dice[i])
    result[i + K] -= line_in_dice[i]

    if result[i] > max_value:
        max_point = i
        max_value = result[i]


def create_median(x):
    if x % 2 == 1:
        return (1 + x) // 2
    else:
        return ((x // 2) + (x // 2 + 1)) / 2


print(sum(create_median(x)
          for x in line_in_dice[max_point - K + 1: max_point+1]))
### BUGGY CODE ###

from itertools import product
from collections import deque
import numpy as np
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

X = iter(open(0).readlines())
h, w = map(int, next(X).split())
ch, cw = map(int, next(X).split())
dh, dw = map(int, next(X).split())
dp = Grid([x.strip() for x in X], function=lambda x: 10**6 if x == '.' else -1)

def dfs(root):
    x, y, d = root
    dp[y, x] = 0
    stack = [root]
    while stack:
        x, y, d = stack.pop()
        if dp[y, x] < d:
            continue
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+dx, y+dy
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d:
                if dp[ny, nx] > d:
                    dp[ny, nx] = d
                    stack.append((nx, ny, d))
        for dx, dy in product(range(-2, 3), repeat=2):
            if abs(dx) + abs(dy) < 2:
                continue
            nx, ny = x+dx, y+dy                
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d+1:
                if dp[ny, nx] > d+1:
                    dp[ny, nx] = d+1
                    stack.append((nx, ny, d+1))
dfs((cw-1, ch-1, 0))
if dp[dh-1, dw-1] == 10**6:
    print(-1)
else:
    print(dp[dh-1, dw-1])

### FIXED CODE ###

from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] == 10**6:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])
### BUGGY CODE ###

from math import factorial


m = 1000000007


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


def F(r, c):
    path = (factorial(r + c) % m) * pow(factorial(r) * factorial(c), m - 2, m) % m
    return path


ans = 0
for i in range(r1, r2 + 1):
    for j in range(c1, c2 + 1):
        ans = (ans + F(i, j)) % m
print(ans)


### FIXED CODE ###

m = 1000000007


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

nf = 10 ** 6 * 2 + 100
fact = [0] * (nf + 1)
fact[0] = 1
for i in range(nf):
    fact[i + 1] = fact[i] * (i + 1) % m


def F(r, c):
    path = (fact[r + c + 2] % m) * pow(fact[r + 1] * fact[c + 1], m - 2, m) % m
    return path - 1


r1 -= 1
c1 -= 1

ans = F(r2, c2)
ans -= F(r1, c2)
ans -= F(r2, c1)
ans += F(r1, c1)
ans = ans % m

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

def popcount(x):
    ans = 0   
    while x > 0:
        if x & 1:
            ans += 1
        x >>= 1
    return ans
              
def f(x, pc, memo=None):
    if memo and (x, pc) in memo:
        return memo[(x, pc)]
    r = x % pc
    if memo:  
        memo[(x, pc)] = r
    return r  
              
N = int(input())
X = input()   
              
x = int(X, 2) 
              
memo = {}     
pc_x = X.count('1')
              
for i in range(N):
    if X[i] == '1':
        pc = pc_x - 1
    else:     
        pc = pc_x + 1
    if pc == 0:
        print('0')
        continue
    f_x = f(x, pc, memo)
    f_res = f(1<<(N-i-1), pc, memo)
    if X[i] == '1':
        f_i = f_x - f_res
    else:     
        f_i = f_x + f_res
    f_i = (f_i + 2 * pc) % pc
    ans = 1   
    while f_i > 0:
        ans += 1
        pc = popcount(f_i)
        f_i = f(f_i, pc)
    print(ans)
              

### FIXED CODE ###

N = int(input())
X = input()   
              
x_val = int(X, 2)
pc_x = X.count('1')
              
x_mod_pc_x_plus_1 = x_val % (pc_x + 1)
x_mod_pc_x_minus_1 = x_val % max(pc_x - 1, 1)
              
for i in range(N):
    if X[i] == '1':
        pc = pc_x - 1
        if pc == 0:
            print(0)
            continue
        val = (x_mod_pc_x_minus_1 - pow(2, N-i-1, pc)) % pc
    else:     
        pc = pc_x + 1
        val = (x_mod_pc_x_plus_1 + pow(2, N-i-1, pc)) % pc
    ans = 1   
    while val > 0:
        val %= bin(val).count('1')
        ans += 1
    print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
B=[0]*N
for n in range(N,0,-1):
    if A[n-1]==1:
        B[n-1]=1
        for x in range(1,int(n**0.5)+1):
            if n%x==0:
                if x**2==n:
                    A[x-1]=(A[x-1]+1)%2
                else:
                    y=n//x
                    A[x-1]=(A[x-1]+1)%2
                    A[y-1]=(A[y-1]+1)%2
print(sum(B))
for i in range(N):
    if B[i]==1:
        print(i+1,end=" ")

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=[0]*N
for n in range(N,0,-1):
    if A[n-1]==1:
        B[n-1]=1
        for x in range(1,int(n**0.5)+1):
            if n%x==0:
                if x**2==n:
                    A[x-1]=(A[x-1]+1)%2
                else:
                    y=n//x
                    A[x-1]=(A[x-1]+1)%2
                    A[y-1]=(A[y-1]+1)%2
print(sum(B))
for i in range(N):
    if B[i]==1:
        print(i+1,end=" ")
### BUGGY CODE ###

n, k, q = map(int, input().split())
point = {}
tmp = 0

for i in range(q):
    tmp = int(input())
    if tmp in point:
        point[tmp] += 1

    else:
        point[tmp] = 1

for b in range(1, n + 1):
    tmp = 0

    if b in point:
        tmp = sum(point.values()) - point[b]

    else:
        tmp = sum(point.values())

    if tmp >= k:
        print("No")

    else:
        print("Yes")


### FIXED CODE ###

n, k, q = map(int, input().split())
point = {}
tmp = 0

for i in range(q):
    tmp = int(input())
    if tmp in point:
        point[tmp] += 1

    else:
        point[tmp] = 1

total = sum(point.values())

for b in range(1, n + 1):
    if b in point:
        if total - point[b] >= k:
            print("No")
        else:
            print("Yes")

    else:
        if total >= k:
            print("No")

        else:
            print("Yes")
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.reverse()
    mod = 7 + 10**9
    leng = len(format(max(a), 'b'))
    bit_acc = [0 for i in range(leng)]
    for i in range(n):
        #先頭から二進数を0埋めした
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                bit_acc[j] += 1
    ans = 0
    for i in range(n):
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                ans += (n - bit_acc[j]) * (2 ** (leng - j - 1))
            else:
                ans += bit_acc[j] * (2 ** (leng - j - 1))
            ans %= mod
    print((ans * 500000004) % mod)
if __name__ == "__main__":
    main()   




### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.reverse()
    mod = 7 + 10**9
    leng = len(format(max(a), 'b'))
    bit_acc = [0 for i in range(leng)]
    for i in range(n):
        #先頭から二進数を0埋めした
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                bit_acc[j] += 1
    ans = 0
    p = [pow(2,leng - 1 - j, mod) for j in range(leng)]
    for i in range(n):
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                ans += (n - bit_acc[j]) * p[j]
            else:
                ans += bit_acc[j] * p[j]
            ans %= mod
    print((ans * 500000004) % mod)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n = int(input())
five = 0

if n%2 ==0:
  for i in range(n//2):
    s = n-2*i
    while (1):
      if s%5 == 0:
        s = s//5
        five += 1
      else:
        break
  print(five)
else:
  print(0)


### FIXED CODE ###

n = int(input())
fives = n
cnt = 0
cnt2 = 0

if n%2 == 0:
  while (1):
    if fives // 5 > 0:
      fives //= 5
      cnt += 1
    else:
      break

for i in range(cnt):
  cnt2 += n // (2*5**(i+1))

print(cnt2)
### BUGGY CODE ###

import itertools
import math
import sys
from collections import Counter
from fractions import gcd
from functools import reduce

n = int(input())
a = list(map(int, input().split()))
b = [0] + a + [0]
for i in range(n):
    ans = 0
    position = 0
    for j in range(1, n + 2):
        if j - 1 == i:
            continue
        ans += abs(position - b[j])
        position = b[j]
    print(ans)


### FIXED CODE ###

import itertools
import math
import sys
from collections import Counter
from fractions import gcd
from functools import reduce

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

#coding:utf-8

N = int(input())
A = [int(i) for i in input().split()]
ans = N

for i in range(N - 1):
    left = A[i]
    right = A[i]
    for j in range(i + 1, N):
        left ^= A[j]
        right += A[j]
        if left == right:
            ans += 1
        else:
            break

print(ans)


### FIXED CODE ###

#coding:utf-8

N = int(input())
A = [int(i) for i in input().split()]
ans = 0
formula1 = 0
formula2 = 0
lastRight = 0

for left in range(N):
    rightOut = False
    if left > 0:
        formula1 ^= A[left - 1]
        formula2 -= A[left - 1]
    for right in range(lastRight, N):
        formula1 ^= A[right]
        formula2 += A[right]
        if formula1 != formula2:
            rightOut = True
            formula1 ^= A[right]
            formula2 -= A[right]
            break

    lastRight = max(left, right - rightOut) + 1
    ans += lastRight - left
print(ans)
### BUGGY CODE ###

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

i = 0
while i < len(a):
    if a[i] != i+1:
        a.remove(a[i])
        continue
    
    i += 1

if len(a) == 0:
    print(-1)
else:
    print(n-len(a))

### FIXED CODE ###

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

if not 1 in a:
    print(-1)
else:
    cnt = 1
    for i in range(n):
        if a[i] == cnt:
            cnt += 1

    print(n - cnt + 1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
N,W=list(map(int,sys.stdin.readline().split()))

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

WL=[0]* N
VL=[0]*N

for i in range(N):
    w,v=list(map(int,sys.stdin.readline().split()))
    WL[i]=w
    VL[i]=v


def dfs(W,i):
    if i==N:
        return 0
    if dp[W][i]:
        return dp[W][i]
    if W-WL[i]>=0:
        dp[W][i]=max(dfs(W,i+1),dfs(W-WL[i],i+1)+VL[i])
        return dp[W][i]
    else:
        dp[W][i]=dfs(W,i+1)
        return dp[W][i]

print(dfs(W,0))

### FIXED CODE ###

def main():
    import sys
    sys.setrecursionlimit(10**7)
    N,W=list(map(int,sys.stdin.readline().split()))

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

    WL=[0]*N
    VL=[0]*N

    for i in range(N):
        w,v=list(map(int,sys.stdin.readline().split()))
        WL[i]=w
        VL[i]=v

    for i in range(1,N+1):
        for w in range(1,W+1):
            if w>=WL[i-1]:
                a=dp[i-1][w-WL[i-1]]+VL[i-1]
                b=dp[i-1][w]
                dp[i][w]=max(a,b)
            else:
                dp[i][w]=dp[i-1][w]
    print(dp[-1][-1])
main()
### BUGGY CODE ###

import numpy as np

N, K, Q = map(int, input().split())
A = [input() for i in range(Q)]
me =np.full(N, K) 
for i in range(Q):
    me -= 1
    me[int(A[i])-1] += 1
for i in range(N):
    if me[i]>0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

import numpy as np
N, K, Q = map(int, input().split())
a = np.zeros(N)
for i in range(Q):
    A = int(input())
    a[A-1] += 1
for i in range(N):
    if a[i] > Q-K:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import sys
S = input()
Q = int(input())
pin = 0
for i in range(Q):
  t = list(sys.stdin.readline().split())
  if int(t[0]) == 1:
    pin += 1
  else:
    if int(t[1]) % 2 == pin % 2 :
      S = S + t[2]
    else:
      S = t[2] + S
if pin % 2 == 1:
  S = S[::-1]
print(S)


### FIXED CODE ###

import sys
S = input()
Q = int(input())
pin = 0
left = ''
right = ''
for i in range(Q):
  t = list(sys.stdin.readline().split())
  if int(t[0]) == 1:
    pin += 1
  else:
    if int(t[1]) % 2 == pin % 2 :
      right = right + t[2]
    else:
      left = t[2] + left
S = left + S + right
if pin % 2 == 1:
  S = S[::-1]
print(S)
### BUGGY CODE ###

import math
import copy

def gcd(a,b):
    if b==0:return a
    return gcd(b,a%b)

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

if N==2:
    print(max(A))
    exit()
else:
    max=0
    for i in range(N):
        x = copy.deepcopy(A)
        del x[i]
        element = gcd(x[0], x[1])
        if N==2:
            c = element
        else:
            for i in range(2,N-1):
                element=gcd(element,x[i])
            c = element
        if c >= max:
            max = c
print(max)


### FIXED CODE ###

def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)

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

AL=[0]*N
AR=[0]*N
for i in range(N):
    if i == 0:
        AL[0] = A[0]
        AR[0] = A[N-1]
    else:
        AL[i] = gcd(AL[i-1],A[i])
        AR[i] = gcd(AR[i-1],A[N-i-1])

max=0
for i in range(N):
    if i == 0:
        n_ex_gcd =  AR[N-2]
    elif i == N-1:
        n_ex_gcd = AL[N-2]
    else:
        n_ex_gcd = gcd(AL[i-1],AR[N-i-2])
    if n_ex_gcd > max:
        max = n_ex_gcd
print(max)
### BUGGY CODE ###

import copy
n=int(input())
string=[]
ang=0
charcou=[[0]*26 for i in [1]*n]
for c in range(n):
    string.append(input())
    for d in range(10):
        charcou[c][ord(string[c][d])-97]+=1

for c in range(n):
    for d in range(c+1,n):
        if charcou[c]==charcou[d]:
            ang+=1
print(ang)

### FIXED CODE ###

n=int(input())
string=[]
ang=0
charcou=[[0]*26 for i in [1]*n]
for c in range(n):
    string.append(input())
    for d in range(10):
        charcou[c][ord(string[c][d])-97]+=1
charcou.sort()
c=0
while c<n-1:
    comb=1
    while charcou[c]==charcou[c+1]:
        comb+=1
        c+=1
        if c>=n-1:
            break
    if comb!=1:
        ang+=int(comb*(comb-1)/2)
    c+=1
print(ang)
### BUGGY CODE ###

k, s = map(int, input().split())
cnt = 0

for i in range(k+1):
    for j in range(k+1):
        for l in range(k+1):
            if i + j+ l == s:
                cnt += 1
                
print(cnt)

### FIXED CODE ###

k, s = map(int, input().split())
cnt = 0

for i in range(k+1):
    for j in range(k+1):
        l = s-i-j
        if 0 <= l <= k:
            cnt += 1
            
print(cnt)
### BUGGY CODE ###

from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
import fractions
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

n = I()
A = LI()

cnt = [0] * n

sa = set(A)

for v in sa:
    if cnt[v-1] != 0:
        continue
    cnt[v-1] = A.count(v)

for c in cnt:
  print(c)


### FIXED CODE ###

from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
import fractions
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

n = I()
A = LI()

cnt = [0] * n

sa = set(A)
csa = Counter(A)

for v in sa:
    if cnt[v-1] != 0:
        continue
    cnt[v-1] = csa[v]

for c in cnt:
  print(c)
### BUGGY CODE ###

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

mod = 10**9 + 7

out = 0
for i in range(n - 1):
    for j in range(n - i - 1):
        k = i + j + 1
        # print(A[i], A[k])
        out += (A[i] * A[k])
        out %= mod
print(out)

### FIXED CODE ###

mod = 10**9 + 7
n = int(input())
A = list(map(lambda x: int(x) % mod, input().split()))

# out = 0
# for i in range(n - 1):
#     for j in range(n - i - 1):
#         k = i + j + 1
#         # print(A[i], A[k])
#         out += (A[i] * A[k])
#         out %= mod
B = A[1:n]
B_s = 0
for i in range(n - 1):
    B_s += B[i] % mod

out = 0
for i in range(n - 1):
    out += A[i] * B_s
    out %= mod
    B_s -= A[i + 1]
    B_s %= mod
    if B_s < 0:
        B_s += mod

print(out)