Hot Hike

Interview

Time limit2sMemory limit512 MB

Summary

Pick a start day for a 3-day trip so the maximum temperature on the first and third days is as low as possible, breaking ties by smallest start day.

Level: Easy2 of 10
Topics: Brute force, Array, Implementation
Solved: No attempts yet

Problem

To pass the time during your vacation, you decided to go on a hike to visit a scenic lake up in the mountains. Hiking to the lake takes a full day, then you stay there for a day to rest and enjoy the scenery, and then you spend another day hiking home, for a total of three days. However, the weather this summer is ridiculously warm and sunny, and since severe dehydration is not at the top of your priority list, you want to schedule the three-day trip during days when the two hiking days are the least warm. In particular, you want to minimize the maximum temperature during the two hiking days.

Given the current forecast of daily maximum temperatures during your vacation, what are the best days for your trip?

Input

The first line of input contains an integer n (3 ≤ n ≤ 50), the length of your vacation in days. Then follows a line containing n integers t1, t2, ..., tn (−20 ≤ ti ≤ 40), where ti is the temperature forecast for the i'th day of your vacation.

Output

Output two integers d and t, where d is the best day to start your trip, and t is the resulting maximum temperature during the two hiking days. If there are many choices of d that minimize the value of t, then output the smallest such d.

Examples2

Example 1
Input
```
5
23 27 31 28 30
```
Expected output
```
2 28
```
Example 2
Input
```
4
30 20 20 30
```
Expected output
```
1 30
```