Sticks Problem
Sticks Problem
Xuanxuan has n sticks of different length. One day, she puts all her sticks in a line, represented by s_1, s_2, s_3, ..., s_n. After measuring the length of each stick s_k~(1 \le k \le n), she finds that for some sticks s_i and s_j~(1 \le i < j \le n), each stick placed between s_i and s_j is longer than s_i but shorter than s_j.
Now given the length of s_1, s_2, s_3, ..., s_n, you are required to find the maximum value j~–~i.
Input data
Contains multiple test cases. Each case contains two lines. First line is a single integer n~(n \le 50000), indicating the number of sticks. Second line contains n different positive integers (not larger than 10^5), indicating the length of each stick in order.
Output data
Output the maximum value j~–~i in a single line. If there is no such i and j, just output -1.
Examples
4 5 4 3 6 4 6 5 4 3 9 12 4 8 7 5 9 6 3 1
1 -1 4