Піднімайся на Ультрас#6587

Піднімайся на Ультрас

1 секунда

64 мегабайти

Дуже легка

Топографічна виразність вершини є важливою характеристикою для альпіністів і визначається наступним чином: виразність вершини $p$ з висотою $h$ над рівнем моря є найбільшим $d$ , таким що будь-який шлях від $p$ до будь-якої строго вищої вершини повинен пройти через точку з висотою $h - d$ h-d. Якщо немає жодної строго вищої вершини, то виразність дорівнює $h$ . Вершини, у яких топографічна виразність становить не менше $150000$ сантиметрів (точність важлива для альпіністів!), називаються "Ультра".

Вам потрібно створити програму, яка визначить усі Ультра в двовимірному профілі гірського хребта, представленому як послідовність точок. Зверніть увагу, що горизонтальна відстань між точками не має значення; важлива лише висота кожної точки. На малюнку нижче, Ультра є точки $7$ , $12$ , $14$ , $20$ і $23$ .

Вхідні дані

Перший рядок містить ціле число $N$ ( $3 \leq N \leq 1 0^{5}$ 3 \le N \le 10^5), що представляє кількість точок у профілі. Другий рядок містить $N$ цілих чисел $H_{i}$ H_i, що вказують висоти (в сантиметрах) точок, у порядку їх появи в профілі ( $0 \leq H_{i} \leq 1 0^{6}$ 0 \le H_i \le 10^6 для $i = 1, 2, \dots, N$ i = 1, 2, \ldots, N). Послідовні точки мають різні висоти ( $H_{i} \neq = H_{i + 1}$ H_i \ne H_{i+1} для $i = 1, 2, \dots, N - 1$ i = 1, 2, \ldots, N-1), тоді як перша і остання точки знаходяться на рівні моря ( $H_{1} = H_{N} = 0$ H_1 = H_N = 0). Ви можете бути впевнені, що профіль містить принаймні одну Ультра.

Вихідні дані

Виведіть рядок з індексами всіх Ультра в гірському хребті, у порядку їх появи в профілі.

Приклади

Приклад 1