Mentors
Contest: Kotlin Heroes: Practice 3
Tags: *special, data structures, implementation

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 format:
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 format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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.

Example input:
4 2
10 4 10 15
1 2
4 3

Example output:
0 0 1 2

Example input:
10 4
5 4 1 5 4 3 7 1 2 5
4 6
2 1
10 8
3 5

Example output:
5 4 0 5 3 3 9 0 2 5

Editorial:
Firstly we should sort all programmers in non-decreasing order of their skills. Also we need to store initially numbers of the programmers (we can user array of pairs — skill and initial number of the programmer).
We will iterate through the programmers from the left to the right. The current programmer can be a mentor of all programmers to the left of him after sort and with who he are not in a quarrel. Let the number of programmers to the left is $$$x$$$. Subtract from $$$x$$$ the number of already considered programmers, who skill equals to the skill of the current programmer (it can be done, for example, with help of $$$map$$$). Also lets brute all programmers with who the current programmer in a quarrel (we can initially save for each programmer the vector of programmers with who he in a quarell; by analogy with the stoe of graphs) and if the skill of the current programmer more than the skill of a programmers, with which he in a quarrel, we should decrease $$$x$$$ on one, because this programmer is to the left of the current after sort and has been counted in $$$x$$$.
We should store by a number of the current programmer the value $$$x$$$ as answer for him.