시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 3626 1374 1021 41.589%

문제

오늘은 신승원의 생일이다.

박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.

공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.

공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 도킹된 게이트에는 다른 비행기가 도착할 수 없다.

이러한 사고가 일어나면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

입력

첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 105)가 주어진다.

두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 105)가 주어진다.

이후 P개의 줄에 gi (1 ≤ gi ≤ G) 가 주어진다.

출력

승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.

예제 입력 1

4
3
4
1
1

예제 출력 1

2

예제 입력 2

4
6
2
2
3
3
4
4

예제 출력 2

3

힌트

예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다.

예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불가능하다.

 

W3sicHJvYmxlbV9pZCI6IjEwNzc1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhY2Y1XHVkNTZkIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM2MjRcdWIyOThcdWM3NDAgXHVjMmUwXHVjMmI5XHVjNmQwXHVjNzU4IFx1YzBkZFx1Yzc3Y1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYzE1XHVjMmI5XHVjNmQwXHVjNzQwIFx1YzBkZFx1Yzc3Y1x1Yzc0NCBcdWI5ZGVcdWM1NDQgXHVjMmUwXHVjMmI5XHVjNmQwXHVjNWQwXHVhYzhjIFx1Yzc3OFx1Y2M5Y1x1YWQ2ZFx1YzgxY1x1YWNmNVx1ZDU2ZFx1Yzc0NCBcdWMxMjBcdWJiM2NcdWI4NWMgXHVjOTJjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjZjVcdWQ1NmRcdWM1ZDBcdWIyOTQgR1x1YWMxY1x1Yzc1OCBcdWFjOGNcdWM3NzRcdWQyYjhcdWFjMDAgXHVjNzg4XHVjNzNjXHViYTcwIFx1YWMwMVx1YWMwMVx1Yzc0MCAxXHVjNWQwXHVjMTFjIEdcdWFlNGNcdWM5YzBcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNmNVx1ZDU2ZFx1YzVkMFx1YjI5NCBQXHVhYzFjXHVjNzU4IFx1YmU0NFx1ZDU4OVx1YWUzMFx1YWMwMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHViM2M0XHVjYzI5XHVkNTYwIFx1YzYwOFx1YzgxNVx1Yzc3NFx1YmE3MCwgXHViMmY5XHVjMmUwXHVjNzQwIGlcdWJjODhcdWM5ZjggXHViZTQ0XHVkNTg5XHVhZTMwXHViOTdjIDFcdWJjODhcdWJkODBcdWQxMzAgZzxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBnPHN1Yj5pPFwvc3ViPiAmbGU7IEcpIFx1YmM4OFx1YzlmOCBcdWFjOGNcdWM3NzRcdWQyYjhcdWM5MTEgXHVkNTU4XHViMDk4XHVjNWQwIFx1YzYwMVx1YWQ2Y1x1YzgwMVx1YzczY1x1Yjg1YyBcdWIzYzRcdWQwYjlcdWQ1NThcdWI4MjQgXHVkNTVjXHViMmU0LiBcdWJlNDRcdWQ1ODlcdWFlMzBcdWFjMDAgXHViM2M0XHVkMGI5XHViNDFjIFx1YWM4Y1x1Yzc3NFx1ZDJiOFx1YzVkMFx1YjI5NCBcdWIyZTRcdWI5NzggXHViZTQ0XHVkNTg5XHVhZTMwXHVhYzAwIFx1YjNjNFx1Y2MyOVx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjMGFjXHVhY2UwXHVhYzAwIFx1Yzc3Y1x1YzViNFx1YjA5OFx1YmE3NCBcdWFjZjVcdWQ1NmRcdWM3NzQgXHVkM2QwXHVjMWM0XHViNDE4XHVhY2UwLCBcdWM3NzRcdWQ2YzQgXHVjNWI0XHViNWE0IFx1YmU0NFx1ZDU4OVx1YWUzMFx1YjNjNCBcdWIzYzRcdWNjMjlcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMmUwXHVjMmI5XHVjNmQwXHVjNzQwIFx1YWMwMFx1YzdhNSBcdWI5Y2VcdWM3NDAgXHViZTQ0XHVkNTg5XHVhZTMwXHViOTdjIFx1YWNmNVx1ZDU2ZFx1YzVkMCBcdWIzYzRcdWQwYjlcdWMyZGNcdWNmMWNcdWMxMWMgXHViYzE1XHVjMmI5XHVjNmQwXHVjNzQ0IFx1ZDU4OVx1YmNmNVx1ZDU1OFx1YWM4YyBcdWQ1NThcdWFjZTAgXHVjMmY2XHVjNWI0XHVkNTVjXHViMmU0LiBcdWMyYjlcdWM2ZDBcdWM3NzRcdWIyOTQgXHViZTQ0XHVkNTg5XHVhZTMwXHViOTdjIFx1Y2Q1Y1x1YjMwMCBcdWJhODcgXHViMzAwIFx1YjNjNFx1ZDBiOVx1YzJkY1x1ZDBhYyBcdWMyMTggXHVjNzg4XHViMjk0XHVhYzAwPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzhjXHVjNzc0XHVkMmI4XHVjNzU4IFx1YzIxOCBHICgxICZsZTsgRyAmbGU7IDEwPHN1cD41PFwvc3VwPilcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJlNDRcdWQ1ODlcdWFlMzBcdWM3NTggXHVjMjE4IFAgKDEgJmxlOyBQICZsZTsgMTA8c3VwPjU8XC9zdXA+KVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1ZDZjNCBQXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBnPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IGc8c3ViPmk8XC9zdWI+ICZsZTsgRykgXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWMyYjlcdWM2ZDBcdWM3NzRcdWFjMDAgXHViM2M0XHVkMGI5XHVjMmRjXHVkMGFjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHViMzAwXHVjNzU4IFx1YmU0NFx1ZDU4OVx1YWUzMCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM2MDhcdWM4MWMgMSA6IFsyXVs/XVs/XVsxXSBcdWQ2MTVcdWQwZGNcdWI4NWMgXHViM2M0XHVkMGI5XHVjMmRjXHVkMGFjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIDNcdWJjODhcdWM5ZjggXHViZTQ0XHVkNTg5XHVhZTMwXHViMjk0IFx1YjNjNFx1ZDBiOVx1YzJkY1x1ZDBhYyBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWM4MWMgMiA6IFsxXVsyXVszXVs/XSBcdWQ2MTVcdWQwZGNcdWI4NWMgXHViM2M0XHVkMGI5IFx1YzJkY1x1ZDBhYyBcdWMyMTggXHVjNzg4XHVhY2UwLCA0XHViYzg4XHVjOWY4IFx1YmU0NFx1ZDU4OVx1YWUzMFx1YjI5NCBcdWM4MDhcdWIzMDAgXHViM2M0XHVkMGI5IFx1YzJkY1x1ZDBhYyBcdWMyMTggXHVjNWM2XHVjNWI0XHVjMTFjIFx1Yzc3NFx1ZDZjNCBcdWNkOTRcdWFjMDBcdWM4MDFcdWM3NzggXHViM2M0XHVkMGI5XHVjNzQwIFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDc3NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkdhdGVzIiwiZGVzY3JpcHRpb24iOiI8cD5Gb3IgeW91ciBiaXJ0aGRheSwgeW91IHdlcmUgZ2l2ZW4gYW4gYWlycG9ydC48XC9wPlxyXG5cclxuPHA+VGhlIGFpcnBvcnQgaGFzIEcgZ2F0ZXMsIG51bWJlcmVkIGZyb20gMSB0byBHLjxcL3A+XHJcblxyXG48cD5QIHBsYW5lcyBhcnJpdmUgYXQgdGhlIGFpcnBvcnQsIG9uZSBhZnRlciBhbm90aGVyLiBZb3UgYXJlIHRvIGFzc2lnbiB0aGUgaXRoIHBsYW5lIHRvIHBlcm1hbmVudGx5IGRvY2sgYXQgYW55IGdhdGUgMSwgLiAuIC4gLCBnPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IGc8c3ViPmk8XC9zdWI+ICZsZTsgRyksIGF0IHdoaWNoIG5vIHByZXZpb3VzIHBsYW5lIGhhcyBkb2NrZWQuIEFzIHNvb24gYXMgYSBwbGFuZSBjYW5ub3QgZG9jayBhdCBhbnkgZ2F0ZSwgdGhlIGFpcnBvcnQgaXMgc2h1dCBkb3duIGFuZCBubyBmdXR1cmUgcGxhbmVzIGFyZSBhbGxvd2VkIHRvIGFycml2ZS48XC9wPlxyXG5cclxuPHA+SW4gb3JkZXIgdG8ga2VlcCB0aGUgcGVyc29uIHdobyBnYXZlIHlvdSB0aGUgYWlycG9ydCBoYXBweSwgeW91IHdvdWxkIGxpa2UgdG8gbWF4aW1pemUgdGhlIG51bWJlciBvZiBwbGFuZXMgc3RhcnRpbmcgZnJvbSB0aGUgYmVnaW5uaW5nIHRoYXQgY2FuIGFsbCBkb2NrIGF0IGRpZmZlcmVudCBnYXRlcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIEcgKDEgJmxlOyBHICZsZTsgMTA8c3VwPjU8XC9zdXA+KSwgdGhlIG51bWJlciBvZiBnYXRlcyBhdCB0aGUgYWlycG9ydC48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIFAgKDEgJmxlOyBQICZsZTsgMTA8c3VwPjU8XC9zdXA+KSwgdGhlIG51bWJlciBvZiBwbGFuZXMgd2hpY2ggd2lsbCBsYW5kLjxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBQIGxpbmVzIGNvbnRhaW4gb25lIGludGVnZXIgZzxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBnPHN1Yj5pPFwvc3ViPiAmbGU7IEcpLCBzdWNoIHRoYXQgdGhlIGl0aCBwbGFuZSBtdXN0IGRvY2sgYXQgc29tZSBnYXRlIGZyb20gMSB0byBnPHN1Yj5pPFwvc3ViPiwgaW5jbHVzaXZlLjxcL3A+XHJcblxyXG48cD5Ob3RlIHRoYXQgZm9yIGF0IGxlYXN0IDQwJSBvZiB0aGUgbWFya3MgZm9yIHRoaXMgcXVlc3Rpb24sIFAgJmxlOyAyMDAwIGFuZCBHICZsZTsgMjAwMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG1heGltdW0gbnVtYmVyIG9mIHBsYW5lcyB0aGF0IGNhbiBsYW5kIHN0YXJ0aW5nIGZyb20gdGhlIGJlZ2lubmluZy48XC9wPlxyXG4iLCJoaW50IjoiPHA+RXhwbGFuYXRpb24gb2YgT3V0cHV0IGZvciBTYW1wbGUgSW5wdXQgMTxcL3A+XHJcblxyXG48cD5UaGUgZmlyc3QgcGxhbmUgY2FuIGdvIGFueXdoZXJlLCBidXQgaXQgaXMgYmVzdCB0byBub3QgcHV0IGl0IGludG8gR2F0ZSAxLiBOb3RpY2UgdGhhdCBwbGFuZXMgMiBhbmQgMyBib3RoIHdhbnQgdG8gZG9jayBpbnRvIEdhdGUgMSwgc28gcGxhbmUgMyBpcyB1bmFibGUgdG8gZG9jay48XC9wPlxyXG5cclxuPHA+RXhwbGFuYXRpb24gb2YgT3V0cHV0IGZvciBTYW1wbGUgSW5wdXQgMjxcL3A+XHJcblxyXG48cD5UaGUgZmlyc3QgdHdvIHBsYW5lcyB3aWxsIGRvY2sgaW4gZ2F0ZXMgMSBhbmQgMiAoaW4gYW55IG9yZGVyKS4gVGhlIHRoaXJkIHBsYW5lIG11c3QgZG9jayBhdCBHYXRlIDMuIFRodXMsIHRoZSBmb3VydGggcGxhbmUgY2Fubm90IGRvY2sgYW55d2hlcmUsIGFuZCB0aGUgYWlycG9ydCBpcyBjbG9zZWQsIGV2ZW4gdGhvdWdoIHBsYW5lIDUgd291bGQgaGF2ZSBiZWVuIGFibGUgdG8gZG9jay48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Canadian Computing Competition & Olympiad > 2015 > CCC 2015 Senior Division 3번