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 Round52Div2_B_ implements Runnable {
    private int cont(int[] a, int n) {
        int i = 0; 
        for (;i < a.length; i++) {
            if (a[i] == n)
                break;
        }
        return i;
    }

    private boolean checkForSeq(int n, int[] a) {
        int[] z = new int[n];
        for (int i = 0; i < n; i++) {
            z[i] = i + 1;
        }
        for (int i = 0; i < a.length; i++) {
            if (a[i] != z[i])
                return false;
        }
        return true;
    }

    private int [] getsub(int [] a , int i){
        ArrayList <Integer> q = new ArrayList<Integer>();
        for (int j = i; j < a.length - 1; j++) {
            if (a[j] - a[j+1] == 1){
                if (!q.contains(a[j]))
                    q.add(a[j]);
                if (!q.contains(a[j+1]))
                    q.add(a[j+1]);
            }else{
                if (!q.contains(a[j]))
                    q.add(a[j]);
                break;
            }
        }
        int [] res = new int[q.size()]; 
        int c = 0;
        for (int j = q.size() - 1; j>=0; j--) {
            res[c++] = q.get(j);
        }
        return res;
    }
    private boolean conc(int [] a , int [] b , int i , int n){
        int count = 0;
        for (int j = 0; j < a.length; j++) {
            if (i == j-1){
                count = i;
                for (int j2 = 0; j2 < b.length; j2++) {
                    a[count++] = b[j2];
                }
                break;
            }
        }
        if (checkForSeq(n, a))
            return true;
        return false;
            
    }
    private int []  swap(int m, int k, int[] a) {
        int temp = a[m];
        a[m] = a[k];
        a[k] = temp;
        return a;
    }

    private void solve() throws IOException {
        int m = Integer.parseInt(stdin.readLine());
        String s = stdin.readLine();
        String[] f = s.split(" ");
        int[] q = new int[m];
        for (int i = 0; i < f.length; i++) {
            q[i] = Integer.parseInt(f[i]);
        }
        if (checkForSeq(m, q)) {
            System.out.println("0 0");
        } else {
            for (int i = 0; i < q.length; i++) {
                if (q[i] != i + 1) {
                    int [] a = getsub(q, i);
                    if (conc(q, a, i, m)){
                        System.out.println(a[0]+" "+a[a.length - 1]);
                        break;
                    }
                    else{
                        System.out.println("0 0");
                        break;
                    }
                }
            }
        }
    }

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

    BufferedReader stdin;

    public void run() {
        try {
            stdin = new BufferedReader(new InputStreamReader(System.in));
            solve();
            stdin.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

}