Card block reversal

Interview

Time limit1sMemory limit128 MB

Summary

Given a permutation of 1..N, choose one contiguous block to reverse so that the final number of positions i with card i is maximized, breaking ties by leftmost start then leftmost end.

Level: Medium6 of 10
Topics: Array, Hash map, Implementation
Solved: No attempts yet

Problem

Mate holds $N$ cards in one hand. The cards carry the numbers $1$ through $N$ , each number exactly once, and their order in the hand is already fixed. Mate cannot change that order on his own.

Domagoj points at one contiguous block of cards. He may point at a single card, but he always points at at least one card. Mate rotates the block Domagoj pointed at by $180$ degrees and puts it back. The first card of the block swaps places with the last one, the second card swaps places with the second to last one, and the remaining cards swap places the same way. The block ends up reversed.

Domagoj likes fixed points. A fixed point is a card whose number equals its position in the hand, counted from Domagoj's left. He wants the number of fixed points after the reversal to be as large as possible.

Find the block Domagoj has to point at.

Input

The first line contains the number of cards $N$ . ( $1 \le N \le 500000$ )

The second line contains $N$ numbers separated by spaces, the numbers on the cards from Domagoj's left to his right. Each number from $1$ to $N$ appears exactly once.

Output

Print, on one line and in this order, the number $A$ on the first card of the chosen block and the number $B$ on its last card. If the block holds a single card, $A$ and $B$ are the same number.

Several blocks can reach the maximum number of fixed points. In that case print the block whose first card sits at the smallest position. If several such blocks remain, print the one among them whose last card sits at the smallest position.

Examples3

Example 1
Input
```
4
3 2 1 4
```
Expected output
```
3 1
```
Example 2
Input
```
2
1 2
```
Expected output
```
1 1
```
Example 3
Input
```
7
3 6 5 7 4 1 2
```
Expected output
```
3 2
```