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 boolean checking(int n, int[] a) {
        int[] z = new int[n];
        for (int i = 0; i < n; i++) {
            z[i] = i + 1;
            if (a[i]!=z[i])
                return false;
        }
        return true;
    }

    private int[] getSubArray(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 (checking(n, a))
            return true;
        return false;

    }

    private void solve() throws IOException {
        int m = Int();
        String s = string();
        int [] q = split(s);
        if (checking(m, q)) {
            System.out.println("0 0");
        } else {
            for (int i = 0; i < q.length; i++) {
                if (q[i] != i + 1) {
                    int[] a = getSubArray(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);
        }
    }
    
    public String string()throws IOException{
        String s = stdin.readLine();
        return s;
    }
    public int Int()throws IOException{
        int s = Integer.parseInt(stdin.readLine());
        return s;
    }
    public long Long()throws IOException{
        long s = Long.parseLong(stdin.readLine());
        return s;
    }
    public double Double()throws IOException{
        double s = Double.parseDouble(stdin.readLine());
        return s;
    }
    public int [] split(String s){
        String [] f = s.split(" ");
        int [] a = new int[f.length];
        for (int i = 0; i < a.length; i++) {
            a[i] = Integer.parseInt(f[i]);
        }
        return a;
    }

}