시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 788 224 176 28.758%

문제

월드피자 원주 지점에서 N개의 피자 반죽을 오븐에 넣고 구우려고 한다. 그런데, 월드피자에서 만드는 피자 반죽은 지름이 제각각이다. 그런가하면, 월드피자에서 사용하는 오븐의 모양도 몹시 오묘하다. 이 오븐은 깊은 관처럼 생겼는데, 관의 지름이 깊이에 따라 들쭉날쭉하게 변한다. 아래는 오븐의 단면 예시이다.

피자 반죽은 완성되는 순서대로 오븐에 들어간다. 이렇게 N개의 피자가 오븐에 모두 들어가고 나면, 맨 위의 피자가 얼마나 깊이 들어가 있는지가 궁금하다. 이를 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 오븐의 깊이 D와 피자 반죽의 개수 N이 공백을 사이에 두고 주어진다. (1<=D, N<=300,000) 둘째 줄에는 오븐의 최상단부터 시작하여 깊이에 따른 오븐의 지름이 차례대로 주어진다. 셋째 줄에는 피자 반죽이 완성되는 순서대로, 그 각각의 지름이 주어진다. 오븐의 지름이나 피자 반죽의 지름은 10억 이하의 자연수이다.

출력

첫째 줄에, 마지막 피자 반죽의 위치를 출력한다. 오븐의 최상단이 1이고, 최하단 가장 깊은 곳이 D이 된다. 만약 피자가 모두 오븐에 들어가지 않는다면, 0을 출력한다.

예제 입력 1

7 3
5 6 4 3 6 2 3
3 2 5

예제 출력 1

2

힌트

