Polish version    English version  
  History of OI -> VIII OI 2000/2001


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
Stage III - results
Stage II - results
Stage I - results
Problems
Regulations
Organization
Hints
Schedule
Stats
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
VIII Olimpiada Informatyczna 2000/2001

Task: LAN
Author: Marcin Kubica
Chain

III stage contest, the second day  

Byteland had not always been a democratic country. There were also black pages in its book of history. One lovely day general Bytel - commander of the junta which had power over Byteland -- decided to finish the long-lasting time of war and released imprisoned activists of the opposition. However, he had no intention to let the leader Bytesar free. He decided to chain him to the wall with the bytish chain. It consists of joined rings and the bar fixed to the wall. Although the rings are not joined with the bar, it is hard to take them off.

    'General, why have you chained me to the prison walls and did not let rejoice at freedom!' cried Bytesar.
    'But Bytesar, you are not chained at all, and I am certain you are able to take off the rings from the bar by yourself.' perfidiously answered general Bytel, and he added 'But deal with that before a clock strikes the cyber hour and do not make a noise at night, otherwise I will be forced to call Civil Cyber Police.' 


Help Bytesar! Number the following rings of the chain with integers 1,2,...,n. We may put on and take off these rings according to the following rules: 

  • only one ring can be put on or taken off from the bar in one move,
  • the ring number 1 can be always put on or taken off from the bar,
  • if the rings with the numbers 1,...,k-1 (for 1<=k<n) are taken off from the bar and the ring number k is put on, we can put on or take off the ring number k+1. 

Write a program which:

  • reads from the text file LAN.IN the description of the bytish chain,
  • computes minimal number of moves necessary to take off all rings of the bytish chain from the bar,
  • writes the result in the text file LAN.OUT. 

Input

In the first line of the text file LAN.IN there is written one integer n, 1<=n<=1 000. In the second line there are written n integers o1,o2,...,on (each of them is either 0 or 1) separated by single spaces. If oi=1, then the i-th ring is put on the bar, and if oi=0, then the i-th ring is taken off the bar.

 

Output

The text file LAN.OUT should contain exactly one integer equal to the minimal number of moves necessary to take off all the rings of the bytish chain from the bar. 

 

Example

For the input file LAN.IN:
4
1 0 1 0
the correct answer is the output file LAN.OUT:
6




Print friendly version