JMOS
우측 버튼을 눌러 기기를 연결해주세요.
문제정보
G-MOS
100
참여자
50
정답률
64%
2
4

문제


구름이는 새로운 운영체제인 G-MOS(구름운영체제)를 만들었습니다.

G-MOS는 다른 운영체제와 다르게 특별한 점이 있는데, 바로 프로세스와 자원의 관계입니다. 자원은 프로세스의 요청에 따라서 할당되는데, G-MOS는 각 프로세스와 자원에 번호를 붙여 자원이 프로세스로 할당 될 때, 그 관계가 꼬이지 않도록 합니다.

관계가 꼬인다는 의미는 1번 프로세스가 2번 자원을 받고, 2번 프로세스가 1번 자원을 받으면 이 관계는 꼬였다고 합니다. 즉, 프로세스의 번호가 증가한다면 각 프로세스에 할당된 자원의 번호도 증가해야 합니다.

G-MOS에서 프로세스와 자원의 관계가 꼬여있으면 프로세스가 그 자원을 반납합니다. 이때 반납이 되는 자원을 최소화 하는 것이 효율적이기 때문에, 구름이는 꼬인 관계의 자원 반납이 최소화 되도록 설계했습니다.

현재 G-MOS에는 개의 프로세스와 개의 자원이 있습니다. 이때, 현재 G-MOS 상태가 주어졌을 때, 자원 반납이 필요한 프로세스의 최소 개수를 출력하시오.


입력


첫째 줄의 프로세스와 자원의 수를 나타내는 정수 이 주어집니다.
둘째 줄에 순서대로 번째 프로세스에 할당된 자원의 번호를 나타내는 정수 가 개 주어집니다. 

  • 는 서로 다른 값을 가집니다.


출력


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

입/출력 예시
:
공백
:
줄바꿈
:
예시 1
입력
5
24315
출력
2
예시 2
입력
10
10374168529
출력
5
예시 3
입력
53
4046113533391522342745330421291091513504938485312741424437322421882043193626524723311662817142551
출력
42
예시 4
입력
134
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134
출력
0
⋇ 입출력 형식을 잘 지켜주세요
Q&A
누구나 질문하고 답변할 수 있는 Q&A입니다. 문제를 풀며 어려웠던 부분에 대해 질문해보세요.
이 문제에 관한 질문 (0)