## JOI '18 Spring Camp Day 1 P1 - Construction of Highway

View as PDF

Points: 30 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types

There are cities in JOI Kingdom, which are indexed by the numbers from to . City is the capital city. Each city has a value called liveliness and the initial value of liveliness of city () is . Roads in JOI Kingdom connect two different cities bidirectionally. Initially, there are no roads in JOI Kingdom. You have planned constructions of roads. The -th construction () is planned to be done in the following way.

• Two cities, and , are appointed, when one can go from city to city and cannot go from city to city by using only roads constructed at that time.
• You construct a road connecting city and city . The cost of this construction is the number of pairs of cities () satisfying the following conditions: City and City lie on the shortest path between city and city , and when one goes from city to city he arrives city before city , and the value of liveliness of city is strictly larger than that of city . Here, cities lying on the path between city and city include city and city . Notice that the shortest path between city and city is unique.
• The values of liveliness of all cities lying on the path between city and city change to the value of liveliness of city .

You want to know the cost of each construction.

#### Input Specification

The first line of input contains an integer . This means there are cities in JOI Kingdom.

The second line of input contains space separated integers . This means the initial value of liveliness of city is .

Each of following lines contains two space separated integers , . This means city and city are appointed for the -th construction of road. By using roads constructed before the -th construction, one can go from city to city and cannot go from city to city ().

#### Output Specification

Output lines to the standard output. The -th line () of output contains the cost of the -th construction of road.

#### Constraints

All input data satisfy the following conditions.

• By using roads constructed before the construction, one can go from city to city and cannot go from city to city .

#### Sample Input 1

5
1 2 3 4 5
1 2
2 3
2 4
3 5

#### Sample Output 1

0
0
0
2

#### Explanation for Sample 1

In Sample Input 1, constructions are done as follows:

• In the first construction, there are no pairs satisfying the conditions, so the cost is 0. A road connecting city 1 and city 2 is constructed and the value of liveliness of city 1 changes to 2.
• In the second construction, there are no pairs satisfying the conditions too, so the cost is 0. A road connecting city 2 and city 3 is constructed and the values of liveliness of city 1 and city 2 change to 3.
• In the third construction, there are no pairs satisfying the conditions too, so the cost is 0. A road connecting city 2 and city 4 is constructed and the values of liveliness of city 1 and city 2 change to 4.
• In the fourth construction, two pairs satisfy the conditions, so the cost is 2. A road connecting city 3 and city 5 is constructed and the values of liveliness of city 1, city 2 and city 3 change to 5.

#### Sample Input 2

10
1 7 3 4 8 6 2 9 10 5
1 2
1 3
2 4
3 5
2 6
3 7
4 8
5 9
6 10

#### Sample Output 2

0
0
0
1
1
0
1
2
3