# CF978F Mentors

• 46通过
• 64提交
• 题目来源
• 评测方式 RemoteJudge
• 标签
• 难度 普及/提高-
• 时空限制 3000ms / 256MB
• 提示：收藏到任务计划后，可在首页查看。

## 题意翻译

有 $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.

提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。