Hàng cây

Điểm: 1000 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

Sunlight

Dạng bài

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ứ $i$ có độ cao là $h_i$ . 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\le i<j\le 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\dots,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\le i<j\le n$ và $h_i<h_j$ để giá trị $(j-i)$ đạt giá trị lớn nhất

Input, Output và Subtasks

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,\dots,h_n\ (h_i\le 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$ .

Subtasks

Subtask 1 $(50\%)$ : $n\le 10^3$
Subtask 2 $(50\%)$ : $n\le 10^5$

Sample 1

Input

4
4 2 1 3

Output

Sample 2

Input

3
4 2 1

Output

-1

Bình luận

Không có bình luận nào.