F. Sorting by One Swap
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A permutation of natural numbers from 1 to $$$n$$$ is given. Find two non-overlapping segments such that if they are swapped, the permutation becomes sorted in ascending order.

Input

The first line of the input contains an integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).

The second line contains a permutation of integers from 1 to $$$n$$$, with numbers separated by spaces.

Output

If a solution exists, output four integers $$$pos_1$$$, $$$len_1$$$, $$$pos_2$$$, and $$$len_2$$$, where $$$pos_1$$$ is the position of the first element of the first segment (numbering starts from one), $$$len_1$$$ is the length of the first segment, $$$pos_2$$$ and $$$len_2$$$ are the same for the second segment. The inequality $$$pos_1 \lt pos_2$$$ must hold.

If no solution exists, output a single number -1.

Examples
Input
6
3 4 5 1 2 6
Output
1 3
4 2
Input
3
1 2 3
Output
-1