Задача E. Сложная зависимость (Online)

Задачу добавил: alef

Успешно сдано решений: 6

Ограничения: время на тест - 2с, память - 256 Мб

Сотрудник музея Теодор, встретивший Василия, рассказал ему, что в музейном хранилище, расположенном за городом, есть несколько корпусов и материнских плат, и лучше всего поехать туда и выбрать наиболее сохранившиеся экземпляры. Для путешествия за город он предложил Василию пересесть на некое громыхающее и даже слегка дымящее транспортное средство на колесах, работавшее, как показалось Василию, на реактивной тяге. Теодор заметил в глазах Василия удивление и пояснил, что это лучший транспорт для того места, куда они направляются.
Всю поездку Василий мог думать только о том, когда же она закончится. За городом была каменистая пустыня, и этот "мобиль" (Теодор называл его более длинным словом, но Василию запомнилось только окончание) трясло на каждой кочке. Теодор как будто не замечал этого.
Наконец, они подъехали к холмам, и Теодор выскочил из "мобиля".
- Выходи! Это наше хранилище! Очень надежное место! - голос Теодора перекрывался шумом двигателя.
Василий выбрался наружу, и они отправились в хранилище. Внутри большого холма действительно было хорошо оборудованное помещение. Довольно быстро они определились с выбором материнской платы и подходящего корпуса, и вышли наружу.
Пока Теодор запирал замки, Василий рассматривал скудную растительность, покрывавшую холм. На низеньком кустарнике он заметил пару красивых щебечущих пташек и решил сделать снимок (тут надо пояснить, что снимок - это точная копия не только объекта и окружающей среды, но и звуков, и запахов... полный эффект присутствия). Беспрестанно тарахтящий агрегат на колесах этому мешал, и Василий, рассудив, что выключаться двигатель должен довольно просто, нашел-таки и повернул ключ в замке зажигания. Тишина показалась ему полным блаженством. Но спустя секунду она была нарушена криком Теодора "Опять заглох! Ну что же такое!". Теодор подбежал к Василию, схватил его за руку и потащил к странной конструкции, расположенной почти рядом с дверью:
- Сейчас местные полезут!
И действительно, в десятке метров от них возникло человекоподобное существо, небыстрым шагом направлявшееся к двери. Теодор потянул за рукоять странной конструкции, и в голову существа полетел шар, состоящий из какого-то гелеобразного вещества. Попав в "мишень", шар растекся, и существо, всем своим видом выражая огорчение, развернулось и отправилось в другую сторону.
- Мы их "зомби" зовем. Вообще их тут два вида, других мы "колдуны" называем. Ни с теми, ни с другими лучше не связываться. Хранилище нам от колдунов досталось и орудие борьбы - тоже, - пояснил Теодор и рассмеялся. - Швыряемся в них арбузами с помощью этой дынепульты! Зомби реагируют на запах, поэтому мы никогда движок не выключаем - выхлопные газы их не радуют. Но уж когда глохнет - тут надо быстро реагировать. Если до тебя доберутся - просто сжуют. Причем есть вероятность, что дынепульту сжуют тоже. Так что ездить всегда надо вдвоем - если что, один отстреливается, второй "мобиль" заводит. Так что придется тебе стать на время оператором дынепульты, пока я разберусь, почему этот тарантас заглох.
Теодор пояснил, что дынепульта готова выпускать очередной снаряд один раз в 3 секунды. Снаряд попадает в ближайшего зомби и дезориентирует его. От места, где вылезают зомби, до дынепульты, десять с половиной шагов. Снаряд пролетает это расстояние мгновенно.
Зомби появляются в целые моменты времени и за одну единицу времени совершают один шаг. По заданному расписанию появления зомби определите, который из зомби первым доберется до дынепульты.

Формат входного файла input.txt
Первая строка - целое число N (0 <= N <= 10^5) - количество зомби
Вторая строка - целые числа 0 <= A1 < A2 < ... < AN <= 10^9 через пробел - моменты появления зомби.

Формат выходного файла output.txt
Первая строка - целое число J - номер зомби, который первым доберется до дынепульты. Если ни один зомби не доберется до дынепульты, выведите -1.

Пример входного файла - 1:
11
0 1 2 3 4 5 6 7 8 9 10

Пример выходного файла - 1:
7


Пример входного файла - 2:
11
0 2 4 6 8 10 12 14 16 18 20

Пример выходного файла - 2:
-1


Пример входного файла - 3:
20
100 101 102 103 104 105 151 152 154 155 157 158 160 161 163 164 166 167 169 170

Пример выходного файла - 3:
14


Пример входного файла - 4:
30
10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70 73 76 79 82 85 88 91 94 97

Пример выходного файла - 4:
-1


Сдать задачу

Задать вопрос жюри по этой задаче