In BerSoft $n$ programmers work, the programmer $i$ is characterized by a skill $r_i$.

A programmer $a$ can be a mentor of a programmer $b$ if and only if the skill of the programmer $a$ is strictly greater than the skill of the programmer $b$ $(r_a > r_b)$ and programmers $a$ and $b$ are not in a quarrel.

You are given the skills of each programmers and a list of $k$ pairs of the programmers, which are in a quarrel (pairs are unordered). For each programmer $i$, find the number of programmers, for which the programmer $i$ can be a mentor.


-----Input-----

The first line contains two integers $n$ and $k$ $(2 \le n \le 2 \cdot 10^5$, $0 \le k \le \min(2 \cdot 10^5, \frac{n \cdot (n - 1)}{2}))$ — total number of programmers and number of pairs of programmers which are in a quarrel.

The second line contains a sequence of integers $r_1, r_2, \dots, r_n$ $(1 \le r_i \le 10^{9})$, where $r_i$ equals to the skill of the $i$-th programmer.

Each of the following $k$ lines contains two distinct integers $x$, $y$ $(1 \le x, y \le n$, $x \ne y)$ — pair of programmers in a quarrel. The pairs are unordered, it means that if $x$ is in a quarrel with $y$ then $y$ is in a quarrel with $x$. Guaranteed, that for each pair $(x, y)$ there are no other pairs $(x, y)$ and $(y, x)$ in the input.


-----Output-----

Print $n$ integers, the $i$-th number should be equal to the number of programmers, for which the $i$-th programmer can be a mentor. Programmers are numbered in the same order that their skills are given in the input.


-----Examples-----
Input
4 2
10 4 10 15
1 2
4 3

Output
0 0 1 2 

Input
10 4
5 4 1 5 4 3 7 1 2 5
4 6
2 1
10 8
3 5

Output
5 4 0 5 3 3 9 0 2 5 



-----Note-----

In the first example, the first programmer can not be mentor of any other (because only the second programmer has a skill, lower than first programmer skill, but they are in a quarrel). The second programmer can not be mentor of any other programmer, because his skill is minimal among others. The third programmer can be a mentor of the second programmer. The fourth programmer can be a mentor of the first and of the second programmers. He can not be a mentor of the third programmer, because they are in a quarrel.

Difficulty: introductory

Starter code:

Solutions:
def ke(i):
    return a[i]
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=[]
for i in range(n):
    b.append(i)
b.sort(key=ke)
ans=[0]*n
k=0
for i in range(1,n):
    if a[b[i]]==a[b[i-1]]:
        k+=1
        ans[b[i]]=i-k
    else:
        k=0
        ans[b[i]]=i
for i in range(m):
    r1,r2=map(int,input().split())
    if (a[r1-1]>a[r2-1]):
        ans[r1-1]-=1
    elif a[r1-1]<a[r2-1]:
        ans[r2-1]-=1
for i in ans:
    print(i, end=' ')

T = input().split(' ')
n = int(T[0])
k = int(T[1])
S = input().split(' ')
for i in range(len(S)):
    S[i] = (int(S[i]), i)
Q = S.copy()
S.sort()
N = [0] * len(S)
tot = 0
for i in range(1, len(S)):
    if S[i][0] == S[i-1][0]:
        tot+=1
    else:
        tot=0
    N[S[i][1]] = i-tot
B = [0] * len(S)
for i in range(k):
    W = input().split(' ')
    a = int(W[0])
    b = int(W[1])
    if Q[a-1][0] > Q[b-1][0]:
        B[a-1] += 1
    if Q[b-1][0] > Q[a-1][0]:
        B[b-1] += 1
for i in range(len(S)-1):
    print(N[i] - B[i], end=' ')
print(N[n-1] - B[n-1])


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

cross = [0] * n
res = [0] * n

nar = list(sorted([[ar[x], x] for x in range(n)]))

