Cars
Турнир за Купата на Декана, 2012
Time Limit: 0.2s, Memory Limit: 64MiB
Ели мрази, когато влезе в гаража и види, че Станчо отново е излизал с колите и ги е оставил в неправилен ред. Толкова ли не можа да научи, че поршетата са до западната врата, БМВ-тата до източната, а по средата е вейронът! Толкова е просто. Но не – мъжки му работи.
Техният гараж е с размерите на нещо, което обикновените хора биха определили като паркинг пред хипермаркет. Нещо повече, той е почти изцяло пълен с коли. От началните N+1 места, в момента вътре има N коли и едно празно място.
Ели е решила да пренареди колите както тя счита, че е правилно. Поради липсата на място, единствената операция, която може да прави, е да влезе в кола и да я закара на текущото свободно място, като така то вече не е свободно, но се освобождава това, където е била колата до сега. За да премести една кола на нея са ѝ нужни 5... добре де, тъй като е момиче, да кажем 10 минути.
Виждайки подредбата, в която Станчо е оставил колите, помогнете на Ели да изчисли колко време ще ѝ отнеме да ги пренареди в "правилната" подредба, ако действа оптимално. За простота "правилната" подредба ще представим с числата 0, 1, ..., N, където с нула означаваме празното място, докато с положително число – някоя от колите. Началната подредба ще бъде пермутация на числата от 0 до N.
Техният гараж е с размерите на нещо, което обикновените хора биха определили като паркинг пред хипермаркет. Нещо повече, той е почти изцяло пълен с коли. От началните N+1 места, в момента вътре има N коли и едно празно място.
Ели е решила да пренареди колите както тя счита, че е правилно. Поради липсата на място, единствената операция, която може да прави, е да влезе в кола и да я закара на текущото свободно място, като така то вече не е свободно, но се освобождава това, където е била колата до сега. За да премести една кола на нея са ѝ нужни 5... добре де, тъй като е момиче, да кажем 10 минути.
Виждайки подредбата, в която Станчо е оставил колите, помогнете на Ели да изчисли колко време ще ѝ отнеме да ги пренареди в "правилната" подредба, ако действа оптимално. За простота "правилната" подредба ще представим с числата 0, 1, ..., N, където с нула означаваме празното място, докато с положително число – някоя от колите. Началната подредба ще бъде пермутация на числата от 0 до N.
Вход
На първия ред на стандартния вход ще бъде зададено едно цяло число N – броя коли в гаража. На следващия ред ще има N+1 цели числа A1, A2, ..., AN+1 – пермутация на числата от 0 до N, включително.
Изход
На стандартния ред изведете едно цяло число - колко минути ще са нужни на Ели за да подреди колите.
Ограничения
- 1 ≤ N ≤ 1,000
- 0 ≤ Ai ≤ N
Примерен Вход | Примерен Изход |
---|---|
2 1 2 0 | 20 |
6 3 1 0 2 6 4 5 | 60 |