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.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
import java.util.stream.IntStream;

import java.math.BigInteger;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.InputMismatchException;

public class Q3{
	static class InputReader {

		private final InputStream stream;
		private final byte[] buf = new byte[8192];
		private int curChar, snumChars;
		private String[] s;
		public InputReader(InputStream st) {
			this.stream = st;
		}
		public int read() {
			if (snumChars == -1)
				throw new InputMismatchException();
			if (curChar >= snumChars) {
				curChar = 0;
				try {
					snumChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (snumChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public int nextInt() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public long nextLong() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public int[] nextIntArray(int n) {
			int a[] = new int[n];
			s=nextLine().split(" ");
			for (int i = 0; i < n; i++) {
				a[i] = Integer.parseInt(s[i]);
			}
			return a;
		}

		public String readString() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public String nextLine() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndOfLine(c));
			return res.toString();
		}

		public boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		private boolean isEndOfLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

	}
	static InputReader sc=new InputReader(System.in);
	static PrintWriter out=new PrintWriter(System.out);

	public final long MOD = (long) 1e9 + 7;

	
	static int[] ans(int n,int[] num)throws IOException{
		int[] slope=new int[n];
		int[] impossible=new int[] {0,0};
		int[] seg=new int[2];
		
		slope[0]=(num[0]+1>0)?1:-1;
		for(int i=1;i<n;i++)
			slope[i]=(num[i]-num[i-1]>0)?1:-1;
		
		seg[0]=-1;
		for(int i=0;i<n;i++) {
			if(slope[i]==-1) {seg[0]=i-1;break;}
		}
		
		if(seg[0]==-1) {
			return impossible;
		}else {
			for(int i=0;i<n;i++) {
				if(slope[i]==-1) seg[1]=i;
			}
			Stack<Integer> q=new Stack<Integer>();
			for(int i=seg[0];i<=seg[1];i++)
				q.add(num[i]);
				
			for(int i=0;i<seg[0];i++) {
				if(num[i]!=i+1)
					return impossible;
			}
			for(int i=seg[0];i<=seg[1];i++) {
				if(q.pop()!=i+1)
					return impossible;
			}
			for(int i=seg[1]+1;i<n;i++) {
				if(num[i]!=i+1)
					return impossible;
			}
			seg[0]++;
			seg[1]++;
			return seg;
		}
	}

	public static void main(String args[])throws IOException{
		int n=nextInt();
		int[] num=nextIntArray(n);
		int[] seg=ans(n,num);
		printArray(seg);
		out.flush();
		out.close();
	}

	public static int nextInt()throws IOException{
		return sc.nextInt();
	}
	public static long nextLong()throws IOException
	{
		return sc.nextLong();
	}
	public static double nextDouble()throws IOException
	{
		return Double.parseDouble(readString());
	}
	public static String readString()throws IOException
	{
		return sc.readString();
	}
	public static String nextLine()throws IOException{
		return sc.nextLine();
	}
	public static int[] nextIntArray(int n)throws IOException{
		return sc.nextIntArray(n); 
	}
	public static void printSp(Object a)throws IOException{
		out.print(a+" ");
	}
	public static void println(Object a)throws IOException{
		out.println(a);
	}
	public static void printArray(int[] a)throws IOException{
		for(int i=0;i<a.length;i++)
		printSp(a[i]);
	}
	

}