e-olymp
Змагання

December 18 - RMQ

Задача с палочками

Хуанхан имеет n палочек разной длины. Однажды она положила их в ряд, длины которых равны s1, s2, s3, ..., sn. После измерения длины каждой палочки sk (1kn), она обнаружила что для некоторых палочек si и sj (1i < jn) длина каждой палочки расположенной между si и sj, больше si и меньше sj.

По заданным длинам s1, s2, s3, ..., sn найдите наибольшее значение ji.

Входные данные

Состоит из нескольких тестов. Каждый тест состоит из двух строк. Первая строка содержит количество палочек n (n50000). Вторая строка содержит n различных натуральных чисел (не больших 100000) - длины палочек.

Выходные данные

Выведите наибольшее значение ji для каждого теста в отдельной строке. Если не существует таких i и j, то выведите -1.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
4
5 4 3 6
4
6 5 4 3
Вихідні дані #1
1
-1