[백준] 10775번 공항 (gold 2

import java.io.*;
import java.util.*;

public class Main{
    static int[] num;
    public static void main(String[] args )throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        int n=Integer.valueOf(br.readLine());
        num=new int[n+1];
        for(int i=1; i<=n; i++){
            num[i]=i;
        }
		
        int m=Integer.valueOf(br.readLine());
		
        //문제 전체를 관통하는 해법.
        //일단 비행기는 1-자기번호까지 중의 하나를 선택한다.
        //그럼 이때, 비행기는 자기번호가 비었으면 자기번호부터 채우는 것이 최선의 선택이라 할 수 있다.
        //3,1이 들어올때 1번 게이트를 3번으로 채우면, 뒤에오는 1번 비행기를 도킹할 게이트가 없기에
        //그러므로, 자기번호에서 차있으면 그보다 작은 수, 그보다 작은 수로 진행하면서 
        //채우면된다.
        //이를 해결하기 위해 분리집합을 사용했다.
        //유니온 과정에서 더 작은 수를 부모 노드로 갖게 설정을 하여, 
        //특정 방이 차있는 경우, 그 부모노드로 이동하고, 비었으면 그곳을
        //차 있으면 부모의 부모.. .로 나아가서 빈방에 채우는 것이다. 
        boolean[] dok=new boolean[n+1];
        boolean is=true;
        int answer=0;
        for(int i=0; i<m; i++){
            int p=Integer.valueOf(br.readLine());
            if(!is){
                continue;
            }
            int temp=Find(p);
            while(dok[temp]){
                temp=Find(temp)-1;
                if(temp<1){
                    temp=1;
                    break;
                }
            }
            if(dok[temp]){
                is=false;
                continue;
            }
            else{
                dok[temp]=true;
                answer++;
                Union(p,temp);
            }

        }
        bw.write(answer+"");
        bw.flush();

    }

    public static int Find(int v){
        if(num[v]==v){
            return v;
        }
        else{
            return num[v]=Find(num[v]);
        }
    }

    public static void Union(int a, int b){
        int fa=Find(a);
        int fb=Find(b);
        if(fa==fb) {
            return;
        }
        else if(fa>fb){
            num[fa]=fb;
        }
        else{
            num[fb]=fa;
        }
    }
}