{"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 greater than the skill of the programmer $b$ $(r_a > r_b)$ and programmers $a$ and $b$ are not in a quarrel.\n\nYou 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.\n\n## Input\n\nThe 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.\n\nThe 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.\n\nEach 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.\n\n## Output\n\nPrint $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.\n\n[samples]\n\n## Note\n\nIn 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.","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$，求出有多少名程序员，使得程序员 $i$ 可以成为他们的导师。\n\n第一行包含两个整数 $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})$）——程序员总数和发生争吵的程序员对数。\n\n第二行包含一个整数序列 $r_1, r_2, \\dots, r_n$（$1 \\leq r_i \\leq 10^9$），其中 $r_i$ 表示第 $i$ 名程序员的技能。\n\n接下来的 $k$ 行，每行包含两个不同的整数 $x, y$（$1 \\leq x, y \\leq n$，$x \\ne y$）——一对发生争吵的程序员。这些配对是无序的，即如果 $x$ 与 $y$ 争吵，则 $y$ 也与 $x$ 争吵。保证输入中每对 $(x, y)$ 唯一，不存在重复的 $(x, y)$ 或 $(y, x)$。\n\n请输出 $n$ 个整数，第 $i$ 个数应等于第 $i$ 名程序员可以担任导师的程序员数量。程序员的编号顺序与输入中技能给出的顺序一致。\n\n在第一个例子中，第一个程序员无法成为任何其他人的导师（因为只有第二个程序员的技能低于他，但他们发生了争吵）。第二个程序员无法成为任何其他程序员的导师，因为他的技能是最小的。第三个程序员可以成为第二个程序员的导师。第四个程序员可以成为第一个和第二个程序员的导师，但他不能成为第三个程序员的导师，因为他们发生了争吵。\n\n## Input\n\n第一行包含两个整数 $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\n## Output\n\n请输出 $n$ 个整数，第 $i$ 个数应等于第 $i$ 名程序员可以担任导师的程序员数量。程序员的编号顺序与输入中技能给出的顺序一致。\n\n[samples]\n\n## Note\n\n在第一个例子中，第一个程序员无法成为任何其他人的导师（因为只有第二个程序员的技能低于他，但他们发生了争吵）。第二个程序员无法成为任何其他程序员的导师，因为他的技能是最小的。第三个程序员可以成为第二个程序员的导师。第四个程序员可以成为第一个和第二个程序员的导师，但他不能成为第三个程序员的导师，因为他们发生了争吵。","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 $.  \nLet $ Q \\subseteq \\binom{[n]}{2} $ be the set of unordered quarrel pairs, with $ |Q| = k $.  \n\n**Constraints**  \n1. $ 2 \\leq n \\leq 2 \\cdot 10^5 $  \n2. $ 0 \\leq k \\leq \\min\\left(2 \\cdot 10^5, \\binom{n}{2}\\right) $  \n3. $ 1 \\leq r_i \\leq 10^9 $ for all $ i \\in [n] $  \n4. For each $ \\{x, y\\} \\in Q $, $ x \\ne y $, and all pairs are distinct.  \n\n**Objective**  \nFor each programmer $ i \\in [n] $, compute:  \n$$\nm_i = \\left| \\left\\{ j \\in [n] \\setminus \\{i\\} \\,\\middle|\\, r_i > r_j \\text{ and } \\{i, j\\} \\notin Q \\right\\} \\right|\n$$  \nOutput the vector $ (m_1, m_2, \\dots, m_n) $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF978F","tags":["binary search","data structures","implementation"],"sample_group":[["4 2\n10 4 10 15\n1 2\n4 3","0 0 1 2"],["10 4\n5 4 1 5 4 3 7 1 2 5\n4 6\n2 1\n10 8\n3 5","5 4 0 5 3 3 9 0 2 5"]],"created_at":"2026-03-03 11:00:39"}}