Problem: Vasya collects coins: he has exactly one coin for every year from 1 to n. Naturally, Vasya keeps all the coins in his collection in the order in which they were released. Once Vasya's younger brother made a change — he took all the coins whose release year dated from l to r inclusively and put them in the reverse order. That is, he took a certain segment [l, r] and reversed it. At that the segment's endpoints did not coincide. For example, if n = 8, then initially Vasya's coins were kept in the order 1 2 3 4 5 6 7 8. If Vasya's younger brother chose the segment [2, 6], then after the reversal the coin order will change to 1 6 5 4 3 2 7 8. Vasya suspects that someone else could have spoilt the permutation after his brother. Help him to find that out. Check if the given permutation can be obtained from the permutation 1 2 ... n using exactly one segment reversal. If it is possible, find the segment itself.

Input

The first line contains an integer n (1 ≤ n ≤ 1000) which is the number of coins in Vasya's collection. The second line contains space-separated n integers which are the spoilt sequence of coins. It is guaranteed that the given sequence is a permutation, i.e. it contains only integers from 1 to n, and every number is used exactly 1 time.

Output

If it is impossible to obtain the given permutation from the original one in exactly one action, print 0 0. Otherwise, print two numbers l r (1 ≤ l < r ≤ n) which are the endpoints of the segment that needs to be reversed to obtain from permutation 1 2 ... n the given one.

Examples

Input

8
1 6 5 4 3 2 7 8


Output

2 6


Input

4
2 3 4 1


Output

0 0


Input

4
1 2 3 4


Output

0 0

Solution (in JAVA):

Solution:

import java.io.*;
import java.util.*;
public class Template {
	//static int cnt=0;
static Scanner sc=new Scanner(System.in);
	static ArrayList<Integer> v=new ArrayList();;
	static int max=0;
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); 
	
	public static void main (String[] args) throws java.lang.Exception{
int n=sc.nextInt();
ArrayList<Integer> arr=arrInpInt(n);
int h=0,l=0;
boolean p=true;
//int h=0,l=0;
ArrayList<Integer> fin=new ArrayList();
for(int i=0;i<n;i++) {
	if(arr.get(i)!=i+1) {
		if(h!=0 && l!=0) {
			p=false;
			break;
		}
		
		h=arr.get(i);
		for(int j=i+1;j<n;j++) {
			if(arr.get(j)-arr.get(j-1)!=-1 || j==n-1) {
				if(j==n-1) {
					l=arr.get(j);
					for(int k=j;k>=i;k--) {
						fin.add(arr.get(k));
					}
					i=n+1;
break;
					}
				else {
					//System.out.println(i+" "+j);
					l=arr.get(j-1);
				for(int k=j-1;k>=i;k--) {
					//System.out.println("here");
					fin.add(arr.get(k));
				}
		      i=j-1;
				break;
			}
		}
	}
	}
	else {
		fin.add(arr.get(i));
	}
}
//System.out.println( fin);
if(!p)
	System.out.println("0 0");
else
{
	for(int i=0;i<n;i++) {
		if(fin.get(i)!=i+1) {
			p=false;
			break;
		}
	}
	if(p)
		System.out.println(l+" "+h);
	else
		System.out.println("0 0");
}

}	
	
	
	
	



	
//}
	
	
	
	
	
		
	
	
	

		
	
	




	
	

		
		
	
		
	

	
	
	

		
	
	
	
	
static long gcd(long a,long b) {
		
	
		if(b==0) {
		return a;
		}
			
		
	return gcd(b,a%b);
	
	}
	
	
	
	
	
	public static int s2i(String s) {
		return Integer.parseInt(s);
	}
	

	
	
	public static int LeastIntFn(int a,int b) {
		if((b%a)==0) {
			return (int)b/a;
		}
		return (int)(b/a)+1;
	}
	
	
	
	public static ArrayList<Long> arrInpLong(int n){
		ArrayList<Long> arr=new ArrayList();
		for(int i=0;i<n;i++) {
		arr.add(sc.nextLong());	
		}
		return arr;
	}
	public static ArrayList<String> arrInpStr(int n){
		ArrayList<String> arr=new ArrayList();
		for(int i=0;i<n;i++) {
					arr.add(sc.nextLine());	
		}
		return arr;
	}
	
	public static ArrayList<Integer> arrInpInt(int n){
		ArrayList<Integer> arr=new ArrayList();
		for(int i=0;i<n;i++) {
			int k=sc.nextInt();
			if(k>max)
				max=k;
		arr.add(k);	
		}
		return arr;
	}
	
	
	public static void printArrInt(ArrayList<Integer> arr) {
		for(int i=0;i<arr.size();i++) {
			System.out.print(arr.get(i)+" ");
	}	
		}
	
	
	public static int min(int a,int b,int c) {
		int min1=Math.min(a, b);
		return Math.min(min1,c);
	}
}