English · Original
Chinese · Translation
Formal · Original
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.
[samples]
## 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.
在 BerSoft 中有 $n$ 名程序员，第 $i$ 名程序员的技能为 $r_i$。
程序员 $a$ 可以成为程序员 $b$ 的导师，当且仅当程序员 $a$ 的技能严格大于程序员 $b$ 的技能（$r_a > r_b$）且程序员 $a$ 和 $b$ 之间没有争吵。
给你每个程序员的技能值，以及 $k$ 对发生争吵的程序员（配对是无序的）。对于每个程序员 $i$，求出有多少名程序员，使得程序员 $i$ 可以成为他们的导师。
第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 2 \cdot 10^5$，$0 \leq k \leq \min(2 \cdot 10^5, \frac{n \cdot (n - 1)}{2})$）——程序员总数和发生争吵的程序员对数。
第二行包含一个整数序列 $r_1, r_2, \dots, r_n$（$1 \leq r_i \leq 10^9$），其中 $r_i$ 表示第 $i$ 名程序员的技能。
接下来的 $k$ 行，每行包含两个不同的整数 $x, y$（$1 \leq x, y \leq n$，$x \ne y$）——一对发生争吵的程序员。这些配对是无序的，即如果 $x$ 与 $y$ 争吵，则 $y$ 也与 $x$ 争吵。保证输入中每对 $(x, y)$ 唯一，不存在重复的 $(x, y)$ 或 $(y, x)$。
请输出 $n$ 个整数，第 $i$ 个数应等于第 $i$ 名程序员可以担任导师的程序员数量。程序员的编号顺序与输入中技能给出的顺序一致。
在第一个例子中，第一个程序员无法成为任何其他人的导师（因为只有第二个程序员的技能低于他，但他们发生了争吵）。第二个程序员无法成为任何其他程序员的导师，因为他的技能是最小的。第三个程序员可以成为第二个程序员的导师。第四个程序员可以成为第一个和第二个程序员的导师，但他不能成为第三个程序员的导师，因为他们发生了争吵。
## Input
第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 2 \cdot 10^5$，$0 \leq k \leq \min(2 \cdot 10^5, \frac{n \cdot (n - 1)}{2})$）——程序员总数和发生争吵的程序员对数。第二行包含一个整数序列 $r_1, r_2, \dots, r_n$（$1 \leq r_i \leq 10^9$），其中 $r_i$ 表示第 $i$ 名程序员的技能。接下来的 $k$ 行，每行包含两个不同的整数 $x, y$（$1 \leq x, y \leq n$，$x \ne y$）——一对发生争吵的程序员。这些配对是无序的，即如果 $x$ 与 $y$ 争吵，则 $y$ 也与 $x$ 争吵。保证输入中每对 $(x, y)$ 唯一，不存在重复的 $(x, y)$ 或 $(y, x)$。
## Output
请输出 $n$ 个整数，第 $i$ 个数应等于第 $i$ 名程序员可以担任导师的程序员数量。程序员的编号顺序与输入中技能给出的顺序一致。
[samples]
## Note
在第一个例子中，第一个程序员无法成为任何其他人的导师（因为只有第二个程序员的技能低于他，但他们发生了争吵）。第二个程序员无法成为任何其他程序员的导师，因为他的技能是最小的。第三个程序员可以成为第二个程序员的导师。第四个程序员可以成为第一个和第二个程序员的导师，但他不能成为第三个程序员的导师，因为他们发生了争吵。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of programmers.
Let $ r = (r_1, r_2, \dots, r_n) \in \mathbb{Z}^n $ be the skill vector, where $ r_i $ is the skill of programmer $ i $.
Let $ Q \subseteq \binom{[n]}{2} $ be the set of unordered quarrel pairs, with $ |Q| = k $.
**Constraints**
1. $ 2 \leq n \leq 2 \cdot 10^5 $
2. $ 0 \leq k \leq \min\left(2 \cdot 10^5, \binom{n}{2}\right) $
3. $ 1 \leq r_i \leq 10^9 $ for all $ i \in [n] $
4. For each $ \{x, y\} \in Q $, $ x \ne y $, and all pairs are distinct.
**Objective**
For each programmer $ i \in [n] $, compute:
$$
m_i = \left| \left\{ j \in [n] \setminus \{i\} \,\middle|\, r_i > r_j \text{ and } \{i, j\} \notin Q \right\} \right|
$$
Output the vector $ (m_1, m_2, \dots, m_n) $.
API Response (JSON)
{
"problem": {
"name": "F. Mentors",
"description": {
"content": "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 ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 3000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF978F"
},
"statements": [
{
"statement_type": "Markdown",
"content": "In BerSoft $n$ programmers work, the programmer $i$ is characterized by a skill $r_i$.\n\nA programmer $a$ can be a mentor of a programmer $b$ if and only if the skill of the programmer $a$ is strictly ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "在 BerSoft 中有 $n$ 名程序员，第 $i$ 名程序员的技能为 $r_i$。\n\n程序员 $a$ 可以成为程序员 $b$ 的导师，当且仅当程序员 $a$ 的技能严格大于程序员 $b$ 的技能（$r_a > r_b$）且程序员 $a$ 和 $b$ 之间没有争吵。\n\n给你每个程序员的技能值，以及 $k$ 对发生争吵的程序员（配对是无序的）。对于每个程序员 $i$，求出有多少名程序员，使得程序员...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of programmers. \nLet $ r = (r_1, r_2, \\dots, r_n) \\in \\mathbb{Z}^n $ be the skill vector, where $ r_i $ is the skill of programmer $ i $. \n...",
"is_translate": false,
"language": "Formal"
}
]
}