Problem F. Fortress of Vladivostok ≡
| Author: | I. Tuphanov | Time limit: | 1 sec | |
| Input file: | input.txt | Memory limit: | 256 Mb | |
| Output file: | output.txt |
Statement
Vladivostok fortress is a unique distributed system of fortifications. City government made a museum on a nearby island with n fortifications (we will call them »sites»), and has developed an unusual tourist route.
Sites are numbered from 1 to n. The site i may have an arrow (not more then one), pointing to another site ai. The value ai = 0 means that there is no arrow on the site i.
A tourist is disembarked from a helicopter to a random site i (the probability is equal for all sites). He stays at the site i for a while, and then follows the arrow to the next site ai. On the new site the tourist is doing the same thing. If ai = 0, the tourist just stays where he is. If ai was already visited by the tourist, he also stays where he is. In the evening the helicopter picks up the tourist.
Arrows are placed properly, which means that there exists a site (maybe more then one), that will be visited by a tourist disembarked at any site.
The more sites the tourist has visited, the happier he is. So the government have decided to increase the expected number of sites visited by a tourist. Due to insufficient funding, they've just decided to change ak for a single site k.
Help the government to choose k and a new ak, such that arrows are still placed properly and the expected number of visited sites is maximized.
Consider the example below. There are 8 sites. Arrows are placed properly since from any site a tourist will get to the site 1. The expected number of visited sites is 1 / 8 * (1 + 2 + 3 + 2 + 3 + 4 + 4 + 5) = 3.0. After the change, arrows are still placed properly since from any site a tourist will get to sites 1, 4, 5, 7, and 8. The expected number of visited sites is 1 / 8 * (5 + 6 + 7 + 5 + 5 + 6 + 5 + 5) = 5.5. Any other value of a1 would not give a better answer. Changing ak for any k ≠ 1 would not give a better answer.
Input file format
Input file contains an integer n followed by n integers ai.
Output file format
Output file must contain two integers — k and a new ak. If there is more then one optimal solution, output any of them. If it's impossible to increase the expected number of visited sites, output 0 0.
Constraints
1 ≤ n ≤ 5 × 105; 0 ≤ ai ≤ n.
Sample tests
| No. | Input file (input.txt) |
Output file (output.txt) |
|---|---|---|
| 1 | |
|