Mentors

题意翻译

有 $n$ ($ 2 \le n \le 2 \cdot 10^5 $) 个程序员，编号从 $1$ 到 $n$。第 $i$ 个程序员有一个能力值 $r_i$ ($ 1 \le r_i \le 10^9 $)。 他们当中有 $k$ ($ 0 \le k \le \min(2 \cdot 10^5, \frac{n \cdot (n - 1)}{2}) $) 对程序员 $x$ 和 $y$ ($1 \le x, y \le n$, $ x \not = y $) 会发生口角。$x$ 和 $y$ 是无序的，但是保证不会重复描述某两个人之间的口角。 规定一个程序员 $a$ 可以成为另一个程序员 $b$ 的导师，仅当 $a$ 的能力值严格大于 $b$ 的能力值 ($ r_a > r_b $)，且 $a$, $b$ 之间没有发生口角。 现在请你求出，对于每一个程序员，他可以成为多少人的导师。 由 @Tweetuzki 提供翻译

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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.

输入输出样例

输入样例 #1

4 2
10 4 10 15
1 2
4 3

输出样例 #1

0 0 1 2 

输入样例 #2

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

输出样例 #2

5 4 0 5 3 3 9 0 2 5 

说明

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.