시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB74542045150227.309%

문제

월드피자 원주 지점에서 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+PFwvcD5cclxuXHJcbjxwPlx1ZDUzY1x1Yzc5MCBcdWJjMThcdWM4ZmRcdWM3NDAgXHVjNjQ0XHVjMTMxXHViNDE4XHViMjk0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM2MjRcdWJlMTBcdWM1ZDAgXHViNGU0XHVjNWI0XHVhYzA0XHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgTlx1YWMxY1x1Yzc1OCBcdWQ1M2NcdWM3OTBcdWFjMDAgXHVjNjI0XHViZTEwXHVjNWQwIFx1YmFhOFx1YjQ1MCBcdWI0ZTRcdWM1YjRcdWFjMDBcdWFjZTAgXHViMDk4XHViYTc0LCBcdWI5ZTggXHVjNzA0XHVjNzU4IFx1ZDUzY1x1Yzc5MFx1YWMwMCBcdWM1YmNcdWI5YzhcdWIwOTggXHVhZTRhXHVjNzc0IFx1YjRlNFx1YzViNFx1YWMwMCBcdWM3ODhcdWIyOTRcdWM5YzBcdWFjMDAgXHVhZDgxXHVhZTA4XHVkNTU4XHViMmU0LiBcdWM3NzRcdWI5N2MgXHVjNTRjXHVjNTQ0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzYyNFx1YmUxMFx1Yzc1OCBcdWFlNGFcdWM3NzQgRFx1YzY0MCBcdWQ1M2NcdWM3OTAgXHViYzE4XHVjOGZkXHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBELCBOICZsZTsgMzAwLDAwMCkgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM2MjRcdWJlMTBcdWM3NTggXHVjZDVjXHVjMGMxXHViMmU4XHViZDgwXHVkMTMwIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YzVlYyBcdWFlNGFcdWM3NzRcdWM1ZDAgXHViNTMwXHViOTc4IFx1YzYyNFx1YmUxMFx1Yzc1OCBcdWM5YzBcdWI5ODRcdWM3NzQgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ1M2NcdWM3OTAgXHViYzE4XHVjOGZkXHVjNzc0IFx1YzY0NFx1YzEzMVx1YjQxOFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMsIFx1YWRmOCBcdWFjMDFcdWFjMDFcdWM3NTggXHVjOWMwXHViOTg0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNjI0XHViZTEwXHVjNzU4IFx1YzljMFx1Yjk4NFx1Yzc3NFx1YjA5OCBcdWQ1M2NcdWM3OTAgXHViYzE4XHVjOGZkXHVjNzU4IFx1YzljMFx1Yjk4NFx1Yzc0MCAxMFx1YzViNSBcdWM3NzRcdWQ1NThcdWM3NTggXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAsIFx1YjljOFx1YzljMFx1YjljOSBcdWQ1M2NcdWM3OTAgXHViYzE4XHVjOGZkXHVjNzU4Jm5ic3A7XHVjNzA0XHVjZTU4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNjI0XHViZTEwXHVjNzU4IFx1Y2Q1Y1x1YzBjMVx1YjJlOFx1Yzc3NCAxXHVjNzc0XHVhY2UwLCBcdWNkNWNcdWQ1NThcdWIyZTggXHVhYzAwXHVjN2E1IFx1YWU0YVx1Yzc0MCBcdWFjZjNcdWM3NzQgRFx1Yzc3NCBcdWI0MWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWQ1M2NcdWM3OTBcdWFjMDAgXHViYWE4XHViNDUwIFx1YzYyNFx1YmUxMFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWFjMDBcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0XHViYTc0LCAwXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTAwNlwvcGl6Mi5QTkdcIiBzdHlsZT1cImhlaWdodDoxNTZweDsgd2lkdGg6MjY2cHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjE3NTYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaGUgRGlza3MiLCJkZXNjcmlwdGlvbiI6IjxwPkZvciBoaXMgYmlydGhkYXkgcHJlc2VudCBsaXR0bGUgSm9obm55IGhhcyByZWNlaXZlZCBmcm9tIGhpcyBwYXJlbnRzIGEgbmV3IHBsYXl0aGluZyB3aGljaCBjb25zaXN0cyBvZiBhIHR1YmUgYW5kIGEgc2V0IG9mIGRpc2tzLiBUaGUgYWZvcmVtZW50aW9uZWQgdHViZSBpcyBvZiB1bnVzdWFsIHNoYXBlLiBOYW1lbHksIGl0IGlzIG1hZGUgb2YgYSBjZXJ0YWluIG51bWJlciBvZiBjeWxpbmRlcnMgKG9mIGVxdWFsIGhlaWdodCkgd2l0aCBhcGVydHVyZXMgb2YgZGlmZmVyZW50IGRpYW1ldGVycyBjYXJ2ZWQgY29heGlhbGx5IHRocm91Z2ggdGhlbS4gVGhlIHR1YmUgaXMgY2xvc2VkIGF0IHRoZSBib3R0b20sIG9wZW4gYXQgdGhlIHRvcC4gQW4gZXhlbXBsYXJ5IHR1YmUgY29uc2lzdGluZyBvZiBjeWxpbmRlcnMgd2hvc2UgYXBlcnR1cmVzIGhhdmUgdGhlIGRpYW1ldGVyczogNWNtLCA2Y20sIDRjbSwgM2NtLCA2Y20sIDJjbSBhbmQgM2NtIGlzIHByZXNlbnRlZCBpbiB0aGUgaW1hZ2UgYmVsb3cuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wva3JhMS5wbmdcIiBzdHlsZT1cImhlaWdodDoyMDZweDsgd2lkdGg6MzUwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+VGhlIGRpc2tzIGluIEpvaG5ueSYjMzk7cyBwbGF5dGhpbmcgYXJlIGN5bGluZGVycyBvZiBkaWZmZXJlbnQgZGlhbWV0ZXJzIGFuZCBoZWlnaHQgZXF1YWwgdG8gdGhvc2UgZm9ybWluZyB0aGUgdHViZS48XC9wPlxyXG5cclxuPHA+Sm9obm55IGhhcyBpbnZlbnRlZCBhIGZvbGxvd2luZyBnYW1lOiBoYXZpbmcgYSBjZXJ0YWluIHNldCBvZiBkaXNrcyBhdCBoaXMgZGlzcG9zYWwsIGhlIHNlZWtzIHRvIGZpbmQgd2hhdCBkZXB0aCB0aGUgbGFzdCBvZiB0aGVtIHdvdWxkIHN0b3AgYXQsIGFzc3VtaW5nIHRoYXQgdGhleSBhcmUgYmVpbmcgdGhyb3duIGludG8gdGhlIGNlbnRyZSBvZiB0aGUgdHViZS4gSWYsIGZvciBpbnN0YW5jZSwgd2Ugd2VyZSB0byB0aHJvdyBkaXNrcyBvZiBjb25zZWN1dGl2ZSBkaWFtZXRlcnM6IDNjbSwgMmNtIGFuZCA1Y20sIHdlIHdvdWxkIG9idGFpbiB0aGUgZm9sbG93aW5nIHNpdHVhdGlvbjo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9rcmEyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIwNnB4OyB3aWR0aDozNTBweFwiIFwvPjxcL3A+XHJcblxyXG48cD5BcyB5b3UgY2FuIHNlZSwgdXBvbiBiZWluZyB0aHJvd24gaW4sIGV2ZXJ5IGRpc2sgZmFsbHMgdW50aWwgaXQgZ2V0cyBzdHVjayAod2hpY2ggbWVhbnMgdGhhdCBpdCBsaWVzIGF0b3AgYSBjeWxpbmRlciwgYXBlcnR1cmUgb2Ygd2hpY2ggaGFzIGEgZGlhbWV0ZXIgc21hbGxlciB0aGFuIHRoZSBkaWFtZXRlciBvZiB0aGUgZGlzaykgb3IgaXQgaXMgc3RvcHBlZCBieSBhbiBvYnN0YWNsZTogdGhlIGJvdHRvbSBvZiB0aGUgdHViZSBvciBhbm90aGVyIGRpc2ssIHdoaWNoIGhhcyBhbHJlYWR5IHN0b3BwZWQuPFwvcD5cclxuXHJcbjxwPlRoZSBnYW1lIGJlaW5nIGRpZmZpY3VsdCwgSm9obm55IGNvbnN0YW50bHkgYXNrcyBoaXMgcGFyZW50cyBmb3IgaGVscC4gQXMgSm9obm55JiMzOTtzIHBhcmVudHMgZG8gbm90IGxpa2Ugc3VjaCBpbnRlbGxlY3R1YWwgZ2FtZXMsIHRoZXkgaGF2ZSBhc2tlZCB5b3UgLSBhbiBhY3F1YWludGFuY2Ugb2YgdGhlaXJzIGFuZCBhIHByb2dyYW1tZXIgLSB0byB3cml0ZSBhIHByb2dyYW1tZSB3aGljaCB3aWxsIHByb3ZpZGUgdGhlbSB3aXRoIGFuc3dlcnMgdG8gSm9obm55JiMzOTtzIHF1ZXN0aW9ucy48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtbWUgd2hpY2g6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+cmVhZHMgdGhlIGRlc2NyaXB0aW9uIG9mIHRoZSB0dWJlIGFuZCB0aGUgZGlza3Mgd2hpY2ggSm9obm55IHdpbGwgdGhyb3cgaW50byBpdCBmcm9tIHRoZSBzdGFuZGFyZCBpbnB1dCw8XC9saT5cclxuXHQ8bGk+Y29tcHV0ZXMgdGhlIGRlcHRoIHdoaWNoIHRoZSBsYXN0IGRpc2sgdGhyb3duIGJ5IEpvaG5ueSBzdG9wcyBhdCw8XC9saT5cclxuXHQ8bGk+d3JpdGVzIHRoZSBvdXRjb21lIHRvIHRoZSBzdGFuZGFyZCBvdXRwdXQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBzdGFuZGFyZCBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnMgbiBhbmQgbSAoMSAmbGU7IG4sbSAmbGU7IDMwMCAwMDApIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZSBhbmQgZGVub3RpbmcgdGhlIGhlaWdodCBvZiBKb2hubnkmIzM5O3MgdHViZSAodGhlIG51bWJlciBvZiBjeWxpbmRlcnMgaXQgY29tcHJpc2VzKSBhbmQgdGhlIG51bWJlciBvZiBkaXNrcyBKb2hubnkgaW50ZW5kcyB0byB0aHJvdyBpbnRvIGl0LCByZXNwZWN0aXZlbHkuIFRoZSBzZWNvbmQgbGluZSBvZiB0aGUgc3RhbmRhcmQgaW5wdXQgY29udGFpbnMgbiBpbnRlZ2VycyByPHN1Yj4xPFwvc3ViPixyPHN1Yj4yPFwvc3ViPiwuLi4scjxzdWI+bjxcL3N1Yj4gKDEgJmxlOyByPHN1Yj5pPFwvc3ViPiAmbGU7IDEgMDAwIDAwMCAwMDAgZm9yIDEgJmxlOyBpICZsZTsgbikgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMgYW5kIGRlbm90aW5nIHRoZSBkaWFtZXRlcnMgb2YgdGhlIGFwZXJ0dXJlcyBjYXJ2ZWQgdGhyb3VnaCB0aGUgY29uc2VjdXRpdmUgY3lsaW5kZXJzIChpbiB0b3AtZG93biBvcmRlciksIHdoaWNoIHRoZSB0dWJlIGNvbnNpc3RzIG9mLiBUaGUgdGhpcmQgbGluZSBjb250YWlucyBtIGludGVnZXJzIGs8c3ViPjE8XC9zdWI+LGs8c3ViPjI8XC9zdWI+LC4uLixrPHN1Yj5tPFwvc3ViPiAoMSAmbGU7IGs8c3ViPmo8XC9zdWI+ICZsZTsgMSAwMDAgMDAwIDAwMCBmb3IgMSAmbGU7IGogJmxlOyBtKSBzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlcyBhbmQgZGVub3RpbmcgdGhlIGRpYW1ldGVycyBvZiBjb25zZWN1dGl2ZSBkaXNrcyB3aGljaCBKb2hubnkgaW50ZW5kcyB0byB0aHJvdyBpbnRvIHRoZSB0dWJlLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiB0aGUgc3RhbmRhcmQgb3V0cHV0IHNob3VsZCBjb250YWluIGEgc2luZ2xlIGludGVnZXIgZGVub3RpbmcgdGhlIGRlcHRoIHdoaWNoIHRoZSBsYXN0IGRpc2sgc3RvcHMgYXQuIFNob3VsZCB0aGUgZGlzayBub3QgZmFsbCBpbnRvIHRoZSB0dWJlIGF0IGFsbCwgdGhlIGFuc3dlciBzaG91bGQgYmUgMC48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

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