cur = ['1', 0]
for x in nar:
    if x[0] == cur[0]:
        cur[1] += 1
        cross[x[1]] += cur[1]
    else:
        cur[0] = x[0]
        cur[1] = 0

for x in range(k):
    a, b = [int(x) - 1 for x in input().split()]
    if ar[a] != ar[b]:
        cross[max(a, b, key=lambda x: ar[x])] += 1

for x in range(n):
    res[x] -= cross[x]
    res[nar[x][1]] += x

print(*res)


from itertools import accumulate

def main():
	n, k = [int(_) for _ in input().split()]
	skills = [int(_) for _ in input().split()]

	b = [(r, i) for i, r in enumerate(skills)]
	b.sort()

	x = 0
	c = [0] * n
	cnt = 0
	for r, i in b:
		if r > x:
			cnt_less = cnt
		c[i] = cnt_less
		cnt += 1
		x = r

	# print(c)
	for _ in range(k):
		u, v = [int(_) for _ in input().split()]
		u -= 1
		v -= 1
		if skills[u] > skills[v]:
			c[u] -= 1
		elif skills[v] > skills[u]:
			c[v] -= 1

	print(' '.join(map(str, c)))



def __starting_point():
	main()

__starting_point()

from bisect import bisect_left

n, k = map(int, input().split())
a = [int(x) for x in input().split()]
sa = sorted(a)

ans = [0] * n
for i in range(k):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    if a[x] > a[y]:
        ans[x] -= 1
    if a[y] > a[x]:
        ans[y] -= 1

for i in range(n):
    t = bisect_left(sa, a[i])
    ans[i] += t
    print(ans[i], end=' ')


import bisect
n,k=list(map(int,input().split()))
r,o=list(map(int,input().split())),''
d={}
for i in range(k):
    a,b=list(map(int,input().split()))
    if [b]!=d.setdefault(a,[b]):
        d[a]+=[b]
    if [a]!=d.setdefault(b,[a]):
        d[b]+=[a]
rr=sorted(r)
for i in range(1,n+1):
    a=bisect.bisect_left(rr,r[i-1])
    if i in d:
        for j in d[i]:
            if r[j-1]<r[i-1]:
                a-=1
    o+=str(a)+' '
print(o)


n, k = list(map(int, input().split()))
arr = list(map(int, input().split()))
person_to_skill = {}
skill_to_numMentor = {}
person_to_numMentor = {}
for person in range(len(arr)):
    person_to_skill[person] = arr[person]
arr = sorted(arr)
temp = -1
for i in range(len(arr)):
    if arr[i] != temp:
        skill_to_numMentor[arr[i]] = i
        temp = arr[i]
for person in range(n):
    person_to_numMentor[person] = skill_to_numMentor[person_to_skill[person]]
for quarrel in range(k):
    p1, p2 = list(map(int, input().split()))
    if person_to_skill[p1 - 1] > person_to_skill[p2 - 1]:
        person_to_numMentor[p1 - 1] -= 1
    if person_to_skill[p2 - 1] > person_to_skill[p1 - 1]:
        person_to_numMentor[p2 - 1] -= 1
s = ""
s += str(person_to_numMentor[0])
for i in range(1, n):
    s += ' ' + str(person_to_numMentor[i])
print(s)

[n, k] = [int(x) for x in input().split()]
r = [int(x) for x in input().split()]
progs = [[i, x, 0, 0] for i, x in enumerate(r)]
IND = 0
RATE = 1
REL = 2
RES = 3
i = 0
while i < k:
  [a, b] = [int(x) for x in input().split()]
  a -= 1
  b -= 1
  if progs[a][RATE] > progs[b][RATE]:
    progs[a][REL] += 1
  if progs[a][RATE] < progs[b][RATE]:
    progs[b][REL] += 1
  i += 1


progs = sorted(progs, key=lambda p: p[RATE])

i = 1
count = 0
while i < n:
  cur = progs[i]
  prev = progs[i-1]
  if cur[RATE] > prev[RATE]:
    count = i
  cur[RES] = count - cur[REL]
  i += 1

