D — Run of the Cards

“Yes, that's upside down” – whispers Domagoj, looking at Mate's hand while playing a heavily modified version of the card game Hanabi. For the sake of simplicity, Mate is holding N cards in his hands, numbered 1, 2, …, N in a certain order. (Each number from 1 to N appears exactly once.) As when playing the real game, he cannot voluntarily change the card order.

Just so the task is at least somewhat related to the story, Domagoj will point for Mate to a contiguous subarray of cards. (He can point to a single card too, but he will point to at least one card.) Mate will then “rotate” that contiguous subarray and put it back. (Rotating can be thought of as taking all the cards in the given subarray and swapping the first and last card, then the second and the second to last card, and so on.)

A fixed point is a card whose number matches its position in hand, counting from Domagoj's left side. Like all of us, Domagoj is very fond of fixed points. Therefore, he'd like the number of fixed points to be as great as possible after rotating the given subarray.

Help Domagoj find out which contiguous subarray he needs to point out so that the number of fixed points in Mate's hand after rotating that subarray is maximal.

Input Specification

The first line of the input contains a positive integer N (1 ≤ N ≤ 500 000), the number of cards in Mate's hand.

The following line contains the numbers on the cards in Mate's hand in the order that Domagoj sees them.

Output Specification

You must output a single line containing A and B, the numbers on the cards that are the beginning and the end of the required contiguous subarray, in that order, separated by a space. If there are multiple options, output any of them.

Sample Input 1

1. 4
2. 3 2 1 4

download as text file

Output for Sample Input 1

1. 3 1

download as text file

Sample Input 2

1. 2
2. 1 2

download as text file

Output for Sample Input 2

1. 1 1

download as text file

Sample Input 3

1. 7
2. 3 6 5 7 4 1 2

download as text file

Output for Sample Input 3

1. 3 2

download as text file

Clarification of the Samples

In the first test case, after rotating the contiguous subarray that starts with 3 and ends with 1, the cards will be ordered 1 2 3 4, and now all the cards are fixed points. In this example, the given output is the only correct output.

In the second test case, rotating any subarray consisting of only one card results in the same card order, the one that produces the maximal number of fixed points.

Original Problem

Croatian Open Competition in Informatics 2017/2018, Contest #2, Doktor