Polish version    English version  
  History of OI -> XII OI 2004/2005 -> Problems


 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
Schedule
Problems
Stage III - results
Stage II - results
Stage I - results
Stage II
Stage III
Regulations
For contestants
Helpful resources
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
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

Task: ska


Piggy banks


I stage competition  
Source file: ska.xxx (xxx=pas,c,cpp)
Memory limit: 32 MB

Alternative formats: PostScript | PDF

Byteazar the Dragon has N piggy banks. Each piggy bank can either be opened with its corresponding key or smashed. Byteazar has put the keys in some of the piggy banks - he remembers which key has been placed in which piggy bank. Byteazar intends to buy a car and needs to gain access to all of the piggy banks. However, he wants to destroy as few of them as possible. Help Byteazar to determine how many piggy banks have to be smashed.

Task

Write a programme which:

  • reads from the standard input the number of piggy banks and the deployment of their corresponding keys,
  • finds the minimal number of piggy banks to be smashed in order to gain access to all of them,
  • writes the outcome to the standard output.

Input

The first line of the standard input contains a single integer  N (1 <= N <= 1.000.000) - this is the number of piggy banks owned by the dragon. The piggy banks (as well as their corresponding keys) are numbered from 1 to N. Next, there are N lines: the i+1st line contains a single integer - the number of the piggy bank in which the ith key has been placed.

Output

The first and only line of the standard output should contain a single integer - the minimal number of piggy banks to be smashed in order to gain access to all of the piggy banks.  

Example

For the input data:

4
2
1
2
4

the correct outcome is:

2
In the foregoing example piggy banks 1 and 4 have to be smashed.


Print friendly version