progs = sorted(progs, key=lambda p: p[IND])
for p in progs:
  print(p[RES], end=' ')




def solve(n,m,a,adj):
	a = sorted(a)

	res = []
	for i in range(n):
		res.append(0)

	equal = 0
	for i in range(n):
		pos = a[i][1]
		if (i == 0):
			res[pos] = 0
			continue

		if (a[i][0] == a[i-1][0]):
			equal += 1
		else:
			equal = 0

		res[pos] = i - equal - len(adj[pos])

	for i in res:
		print(i, end = ' ')
		





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

tmp = list(map(int, input().split()))
a = []
adj = []
for i in range(n):
	a.append((tmp[i],i))
	adj.append([])


for i in range(m):
	x, y = map(int, input().split())
	x -= 1
	y -= 1
	if (a[x][0] < a[y][0]):
		adj[y].append(x)
	elif (a[x][0] > a[y][0]):
		adj[x].append(y)
	

solve(n,m,a,adj)

n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
ans = [0] * n
for i in range(k):
	x, y = [int(j) - 1 for j in input().split()]
	if a[x] < a[y]:
		ans[y] -= 1
	if a[x] > a[y]:
		ans[x] -= 1
d = {}
e = {}
f = {}
for i in a:
	d[i] = 0
	f[i] = True
	e[i] = 0
for i in a:
	d[i] += 1
	e[i] += 1

wk1 = [i for i in a]
wk1.sort()
for i in range(n):
	if (f[wk1[i]]) and (wk1[i] != wk1[0]):
		d[wk1[i]] += d[wk1[i - 1]]
		f[wk1[i]] = False
for i in range(n):
	ans[i] += d[a[i]] - e[a[i]]

for i in range(n):
	if i != n - 1:
		print(ans[i], end = " ")
	else:
		print(ans[i])


R = lambda: map(int, input().split())

n, k = R()

r = list(R())
h = sorted(r)
d = {}

d[h[0]] = 0 # d[i]: 比i小的数字数量
for i in range(1, n):
    if h[i-1] != h[i]:
        d[h[i]] = i

res = [0]*n
for i in range(n): res[i] = d[r[i]]

for i in range(k):
    a, b = R()
    a -= 1; b -= 1
    if r[a] > r[b]: res[a] -= 1
    elif r[a] < r[b]: res[b] -= 1

res = list(map(str, res))
print(' '.join(res))

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

d = {}
a = []
for x in input().split():
    x = int(x)
    if not x in d:
        d[x] = 0
    d[x] += 1
    a.append(x)
    
lst = sorted(d)
lst.reverse()

d1 = {lst[0]: d[lst[0]]}
for x in range(1, len(lst)):
    d1[lst[x]] = d1[lst[x - 1]] + d[lst[x]]

array = [0] * n
for x in range(n):
    array[x] = n - d1[a[x]]

for x in range(k):
    (l, r) = list(map(int, input().split()))
    if a[l - 1] > a[r - 1]:
        array[l - 1] -= 1
    elif a[l - 1] < a[r - 1]:
        array[r - 1] -= 1

print(*array)


n, k = map(int, input().split())
a = list(map(int, input().split()))
rec = []
rec1 = {}
for i in range(n):
    rec.append((i, a[i]))
    rec1[i + 1] = a[i]


rec = sorted(rec, key=lambda s: s[1])

num = [0] * n
j = 0
for i in range(n):
    num[rec[i][0]] = i
i = 1
while i < n:
    if rec[i - 1][1] == rec[i][1]:
        j = 1
        while i < n and rec[i - 1][1] == rec[i][1]:
            num[rec[i][0]] -= j
            j += 1
            i += 1
    i += 1

for i in range(k):
    x, y = map(int, input().split())
    if rec1[x] < rec1[y]:
        num[y - 1] -= 1
    elif rec1[y] < rec1[x]:
        num[x - 1] -= 1

print(" ".join(map(str, num)))