W3sicHJvYmxlbV9pZCI6IjE3NTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1M2NcdWM3OTAgXHVhZDdkXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM2ZDRcdWI0ZGNcdWQ1M2NcdWM3OTAgXHVjNmQwXHVjOGZjIFx1YzljMFx1YzgxMFx1YzVkMFx1YzExYyBOXHVhYzFjXHVjNzU4IFx1ZDUzY1x1Yzc5MCBcdWJjMThcdWM4ZmRcdWM3NDQgXHVjNjI0XHViZTEwXHVjNWQwIFx1YjEyM1x1YWNlMCBcdWFkNmNcdWM2YjBcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI3ZjBcdWIzNzAsIFx1YzZkNFx1YjRkY1x1ZDUzY1x1Yzc5MFx1YzVkMFx1YzExYyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVkNTNjXHVjNzkwIFx1YmMxOFx1YzhmZFx1Yzc0MCBcdWM5YzBcdWI5ODRcdWM3NzQgXHVjODFjXHVhYzAxXHVhYzAxXHVjNzc0XHViMmU0LiBcdWFkZjhcdWI3ZjBcdWFjMDBcdWQ1NThcdWJhNzQsIFx1YzZkNFx1YjRkY1x1ZDUzY1x1Yzc5MFx1YzVkMFx1YzExYyBcdWMwYWNcdWM2YTlcdWQ1NThcdWIyOTQgXHVjNjI0XHViZTEwXHVjNzU4IFx1YmFhOFx1YzU5MVx1YjNjNCBcdWJhYjlcdWMyZGMgXHVjNjI0XHViYjE4XHVkNTU4XHViMmU0LiBcdWM3NzQgXHVjNjI0XHViZTEwXHVjNzQwIFx1YWU0YVx1Yzc0MCBcdWFkMDBcdWNjOThcdWI3ZmMgXHVjMGRkXHVhY2JjXHViMjk0XHViMzcwLCBcdWFkMDBcdWM3NTggXHVjOWMwXHViOTg0XHVjNzc0IFx1YWU0YVx1Yzc3NFx1YzVkMCBcdWI1MzBcdWI3N2MgXHViNGU0XHVjYjQ5XHViMGEwXHVjYjQ5XHVkNTU4XHVhYzhjIFx1YmNjMFx1ZDU1Y1x1YjJlNC4gXHVjNTQ0XHViNzk4XHViMjk0IFx1YzYyNFx1YmUxMFx1Yzc1OCBcdWIyZThcdWJhNzQgXHVjNjA4XHVjMmRjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC91cGxvYWRcLzIwMTAwNlwvcGl6ejEuUE5HXCIgc3R5bGU9XCJoZWlnaHQ6MTU3cHg7IHdpZHRoOjI2OHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1ZDUzY1x1Yzc5MCBcdWJjMThcdWM4ZmRcdWM3NDAgXHVjNjQ0XHVjMTMxXHViNDE4XHViMjk0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM2MjRcdWJlMTBcdWM1ZDAgXHViNGU0XHVjNWI0XHVhYzA0XHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgTlx1YWMxY1x1Yzc1OCBcdWQ1M2NcdWM3OTBcdWFjMDAgXHVjNjI0XHViZTEwXHVjNWQwIFx1YmFhOFx1YjQ1MCBcdWI0ZTRcdWM1YjRcdWFjMDBcdWFjZTAgXHViMDk4XHViYTc0LCBcdWI5ZTggXHVjNzA0XHVjNzU4IFx1ZDUzY1x1Yzc5MFx1YWMwMCBcdWM1YmNcdWI5YzhcdWIwOTggXHVhZTRhXHVjNzc0IFx1YjRlNFx1YzViNFx1YWMwMCBcdWM3ODhcdWIyOTRcdWM5YzBcdWFjMDAgXHVhZDgxXHVhZTA4XHVkNTU4XHViMmU0LiBcdWM3NzRcdWI5N2MgXHVjNTRjXHVjNTQ0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzYyNFx1YmUxMFx1Yzc1OCBcdWFlNGFcdWM3NzQgRFx1YzY0MCBcdWQ1M2NcdWM3OTAgXHViYzE4XHVjOGZkXHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEmbHQ7PUQsIE4mbHQ7PTMwMCwwMDApIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNjI0XHViZTEwXHVjNzU4IFx1Y2Q1Y1x1YzBjMVx1YjJlOFx1YmQ4MFx1ZDEzMCBcdWMyZGNcdWM3OTFcdWQ1NThcdWM1ZWMgXHVhZTRhXHVjNzc0XHVjNWQwIFx1YjUzMFx1Yjk3OCBcdWM2MjRcdWJlMTBcdWM3NTggXHVjOWMwXHViOTg0XHVjNzc0IFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNTNjXHVjNzkwIFx1YmMxOFx1YzhmZFx1Yzc3NCBcdWM2NDRcdWMxMzFcdWI0MThcdWIyOTQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjLCBcdWFkZjggXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzljMFx1Yjk4NFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzYyNFx1YmUxMFx1Yzc1OCBcdWM5YzBcdWI5ODRcdWM3NzRcdWIwOTggXHVkNTNjXHVjNzkwIFx1YmMxOFx1YzhmZFx1Yzc1OCBcdWM5YzBcdWI5ODRcdWM3NDAgMTBcdWM1YjUgXHVjNzc0XHVkNTU4XHVjNzU4IFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwLCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVkNTNjXHVjNzkwIFx1YmMxOFx1YzhmZFx1Yzc1OCZuYnNwO1x1YzcwNFx1Y2U1OFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzYyNFx1YmUxMFx1Yzc1OCBcdWNkNWNcdWMwYzFcdWIyZThcdWM3NzQgMVx1Yzc3NFx1YWNlMCwgXHVjZDVjXHVkNTU4XHViMmU4IFx1YWMwMFx1YzdhNSBcdWFlNGFcdWM3NDAgXHVhY2YzXHVjNzc0IERcdWM3NzQgXHViNDFjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVkNTNjXHVjNzkwXHVhYzAwIFx1YmFhOFx1YjQ1MCBcdWM2MjRcdWJlMTBcdWM1ZDAgXHViNGU0XHVjNWI0XHVhYzAwXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNFx1YmE3NCwgMFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDZcL3BpejIuUE5HXCIgc3R5bGU9XCJoZWlnaHQ6MTU2cHg7IHdpZHRoOjI2NnB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNzU2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIERpc2tzIiwiZGVzY3JpcHRpb24iOiI8cD5Gb3IgaGlzIGJpcnRoZGF5IHByZXNlbnQgbGl0dGxlIEpvaG5ueSBoYXMgcmVjZWl2ZWQgZnJvbSBoaXMgcGFyZW50cyBhIG5ldyBwbGF5dGhpbmcgd2hpY2ggY29uc2lzdHMgb2YgYSB0dWJlIGFuZCBhIHNldCBvZiBkaXNrcy4gVGhlIGFmb3JlbWVudGlvbmVkIHR1YmUgaXMgb2YgdW51c3VhbCBzaGFwZS4gTmFtZWx5LCBpdCBpcyBtYWRlIG9mIGEgY2VydGFpbiBudW1iZXIgb2YgY3lsaW5kZXJzIChvZiBlcXVhbCBoZWlnaHQpIHdpdGggYXBlcnR1cmVzIG9mIGRpZmZlcmVudCBkaWFtZXRlcnMgY2FydmVkIGNvYXhpYWxseSB0aHJvdWdoIHRoZW0uIFRoZSB0dWJlIGlzIGNsb3NlZCBhdCB0aGUgYm90dG9tLCBvcGVuIGF0IHRoZSB0b3AuIEFuIGV4ZW1wbGFyeSB0dWJlIGNvbnNpc3Rpbmcgb2YgY3lsaW5kZXJzIHdob3NlIGFwZXJ0dXJlcyBoYXZlIHRoZSBkaWFtZXRlcnM6IDVjbSwgNmNtLCA0Y20sIDNjbSwgNmNtLCAyY20gYW5kIDNjbSBpcyBwcmVzZW50ZWQgaW4gdGhlIGltYWdlIGJlbG93LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2tyYTEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjA2cHg7IHdpZHRoOjM1MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRoZSBkaXNrcyBpbiBKb2hubnkmIzM5O3MgcGxheXRoaW5nIGFyZSBjeWxpbmRlcnMgb2YgZGlmZmVyZW50IGRpYW1ldGVycyBhbmQgaGVpZ2h0IGVxdWFsIHRvIHRob3NlIGZvcm1pbmcgdGhlIHR1YmUuPFwvcD5cclxuXHJcbjxwPkpvaG5ueSBoYXMgaW52ZW50ZWQgYSBmb2xsb3dpbmcgZ2FtZTogaGF2aW5nIGEgY2VydGFpbiBzZXQgb2YgZGlza3MgYXQgaGlzIGRpc3Bvc2FsLCBoZSBzZWVrcyB0byBmaW5kIHdoYXQgZGVwdGggdGhlIGxhc3Qgb2YgdGhlbSB3b3VsZCBzdG9wIGF0LCBhc3N1bWluZyB0aGF0IHRoZXkgYXJlIGJlaW5nIHRocm93biBpbnRvIHRoZSBjZW50cmUgb2YgdGhlIHR1YmUuIElmLCBmb3IgaW5zdGFuY2UsIHdlIHdlcmUgdG8gdGhyb3cgZGlza3Mgb2YgY29uc2VjdXRpdmUgZGlhbWV0ZXJzOiAzY20sIDJjbSBhbmQgNWNtLCB3ZSB3b3VsZCBvYnRhaW4gdGhlIGZvbGxvd2luZyBzaXR1YXRpb246PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wva3JhMi5wbmdcIiBzdHlsZT1cImhlaWdodDoyMDZweDsgd2lkdGg6MzUwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+QXMgeW91IGNhbiBzZWUsIHVwb24gYmVpbmcgdGhyb3duIGluLCBldmVyeSBkaXNrIGZhbGxzIHVudGlsIGl0IGdldHMgc3R1Y2sgKHdoaWNoIG1lYW5zIHRoYXQgaXQgbGllcyBhdG9wIGEgY3lsaW5kZXIsIGFwZXJ0dXJlIG9mIHdoaWNoIGhhcyBhIGRpYW1ldGVyIHNtYWxsZXIgdGhhbiB0aGUgZGlhbWV0ZXIgb2YgdGhlIGRpc2spIG9yIGl0IGlzIHN0b3BwZWQgYnkgYW4gb2JzdGFjbGU6IHRoZSBib3R0b20gb2YgdGhlIHR1YmUgb3IgYW5vdGhlciBkaXNrLCB3aGljaCBoYXMgYWxyZWFkeSBzdG9wcGVkLjxcL3A+XHJcblxyXG48cD5UaGUgZ2FtZSBiZWluZyBkaWZmaWN1bHQsIEpvaG5ueSBjb25zdGFudGx5IGFza3MgaGlzIHBhcmVudHMgZm9yIGhlbHAuIEFzIEpvaG5ueSYjMzk7cyBwYXJlbnRzIGRvIG5vdCBsaWtlIHN1Y2ggaW50ZWxsZWN0dWFsIGdhbWVzLCB0aGV5IGhhdmUgYXNrZWQgeW91IC0gYW4gYWNxdWFpbnRhbmNlIG9mIHRoZWlycyBhbmQgYSBwcm9ncmFtbWVyIC0gdG8gd3JpdGUgYSBwcm9ncmFtbWUgd2hpY2ggd2lsbCBwcm92aWRlIHRoZW0gd2l0aCBhbnN3ZXJzIHRvIEpvaG5ueSYjMzk7cyBxdWVzdGlvbnMuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbW1lIHdoaWNoOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnJlYWRzIHRoZSBkZXNjcmlwdGlvbiBvZiB0aGUgdHViZSBhbmQgdGhlIGRpc2tzIHdoaWNoIEpvaG5ueSB3aWxsIHRocm93IGludG8gaXQgZnJvbSB0aGUgc3RhbmRhcmQgaW5wdXQsPFwvbGk+XHJcblx0PGxpPmNvbXB1dGVzIHRoZSBkZXB0aCB3aGljaCB0aGUgbGFzdCBkaXNrIHRocm93biBieSBKb2hubnkgc3RvcHMgYXQsPFwvbGk+XHJcblx0PGxpPndyaXRlcyB0aGUgb3V0Y29tZSB0byB0aGUgc3RhbmRhcmQgb3V0cHV0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgc3RhbmRhcmQgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIG4gYW5kIG0gKDEgJmxlOyBuLG0gJmxlOyAzMDAgMDAwKSBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UgYW5kIGRlbm90aW5nIHRoZSBoZWlnaHQgb2YgSm9obm55JiMzOTtzIHR1YmUgKHRoZSBudW1iZXIgb2YgY3lsaW5kZXJzIGl0IGNvbXByaXNlcykgYW5kIHRoZSBudW1iZXIgb2YgZGlza3MgSm9obm55IGludGVuZHMgdG8gdGhyb3cgaW50byBpdCwgcmVzcGVjdGl2ZWx5LiBUaGUgc2Vjb25kIGxpbmUgb2YgdGhlIHN0YW5kYXJkIGlucHV0IGNvbnRhaW5zIG4gaW50ZWdlcnMgcjxzdWI+MTxcL3N1Yj4scjxzdWI+MjxcL3N1Yj4sLi4uLHI8c3ViPm48XC9zdWI+ICgxICZsZTsgcjxzdWI+aTxcL3N1Yj4gJmxlOyAxIDAwMCAwMDAgMDAwIGZvciAxICZsZTsgaSAmbGU7IG4pIHNlcGFyYXRlZCBieSBzaW5nbGUgc3BhY2VzIGFuZCBkZW5vdGluZyB0aGUgZGlhbWV0ZXJzIG9mIHRoZSBhcGVydHVyZXMgY2FydmVkIHRocm91Z2ggdGhlIGNvbnNlY3V0aXZlIGN5bGluZGVycyAoaW4gdG9wLWRvd24gb3JkZXIpLCB3aGljaCB0aGUgdHViZSBjb25zaXN0cyBvZi4gVGhlIHRoaXJkIGxpbmUgY29udGFpbnMgbSBpbnRlZ2VycyBrPHN1Yj4xPFwvc3ViPixrPHN1Yj4yPFwvc3ViPiwuLi4sazxzdWI+bTxcL3N1Yj4gKDEgJmxlOyBrPHN1Yj5qPFwvc3ViPiAmbGU7IDEgMDAwIDAwMCAwMDAgZm9yIDEgJmxlOyBqICZsZTsgbSkgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMgYW5kIGRlbm90aW5nIHRoZSBkaWFtZXRlcnMgb2YgY29uc2VjdXRpdmUgZGlza3Mgd2hpY2ggSm9obm55IGludGVuZHMgdG8gdGhyb3cgaW50byB0aGUgdHViZS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2YgdGhlIHN0YW5kYXJkIG91dHB1dCBzaG91bGQgY29udGFpbiBhIHNpbmdsZSBpbnRlZ2VyIGRlbm90aW5nIHRoZSBkZXB0aCB3aGljaCB0aGUgbGFzdCBkaXNrIHN0b3BzIGF0LiBTaG91bGQgdGhlIGRpc2sgbm90IGZhbGwgaW50byB0aGUgdHViZSBhdCBhbGwsIHRoZSBhbnN3ZXIgc2hvdWxkIGJlIDAuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Polish Olympiad in Informatics > POI 2005/2006 > Stage 1 1번