Как решить задачу линейным алгоритмом?

Question

[nicknamecsharp]

Задачу решить могу, но вообще не выкупаю, почему в первом тесте ответ 2 5, а не 1 4:

Отношение
Дан массив a1,a2,...an. Необходимо выбрать в нём два элемента ai и aj, такие что i < j,
и отношение aj/ai — максимально и больше 1.

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

В первой строке задано целое число 2 ⩽n⩽ 100 000 — количество элементов в массиве.

Во второй строке заданы n целых положительных чисел ai(1 ⩽i⩽n, 1 ⩽ai⩽ 5000).

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

Выведите два числа — индексы элементов i и j. Если ответов несколько, то выведите любой из них.

Если ответа нет, то выведите два нуля, разделённых пробелом.

Тесты

6
10 3 5 3 11 9
2 5

4
5 5 5 5
0 0

Answer 1

[Alexandroppolus]

Это задача про однократную покупку/продажу акции. Решается за один проход, просто надо помнить текущий максимум aj/ai, и минимальное ai (чтобы на него делить очередное значение), и соответственно индексы, при которых эти рекорды были достигнуты.

почему в первом тесте ответ 2 5, а не 1 4

индексы здесь начинаются с 1, а не с 0.
Паскальщик составлял.

Comments

[nicknamecsharp]

а почему в тесте
6
10 3 5 3 11 9
ответ 2 5, хотя под условие больше подходит 1 4 (11 / 3 больше, чем 9 / 5)

[Alexandroppolus]

nicknamecsharp, индексы начинаются с 1

[nicknamecsharp]

Alexandroppolus, спасибо. паскальщик жизнь усложнил

Answer 2

[Rsa97]

1 ⩽ i ⩽ n