JMOS - 구름LEVEL
JMOS
Quiz Info
JMOS
100points
Participant
46
Solved Rate
63%
2
2


정민이는 운영체제에 관해 공부하다가 직접 만들어 보고 싶은 마음에 운영체제를 개발하기 시작했습니다. 그리고 1년 후, 운영체제를 개발하는 데 성공합니다. 정민이는 이 운영체제를 JMOS(정민운영체제)라고 명명했습니다.

JMOS는 다른 운영체제와는 다른 특별한 점이 한 가지 있는데, 바로 프로세스와 자원의 관계입니다. 자원은 프로세스의 요청에 따라 할당되는데, JMOS에서는 각 프로세스와 자원에 번호를 붙여 자원이 프로세스로 할당될 때 그 관계가 꼬이지 않도록 하려고 합니다. 예를 들어 1번 프로세스가 2번 자원을 할당받고 2번 프로세스가 1번 자원을 할당받으면 이 관계는 꼬였다고 합니다. 쉽게 말해서, 프로세스의 번호가 증가한다면 각 프로세스에 할당된 자원의 번호도 증가해야 합니다.

만약 JMOS에서 프로세스와 자원의 관계가 꼬여있으면 프로세스가 그 자원을 반납하도록 합니다. 이때 많은 수의 프로세스가 자원을 반납하는 것보다 적은 수의 프로세스가 자원을 반납하는 것이 효율이 높기 때문에, 정민이는 꼬인 관계를 없애기 위해 필요한 최소한의 프로세스만이 자원을 반납하도록 설계했습니다.

현재 JMOS의 내부에 프로세스와 자원의 관계를 알고 있을 때, 자원을 반납해야 할 프로세스의 최소 개수를 구해주세요.


입력


첫째 줄의 프로세스와 자원의 수를 나타내는 정수 N이 주어집니다. (단, )

둘째 줄에 i번째 프로세스에 할당된 자원의 번호를 나타내는 정수 가 N개 주어집니다. (단, )

모든 는 서로 다른 값을 가집니다.


출력


꼬인 관계를 모두 없애기 위해 자원을 반납해야 할 프로세스의 최소 개수를 출력합니다.



Input/Output Example
:
Blank
:
Line Break
:
Tab
Example 1
Input
5
24315
Output
2
Example 2
Input
10
10374168529
Output
5
Example 3
Input
53
4046113533391522342745330421291091513504938485312741424437322421882043193626524723311662817142551
Output
42
Example 4
Input
134
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134
Output
0
⋇ Please keep the input and output formats carefully
Q & A
누구나 질문하고 답변할 수 있는 Q&A 게시판입니다.
다른 수강생들과 질문과 답변을 주고 받으며 함께 성장하세요!

Registered Questions (0)