D. By the pricking of my thumbs, Pupil #1 this way comes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

While searching for an open room in the GDC, Macbeth discovers three witches. They prophesy that he will be the highest rated CodeForces competitor at UT.

Elated, Macbeth devises a masterful plan to fulfill the witches' prophecy. Instead of training on CodeForces to improve his rating, he'll gain access to the UT database and forcefully graduate students rated equal to or higher than him.

Macbeth has a list of all the CodeForces accounts connected to UT students, but he doesn't know who's behind each username. He knows the CodeForces usernames of only his friends, who know the CF usernames of only their friends. The network of who knows each other's usernames can be represented as a tree with $$$N$$$ nodes, with Macbeth at node 1. This tree spans all the competitive programmers at UT.

For Macbeth to learn more usernames, he must ask someone whose username he already knows, and this person will tell Macbeth all the usernames they know. Output the minimum number of asks Macbeth must make for him to learn of everyone who has a rating greater than or equal to his.

Input

Line 1: $$$N \:(1 \leq N \leq 10^5)$$$, specifying the number of competitive programmers at UT.

Line 2: $$$r_1\:r_2\: ...\: r_i \:... \:r_n\: (1 \leq r_i \leq 5000)$$$, where $$$r_i$$$ denotes the rating of account $$$i$$$.

Lines $$$3 .. N + 2$$$: $$$p\;q \:(1 \leq p, q \leq N)$$$, specifying that the people behind accounts $$$p$$$ and $$$q$$$ know each other's usernames.

Output

One integer specifying the minimum number of people Macbeth must ask to have the #1 rated CodeForces account at UT.

Example
Input
7
1000 1400 800 1800 3800 400 900
1 2
1 3
3 6
3 4
5 6
6 7
Output
2