e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Соревнования

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