eolymp
bolt
Try our new interface for solving problems
Problems

Sticks Problem

Sticks Problem

Time limit 1 second
Memory limit 128 MiB

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

Input example #1
4
5 4 3 6
4
6 5 4 3
9
12 4 8 7 5 9 6 3 1
Output example #1
1
-1
4