Bình và An là đôi bạn thân. Hàng ngày, hai bạn cùng nhau đi bộ tới trường. Trên con đường mà hai bạn đi có một hàng cây gồm \(n\) cây, các cây được đánh thứ tự từ \(1\) đến \(n\). Bình và An rất yêu thích hàng cây này, hai bạn đã tìm hiểu và biết được độ cao của từng cây, cây thứ \(k \ (k=1,2,…,n)\) có độ cao là \(h_k\). Thật đặc biệt, các cây có độ cao đôi một khác nhau. Một hôm, An đố Bình bài toán sau: Tìm hai số \(i,j\) là chỉ số của hai cây thỏa mãn điều kiện: \(1 \leq i < j \leq n\) và \(h_i < h_j\) để giá trị \((j-i)\) đạt giá trị lớn nhất. Bình đề nghị: “Chúng ta hãy cùng lập trình giải quyết bài toán này.”

Yêu cầu: Cho \(n\) số nguyên dương đôi một khác nhau \(h_1,h_2,…,h_n\) là độ cao của \(n\) cây, hãy tìm hai số \(i,j\) là chỉ số của hai cây mà \(1 \leq i < j \leq n\) và \(h_i < h_j\) để giá trị \((j-i)\) đạt giá trị lớn nhất.

Input

• Dòng đầu chứa một số nguyên dương \(n\).
• Dòng thứ hai gồm \(n\) số nguyên dương đôi một khác nhau \(h_1,h_2,…,h_n \ (h_i \leq 10^6).\)

Output

• Một dòng chứa một số là giá trị \((j-i)\) lớn nhất tìm được. Nếu không tồn tại hai chỉ số \(i,j\) thỏa mãn thì in ra \(-1\).

Scoring

• Subtask #1 (\(50\%\) số điểm): \(n \leq 10^3\).
• Subtask #2 (\(50\%\) số điểm): \(n \leq 10^5\).

Example

4
4 2 1 3 

2

3
4 2 1 

-1