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.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Zyflair Griffane
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		PandaScanner in = new PandaScanner(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		B solver = new B();
		solver.solve(1, in, out);
		out.close();
	}
}

class B {
    public void solve(int testNumber, PandaScanner in, PrintWriter out) {
        int n = in.nextInt();
        int s = 1, t = n;
        IntDeque lst = new IntDeque(n);
        for (int i = 0; i < n; i++) {
            lst.add(in.nextInt());
        }
        while (!lst.isEmpty() && lst.peekFirst() == s) {
            s++;
            lst.pollFirst();
        }
        while (!lst.isEmpty() && lst.peekLast() == t) {
            t--;
            lst.pollLast();
        }
        String res = s + " " + t;
        boolean good = !lst.isEmpty();
        while (!lst.isEmpty()) {
            good &= lst.poll() == t--;
        }
        out.println(!good ? "0 0" : res);
    }
}

class PandaScanner {
    public BufferedReader br;
    public StringTokenizer st;
    public InputStream in;

    public PandaScanner(InputStream in) {
        br = new BufferedReader(new InputStreamReader(this.in = in));
    }

    public String nextLine() {
        try {
            return br.readLine();
        }
        catch (Exception e) {
            return null;
        }
    }

    public String next() {
        if (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(nextLine().trim());
            return next();
        }
        return st.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    }

class IntDeque implements Iterable<Integer> {

    private int capacity;
    private int size = 0;
    private int front = 0;
    private int back = 0;
    private int[] deque;
    public IntDeque() {
        this(100);
    }
    public IntDeque(int capacity) {
        this.capacity = capacity;
        deque = new int[capacity];
    }
    public void add(int x) {
        addLast(x);
    }
    public void addLast(int x) {
        ensureCapacity();
        size++;
        deque[back++] = x;
        if (back == capacity) {
            back = 0;
        }
    }
    public void ensureCapacity() {
        if (size < capacity) {
            return;
        }
        int[] newDeque = new int[capacity << 1];
        for (int i = 0, j = front; i < size; i++, j++) {
            if (j == capacity) {
                j = 0;
            }
            newDeque[i] = deque[j];
        }
        deque = newDeque;
        capacity <<= 1;
        front = 0;
        back = size;
    }
    public boolean isEmpty() {
        return size == 0;
    }
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            int done = 0;
            int curr = front;
            public boolean hasNext() {
                return done < size;
            }
            public Integer next() {
                Integer res = deque[curr++];
                if (curr == capacity) {
                    curr = 0;
                }
                done++;
                return res;
            }
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }
    public int peekFirst() {
        return deque[front];
    }
    public int peekLast() {
        return deque[back == 0 ? capacity - 1 : back - 1];
    }
    public int poll() {
        return pollFirst();
    }
    public int pollFirst() {
        if (size == 0) {
            throw new RuntimeException("IntDeque is empty!");
        }
        size--;
        int res = deque[front++];
        if (front == capacity) {
            front = 0;
        }
        return res;
    }
    public int pollLast() {
        if (size == 0) {
            throw new RuntimeException("IntDeque is empty!");
        }
        size--;
        if (back == 0) {
            back = capacity;
        }
        return deque[--back];
    }
    public String toString() {
        if (size == 0) {
            return "";
        }
        StringBuilder res = new StringBuilder();
        for (int i: this) {
            res.append(i);
            res.append(" ");
        }
        res.setLength(res.length() - 1);
        return res.toString();
    }
}