n,k = [int(s) for s in input().split()]
r = [int(s) for s in input().split()]
q = [0]*n
for i in range(k):
    x,y = [int(s)-1 for s in input().split()]
    if r[x] > r[y]:
        q[x] += 1
    if r[y] > r[x]:
        q[y] += 1
r1 = []
for i in range(n):
    r1.append((r[i], i))
r1.sort()
lower = 0
ans = [0]*n
for i in range(n):
    if i > 0 and r1[i][0] > r1[i-1][0]:
        lower = i
    ans[r1[i][1]] = lower-q[r1[i][1]]

print(*ans, sep=" ")

from collections import Counter
def binary(x,ar):
    low=0
    high=len(ar)-1
    while low<=high:
        mid=(low+high)//2
        if ar[mid]==x:
            break
        elif ar[mid]<x:
            low=mid+1
        else:
            high=mid-1
    return mid


n,q=list(map(int,input().split()))
l=list(map(int,input().split()))
frq=dict(Counter(l))
new=sorted(set(l))
look=[frq[new[0]]]
for i in range(1,len(new)):
    look.append(look[i-1]+frq[new[i]])
d=dict()
for i in range(q):
    li,r=list(map(int,input().split()))
    li-=1
    r-=1
    if li in d:
        d[li].append(r)
    else:
        d[li]=[r]
    
    if r in d:
        d[r].append(li)
    else:
        d[r]=[li]
enum=[]
for i in range(n):
    x=binary(l[i],new)
    if x==0:
        sum1=0
    else:
        sum1=look[x-1]
        if i in d:
            
            for j in range(len(d[i])):
                if l[d[i][j]]<l[i]:
                    sum1-=1
    enum.append(sum1)
print(*enum)
    
    
    
            



n, k = map(int, input().split())
m = list(map(int, input().split()))
new_m = [(m[i], i) for i in range(n)]
new_m.sort()
ans = [0 for i in range(n)]
last = -1
for i in range(1, len(new_m)):
    if new_m[i][0] == new_m[i - 1][0]:
        ans[new_m[i][1]] = ans[new_m[i - 1][1]]
    else:
        ans[new_m[i][1]] = i
for i in range(k):
    a, b = map(int, input().split())
    if m[a - 1] > m[b - 1]:
        ans[a - 1] -= 1
    elif m[a - 1] != m[b - 1]:
        ans[b - 1] -= 1
print(*ans)

n, k = list(map(int, input().split()))
skills = list((list(map(int, input().split()))))
quarrels = [0] * n

for _ in range(k):
    x, y = list(map(int, input().split()))
    x -= 1
    y -= 1

    if skills[x] > skills[y]:
        quarrels[x] += 1
    elif skills[y] > skills[x]:
        quarrels[y] += 1

result = [0] * n
next_p = 1

skills = sorted(enumerate(skills), key=lambda x: -x[1])

for i, skill in skills[:-1]:
    while next_p < n and skills[next_p][1] == skill:
        next_p += 1

    result[i] = n - next_p - quarrels[i]

print(' '.join(map(str, result)))


from copy import copy

n, k = map(int, input().split(' '))
l = list(map(int, input().split(' ')))
r = copy(l)

idd = dict()
for i in range(n):
    try:
        idd[l[i]].add(i)
    except:
        idd[l[i]] = {i}

nd = dict()
l.sort()

used = set()

for i in enumerate(l):
    if not i[1] in used:
        for x in idd[i[1]]:
            nd[x] = i[0]
        used.add(i[1])

d = {i:0 for i in range(n)}

for i in range(k):
    a, b = map(lambda x: int(x) - 1, input().split(' '))
    if r[a] < r[b]:
        d[b] += 1
    elif r[b] < r[a]:
        d[a] += 1

for i in range(n):
    print(nd[i] - d[i], end=' ')

from collections import Counter
def search(key,arr):
    low=0
    high=len(arr)-1
    while low<=high:
        mid=(low+high)//2
        if arr[mid]==key:
            break
        elif arr[mid]<key:
            low=mid+1
        else:
            high=mid-1
    return mid

