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:
/**
 * Created by IntelliJ IDEA.
 * User: piyushd
 * Date: 1/31/11
 * Time: 1:58 AM
 * To change this template use File | Settings | File Templates.
 */
public class SpoiltPermutation {

	int[] reverse(int[] a, int l, int r){
		for(int i = l, j = r; i < j; i++, j--){
			int temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
		return a;
	}

    void run(){
		int N = nextInt();
		int[] a = new int[N + 2];
		a[0] = 0; a[N + 1] = N + 1;
		for(int i = 1; i <= N; i++) a[i] = nextInt();

		N += 2;
		int l = -1, r = -1;
		for(int i = 0; i < N - 1; i++)
			if(a[i + 1] - a[i] > 1){
				if(r == -1) r = a[i + 1];
				else if(l == -1) l = a[i];
			}

		if(l == -1 || r == -1){

			System.out.println("0 0");

		}else{

			int[] b = new int[N];
			for(int i = 0; i < N; i++) b[i] = i;
			b = reverse(b, l, r);

			boolean ok = true;
			for(int i = 0; i < N && ok; i++) ok = b[i] == a[i];

			if(ok){
				System.out.println(l + " " + r);
			}else{
				System.out.println("0 0");
			}
		}
    }

    int nextInt(){
        try{
            int c = System.in.read();
            if(c == -1) return c;
            while(c != '-' && (c < '0' || '9' < c)){
                c = System.in.read();
                if(c == -1) return c;
            }
            if(c == '-') return -nextInt();
            int res = 0;
            do{
                res *= 10;
                res += c - '0';
                c = System.in.read();
            }while('0' <= c && c <= '9');
            return res;
        }catch(Exception e){
            return -1;
        }
    }

    long nextLong(){
        try{
            int c = System.in.read();
            if(c == -1) return -1;
            while(c != '-' && (c < '0' || '9' < c)){
                c = System.in.read();
                if(c == -1) return -1;
            }
            if(c == '-') return -nextLong();
            long res = 0;
            do{
                res *= 10;
                res += c-'0';
                c = System.in.read();
            }while('0' <= c && c <= '9');
            return res;
        }catch(Exception e){
            return -1;
        }
    }

    double nextDouble(){
        return Double.parseDouble(next());
    }

    String next(){
        try{
            StringBuilder res = new StringBuilder("");
            int c = System.in.read();
            while(Character.isWhitespace(c))
                c = System.in.read();
            do{
                res.append((char)c);
            }while(!Character.isWhitespace(c=System.in.read()));
            return res.toString();
        }catch(Exception e){
            return null;
        }
    }

    String nextLine(){
        try{
            StringBuilder res = new StringBuilder("");
            int c = System.in.read();
            while(c == '\r' || c == '\n')
                c = System.in.read();
            do{
                res.append((char)c);
                c = System.in.read();
            }while(c != '\r' && c != '\n');
            return res.toString();
        }catch(Exception e){
            return null;
        }
    }

    public static void main(String[] args){
        new SpoiltPermutation().run();
    }
}