B. Soccer
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

There are $$$2 \cdot n$$$ teams in the Soccer League. Teams are numbered from $$$0$$$ to $$$2 \cdot n - 1$$$.

Before the last round, the $$$i$$$-th team has $$$p[i]$$$ points. There will be $$$n$$$ games in the last round, where teams $$$a[i]$$$ and $$$b[i]$$$ will play against each other.

Each team wonders about the best final place their team can get. This is your task to calculate these values.

The team's final place equals the number of teams with strictly more points than their team $$$+ 1$$$. Teams with same points get the same place.

The winner of the game gets $$$3$$$ points, whereas the loser gets $$$0$$$ points. If the game ends in a draw, both teams get $$$1$$$ point each.

Input

First line contains an integer $$$n$$$ – the number of games. ($$$1 \le n \le 10^5$$$)

Second line contains $$$2 \cdot n$$$ integers – $$$p[0], p[1], \ldots, p[2 \cdot n - 1]$$$. ($$$0 \le p[i] \le 5 \cdot 10^5$$$)

Next $$$n$$$ lines contain $$$a[i]$$$ and $$$b[i]$$$. ($$$0 \le a[i], b[i] \le 2 \cdot n - 1$$$)

It is guaranteed that each number from $$$0$$$ to $$$2 \cdot n - 1$$$ occurs exactly once among arrays $$$a$$$ and $$$b$$$.

Output

In the single line print $$$2 \cdot n$$$ space-separated integers $$$t[0], t[1], \ldots, t[2 \cdot n - 1]$$$. Here, $$$t[i]$$$ must equal the best final place $$$i$$$-th team can get.

Scoring
GroupAdd. constraintsPoints
$$$0$$$examples$$$0$$$
$$$1$$$$$$n \le 2$$$$$$6$$$
$$$2$$$$$$n \le 12$$$$$$11$$$
$$$3$$$$$$n \le 200$$$$$$17$$$
$$$4$$$$$$n \le 2000$$$$$$20$$$
$$$5$$$—$$$46$$$
Example
Input
2
47 45 50 48
0 2
3 1
Output
1 2 1 1
Note

Here, $$$p = [47, 45, 50, 48]$$$ and team $$$0$$$ will play against $$$2$$$, whereas team $$$3$$$ will play against $$$1$$$. Let's calculate the best place team $$$0$$$ can get:

  • team $$$0$$$ should win team $$$2$$$. Team $$$0$$$ now has $$$47+3=50$$$ points and team $$$2$$$ has $$$50$$$ points too.
  • the game between teams $$$3$$$ and $$$1$$$ should end in a draw. Team $$$3$$$ now has $$$48+1=49$$$ points and team $$$1$$$ has $$$45+1=46$$$ points.
As a result, teams $$$0$$$ and $$$2$$$ will get first place with $$$50$$$ points, team $$$3$$$ gets third place and team $$$1$$$ gets fourth place. Thus, $$$t[0] = 1$$$.

In another scenario, team $$$3$$$ can get first place, so $$$t[3] = 1$$$. However, team $$$1$$$ can only get second place in their best scenario, so $$$t[1]$$$ should be $$$2$$$.