n,q=list(map(int,input().split()))
l=list(map(int,input().split()))
d=dict()
sel=dict(Counter(l))
no=sorted(set(l))
tab=[sel[no[0]]]
for i in range(1,len(no)):
    tab.append(tab[i-1]+sel[no[i]])
for i in range(q):
    li,r=list(map(int,input().split()))
    li-=1
    r-=1
    if li in d:
        d[li].append(r)
    else:
        d[li]=[r]
    
    if r in d:
        d[r].append(li)
    else:
        d[r]=[li]
fin=[]
for i in range(n):
    x=search(l[i],no)
    if x==0:
        sum1=0
    else:
        sum1=tab[x-1]
        if i in d:
            
            for j in range(len(d[i])):
                if l[d[i][j]]<l[i]:
                    sum1-=1
    fin.append(sum1)
print(*fin)


from collections import defaultdict
n , k = input().split()
n , k = [ int(n) , int(k) ]
prog_power = defaultdict(set)
prog = []
for ind,x in enumerate(input().split()) :
    prog_power[int(x)].add(ind+1)
    prog.append(int(x))

m = defaultdict(set)
for i in range(k) :
    a1 , a2 = input().split()
    a1 , a2 = [int(a1) , int(a2) ]
    if prog[a1-1] > prog[a2-1] :
        m[a1].add(a2)
    elif prog[a1-1] < prog[a2-1] :
        m[a2].add(a1)

power = {}
sum = n
for i in sorted(prog_power.keys() , reverse = True) :
    sum -= len(prog_power[i])
    power[i] = sum
    

for ind,i in enumerate(prog) :
    mentor = power[i] - len(m[ind+1])
    print(mentor,end = ' ')














params = [int(s) for s in input().split(" ")]
n = params[0]
k = params[1]
skills = [int(s) for s in input().split(" ")]
indexes_sorted= [b[0] for b in sorted(enumerate(skills),key=lambda i:i[1])]
bad_relations={}
for i in range(k):
    items = [int(s) for s in input().split(" ")]
    first = items[0] - 1
    second= items[1] - 1
    if skills[first] > skills[second]:
        bad_relations[first] = bad_relations.get(first, 0) + 1
    elif skills[second]> skills[first]:
        bad_relations[second] = bad_relations.get(second, 0) + 1

num_the_same=0
results = {}
prev=None
for idx, index in enumerate(indexes_sorted):
    skill = skills[index]
    if skill==prev:
        num_the_same+=1
    else:
        num_the_same=0
    cnt = idx - num_the_same - bad_relations.get(index,0)
    if cnt < 0:
        cnt= 0
    results[index]= cnt
    prev= skill
final=''
for i in range(n):
    final+=str((results[i])) + " "

print(final.strip())





#!/usr/bin/env python3
from sys import stdin, stdout
from bisect import bisect_left

def rint():
    return map(int, stdin.readline().split())
#lines = stdin.readlines()

n, k = rint()
r = list(rint())
q = [0 for i in range(n)]

for i in range(k):
    x, y = rint()
    x -= 1
    y -= 1
    if r[x] > r[y]: 
        q[x] +=1
    elif r[y] > r[x]:
        q[y] +=1

ans = [-1 for i in range(n)]
r_sorted = r[:]
r_sorted.sort()
#print("r", r)
#print("r_sorted", r_sorted)
#print("q", q)
for i in range(n):
    lower = bisect_left(r_sorted, r[i])
    ans[i] =  max(0, lower - q[i])
print(*ans)

from bisect import bisect_left

n, k = map(int, input().split())
a = [int(x) for x in input().split()]
sa = sorted(a)

ans = [0] * n
for i in range(k):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    if a[x] > a[y]:
        ans[x] -= 1
    if a[y] > a[x]:
        ans[y] -= 1

for i in range(n):
    t = bisect_left(sa, a[i])
    ans[i] += t
    print(ans[i], end=' ')