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.awt.Point;
import java.io.*;
import java.math.BigInteger;
    import java.text.*;
    import java.util.*;
import java.util.regex.*;

    public class Main{
        static class Run implements Runnable{
            //TODO parameters
            final boolean consoleIO = true;
            final String inFile = "input.txt";
            final String outFile = "output.txt";
            
            int n;
            int[] a;
            
            int st;
            int fn;
            
            boolean solve() {
                st = 0;
                while(st<n-1 && a[st]<a[st+1])
                    ++st;
                
                if(st==n-1)
                    return false;
                
                fn = st;
                while(fn<n-1 && a[fn]>a[fn+1])
                    ++fn;
                
                for(int i = fn; i < n-1; ++i)
                    if(a[i]>=a[i+1])
                        return false;
                
                
                if(st==0 && fn==n-1)
                    return true;
                    
                if(st==0)
                    return a[st]==a[fn+1]-1;
                
                if(fn==n-1)
                    return a[fn]==a[st-1]+1;
                
                return a[fn]==a[st-1]+1 && a[st]==a[fn+1]-1;
            }
            
            @Override
            public void run() {
                n = nextInt();
                a = new int[n];
                
                for(int i = 0; i < n; ++i)
                    a[i] = nextInt();
                
                print(solve()?(st+1)+" "+(fn+1):"0 0");
                close();
            }
        //=========================================================================================================================
            BufferedReader in;
            PrintWriter out;
            StringTokenizer strTok;
           
            Run() {
                if (consoleIO) {
                    initConsoleIO();
                }
                else {
                    initFileIO();
                }
            }
           
            void initConsoleIO() {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(new OutputStreamWriter(System.out));
            }
           
            void initFileIO() {
                try {
                    in = new BufferedReader(new FileReader(inFile));
                    out = new PrintWriter(new FileWriter(outFile));
                } catch (FileNotFoundException e) {
                    e.printStackTrace();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
           
            void close() {
                try {
                    in.close();
                    out.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
           
            int nextInt() {
                return Integer.parseInt(nextToken());
            }
           
            double nextDouble() {
                return Double.parseDouble(nextToken());
            }
           
            float nextFloat() {
                return Float.parseFloat(nextToken());
            }
           
            long nextLong() {
                return Long.parseLong(nextToken());
            }
           
            String nextLine() {
                try {
                    return in.readLine();
                } catch (IOException e) {
                    return "__NULL";
                }
            }
           
            boolean hasMoreTokens() {
                return (strTok == null) || (strTok.hasMoreTokens());
            }
           
            String nextToken() {
                while (strTok == null || !strTok.hasMoreTokens()) {
                    String line;
                    try {
                        line = in.readLine();
                        strTok = new StringTokenizer(line);
                    } catch (IOException e) {
                        e.printStackTrace();
                    }
                }
               
                return strTok.nextToken();
            }
           
            void cout(Object o){
                System.out.println(o);
            }
           
            void print(Object o) {
                out.write(o.toString());
            }
            
            void println(Object o) {
                out.write(o.toString() + '\n');
            }
           
            void printf(String format, Object... args) {
                out.printf(format, args);
            }
           
            String sprintf(String format, Object... args) {
            return MessageFormat.format(format, args);
        }
        }
       
        static class Pair<A, B> {
            A a;
            B b;
           
            A f() {
                return a;
            }
           
            B s() {
                return b;
            }
           
            Pair(A a, B b) {
                this.a = a;
                this.b = b;
            }
           
            Pair(Pair<A, B> p) {
                a = p.f();
                b = p.s();
            }
        }
       
        public static void main(String[] args) throws IOException {
            Run run = new Run();
            Thread thread = new Thread(run);
            thread.run();
        }
    }