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

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

Output the maximum value $j–i$ in a single line. If there is no such $i$ and $j$, just output $-1$.

Examples