시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 80 27 25 40.323%

문제

준규는 천재다. 하지만 준규의 발명품은 용도가 좀 애매하다. 준규의 최신 발명품인 'Shuffle-o-matic 3175' 역시 좀 애매하다. Shuffle-o-matic은 아주 특별한 방식으로 사용된다. 먼저 1부터 N까지의 수가 적힌 N개의 카드를 이 기계에 위에 놓는다. 그 다음 셔플 수열을 입력하고 작동 버튼을 누르면, 기계가 자동으로 카드의 숫자를 읽어서 그 수열을 테입에 출력한다. 그 후 기계는 셔플 수열대로 카드를 섞은 후 카드의 숫자를 읽어 테입의 다음 줄에 출력한다. 같은 방식으로 한 번 더 셔플 수열대로 카드를 섞고 다시 카드의 수를 테입의 다음 줄에 출력한다. 테입이 다 떨어질 때 까지 이 과정을 반복한다.

준규는 자신의 발명품을 테스트 해 본 후 좀 쉬기로 했다. 그러다 출력 테입의 한 조각을 발견했다. 그리고 모든 줄은 앞에서부터 C개의 수와 뒤에서부터 D개의 수가 지워져 있었다.

준규는 섞기 전의 수열을 1번째 수열이라고 했을때, A번째 수열에서 B번째 수열까지의 수열 중 맨 처음 섞기 전의 순서와 적힌 부분이 모두 일치하는 수열이 몇 개인지 궁금해졌다. 이를 계산하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에는 정수 N, A, B, C, D (1 ≤ N ≤ 500 000, A ≤ B ≤ 10^12, 0 ≤ C, D ≤ N, C + D < N)가 차례로 주어진다.

둘째 줄에는 셔플 수열이 주어진다. 이 수열에는 1부터 N까지의 수가 한 번씩 등장한다. 만약 수열의 k번째 숫자가 x라면, 이는 카드를 섞을 때 k번째 수를 x번째로 옮긴다는 의미이다.

출력

준규가 찾는 수열의 개수를 출력한다.

예제 입력 1

4 1 5 0 1
1 3 4 2

예제 출력 1

2

힌트

맨 처음 카드의 순서가 1234였다고 하면 이 종이에는

  • 1234
  • 1423
  • 1342
  • 1234
  • 1423

가 적혀 있고, 이 중 앞에서부터 3개의 수가 123인 줄은 총 두 개이므로 답은 2이다.

W3sicHJvYmxlbV9pZCI6IjI5MjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNjOWNcdWM3YWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzkwMFx1YWRkY1x1YjI5NCBcdWNjOWNcdWM3YWNcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWM5MDBcdWFkZGNcdWM3NTggXHViYzFjXHViYTg1XHVkNDg4XHVjNzQwIFx1YzZhOVx1YjNjNFx1YWMwMCBcdWM4ODAgXHVjNTYwXHViOWU0XHVkNTU4XHViMmU0LiBcdWM5MDBcdWFkZGNcdWM3NTggXHVjZDVjXHVjMmUwIFx1YmMxY1x1YmE4NVx1ZDQ4OFx1Yzc3OCZuYnNwOyYjMzk7U2h1ZmZsZS1vLW1hdGljIDMxNzUmIzM5OyBcdWM1ZWRcdWMyZGMgXHVjODgwIFx1YzU2MFx1YjllNFx1ZDU1OFx1YjJlNC4mbmJzcDtTaHVmZmxlLW8tbWF0aWNcdWM3NDAgXHVjNTQ0XHVjOGZjIFx1ZDJiOVx1YmNjNFx1ZDU1YyBcdWJjMjlcdWMyZGRcdWM3M2NcdWI4NWMgXHVjMGFjXHVjNmE5XHViNDFjXHViMmU0LiBcdWJhM2NcdWM4MDAgMVx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWM4MDFcdWQ3OGMgTlx1YWMxY1x1Yzc1OCBcdWNlNzRcdWI0ZGNcdWI5N2MgXHVjNzc0IFx1YWUzMFx1YWNjNFx1YzVkMCBcdWM3MDRcdWM1ZDAgXHViMTkzXHViMjk0XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIFx1YzE1NFx1ZDUwYyBcdWMyMThcdWM1ZjRcdWM3NDQgXHVjNzg1XHViODI1XHVkNTU4XHVhY2UwIFx1Yzc5MVx1YjNkOSBcdWJjODRcdWQyYmNcdWM3NDQgXHViMjA0XHViOTc0XHViYTc0LCBcdWFlMzBcdWFjYzRcdWFjMDAgXHVjNzkwXHViM2Q5XHVjNzNjXHViODVjIFx1Y2U3NFx1YjRkY1x1Yzc1OCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjNzdkXHVjNWI0XHVjMTFjIFx1YWRmOCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVkMTRjXHVjNzg1XHVjNWQwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhZGY4IFx1ZDZjNCBcdWFlMzBcdWFjYzRcdWIyOTQgXHVjMTU0XHVkNTBjIFx1YzIxOFx1YzVmNFx1YjMwMFx1Yjg1YyBcdWNlNzRcdWI0ZGNcdWI5N2MgXHVjMTFlXHVjNzQwIFx1ZDZjNCBcdWNlNzRcdWI0ZGNcdWM3NTggXHVjMjJiXHVjNzkwXHViOTdjIFx1Yzc3ZFx1YzViNCBcdWQxNGNcdWM3ODVcdWM3NTggXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWMxOVx1Yzc0MCBcdWJjMjlcdWMyZGRcdWM3M2NcdWI4NWMgXHVkNTVjIFx1YmM4OCBcdWIzNTQgXHVjMTU0XHVkNTBjIFx1YzIxOFx1YzVmNFx1YjMwMFx1Yjg1YyBcdWNlNzRcdWI0ZGNcdWI5N2MgXHVjMTFlXHVhY2UwIFx1YjJlNFx1YzJkYyBcdWNlNzRcdWI0ZGNcdWM3NTggXHVjMjE4XHViOTdjIFx1ZDE0Y1x1Yzc4NVx1Yzc1OCBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVkMTRjXHVjNzg1XHVjNzc0IFx1YjJlNCBcdWI1YThcdWM1YjRcdWM5YzggXHViNTRjIFx1YWU0Y1x1YzljMCBcdWM3NzQgXHVhY2ZjXHVjODE1XHVjNzQ0IFx1YmMxOFx1YmNmNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOTAwXHVhZGRjXHViMjk0IFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWJjMWNcdWJhODVcdWQ0ODhcdWM3NDQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1ZDU3NCBcdWJjZjggXHVkNmM0IFx1Yzg4MCBcdWMyNmNcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWFkZjhcdWI3ZWNcdWIyZTQgXHVjZDljXHViODI1IFx1ZDE0Y1x1Yzc4NVx1Yzc1OCBcdWQ1NWMgXHVjODcwXHVhYzAxXHVjNzQ0IFx1YmMxY1x1YWNhY1x1ZDU4OFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YmFhOFx1YjRlMCBcdWM5MDRcdWM3NDAgXHVjNTVlXHVjNWQwXHVjMTFjXHViZDgwXHVkMTMwIENcdWFjMWNcdWM3NTggXHVjMjE4XHVjNjQwIFx1YjRhNFx1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMCBEXHVhYzFjXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWM5YzBcdWM2Y2NcdWM4MzggXHVjNzg4XHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM5MDBcdWFkZGNcdWIyOTQgXHVjMTFlXHVhZTMwIFx1YzgwNFx1Yzc1OCBcdWMyMThcdWM1ZjRcdWM3NDQgMVx1YmM4OFx1YzlmOCBcdWMyMThcdWM1ZjRcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTg4XHVjNzQ0XHViNTRjLCBBXHViYzg4XHVjOWY4IFx1YzIxOFx1YzVmNFx1YzVkMFx1YzExYyBCXHViYzg4XHVjOWY4IFx1YzIxOFx1YzVmNFx1YWU0Y1x1YzljMFx1Yzc1OCBcdWMyMThcdWM1ZjQgXHVjOTExIFx1YjllOCBcdWNjOThcdWM3NGMgXHVjMTFlXHVhZTMwIFx1YzgwNFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWM2NDAgXHVjODAxXHVkNzhjIFx1YmQ4MFx1YmQ4NFx1Yzc3NCBcdWJhYThcdWI0NTAgXHVjNzdjXHVjZTU4XHVkNTU4XHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWJhODcgXHVhYzFjXHVjNzc4XHVjOWMwIFx1YWQ4MVx1YWUwOFx1ZDU3NFx1Yzg0Y1x1YjJlNC4mbmJzcDtcdWM3NzRcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MTVcdWMyMTgmbmJzcDtOLCBBLCBCLCBDLCBEICgxICZsZTsgTiAmbGU7IDUwMCAwMDAsIEEgJmxlOyBCICZsZTsgMTBeMTIsIDAgJmxlOyBDLCBEICZsZTsgTiwgQyArIEQgJmx0OyBOKVx1YWMwMCBcdWNjMjhcdWI4NDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzE1NFx1ZDUwYyBcdWMyMThcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHVjMjE4XHVjNWY0XHVjNWQwXHViMjk0IDFcdWJkODBcdWQxMzAgTlx1YWU0Y1x1YzljMFx1Yzc1OCBcdWMyMThcdWFjMDAgXHVkNTVjIFx1YmM4OFx1YzUyOSBcdWI0ZjFcdWM3YTVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWMyMThcdWM1ZjRcdWM3NTgga1x1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWFjMDAgeFx1Yjc3Y1x1YmE3NCwgXHVjNzc0XHViMjk0IFx1Y2U3NFx1YjRkY1x1Yjk3YyBcdWMxMWVcdWM3NDQgXHViNTRjIGtcdWJjODhcdWM5ZjggXHVjMjE4XHViOTdjIHhcdWJjODhcdWM5ZjhcdWI4NWMgXHVjNjJlXHVhZTM0XHViMmU0XHViMjk0IFx1Yzc1OFx1YmJmOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM5MDBcdWFkZGNcdWFjMDAgXHVjYzNlXHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWI5ZTggXHVjYzk4XHVjNzRjIFx1Y2U3NFx1YjRkY1x1Yzc1OCBcdWMyMWNcdWMxMWNcdWFjMDAgMTIzNFx1YzYwMFx1YjJlNFx1YWNlMCBcdWQ1NThcdWJhNzQgXHVjNzc0IFx1Yzg4NVx1Yzc3NFx1YzVkMFx1YjI5NDxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjEyMzQ8XC9saT5cclxuXHQ8bGk+MTQyMzxcL2xpPlxyXG5cdDxsaT4xMzQyPFwvbGk+XHJcblx0PGxpPjEyMzQ8XC9saT5cclxuXHQ8bGk+MTQyMzxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YWMwMCBcdWM4MDFcdWQ2MDAgXHVjNzg4XHVhY2UwLCBcdWM3NzQgXHVjOTExIFx1YzU1ZVx1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMCAzXHVhYzFjXHVjNzU4IFx1YzIxOFx1YWMwMCAxMjNcdWM3NzggXHVjOTA0XHVjNzQwIFx1Y2QxZCBcdWI0NTAgXHVhYzFjXHVjNzc0XHViYmMwXHViODVjIFx1YjJmNVx1Yzc0MCAyXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjkyNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkdFTklKQUxBQyIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gaXMgYSBnZW5pdXMuIEJ1dCB0aGUgcHVycG9zZSBvZiBoaXMgaW52ZW50aW9ucyBpcyBub3QgYWx3YXlzIG9idmlvdXMuIEhpcyBsYXRlc3QgaW52ZW50aW9uLCB0aGUgU2h1ZmZsZS1vLW1hdGljIDMxNzUsIGlzIG9uZSBvZiB0aG9zZS4gVGhlIFNodWZmbGUtby1tYXRpYyBpcyB1c2VkIGluIGEgdmVyeSBzcGVjaWFsIHdheS4gRmlyc3QgTWlya28gcGxhY2VzIE4gcGFwZXIgY2FyZHMsIHdpdGggbnVtYmVycyAxIHRvIE4gcHJpbnRlZCBvbiB0aGVtLCBvbiB0aGUgU2h1ZmZsZS1vLW1hdGljIHdvcmtpbmcgc3VyZmFjZS4gVGhlbiBoZSBpbnB1dHMgdGhlIHNodWZmbGUgc2VxdWVuY2UgaW4gdGhlIHNwZWNpYWwgaW5wdXQgY29uc29sZSBhbmQgaGl0cyB0aGUgZ28gYnV0dG9uLiBUaGUgbWFjaGluZSB0aGFuIHJlYWRzIHRoZSBwYXBlciBjYXJkcyBhbmQgb3V0cHV0cyB0aGUgcmVhZCBzZXF1ZW5jZSBvZiBudW1iZXJzIG9uIGl0cyBvdXRwdXQgdGFwZS4gSXQgdGhhbiBzaHVmZmxlcyB0aGUgY2FyZHMgYWNjb3JkaW5nIHRvIHRoZSBzaHVmZmxlIHNlcXVlbmNlLiBBZnRlciB0aGF0IGl0IHJlYWRzIHRoZSBuZXdseSBvYnRhaW5kIHNlcXVlbmNlIGFuZCB3cml0ZXMgaXQgb250byBhIG5ldyBsaW5lIG9uIGl0cyBvdXRwdXQgdGFwZS4gVGhlbiBpdCBwcm9jZWRlcyB0byBzaHVmZmxlIHRoZSBjYXJkcyBhZ2FpbiBhY29yZGluZyB0byB0aGUgc2FtZSBzaHVmZmxlIHNlcXVlbmNlLCBzY2FucyBhbmQgd3JpdGVzIHRoZSBvdXRwdXQgdG8gdGhlIHRhcGUuIFRoZSBtYWNoaW5lIGRvZXMgdGhpcyB1bnRpbCBpdCBydW5zIG91dCBvZiB0YXBlLjxcL3A+XHJcblxyXG48cD5BZnRlciBleHBlcmltZW50aW5nIHdpdGggdGhlIG1hY2hpbmUgTWlya28gZGVjaWRlZCB0byByZXN0IGEgYml0IG9uIHRoZSBmbG9vci4gVGhlcmUgaGUgbm90aWNlZCBhIHBpZWNlIG9mIG91dHB1dCB0YXBlLiBUaGUgcGllY2UgaXMgbmVhdGx5IGN1dCBqdXN0IGJlZm9yZSB0aGUgQS10aCBvdXRwdXQgcm93IG5hZCBqdXN0IGFmdGVyIHRoZSBCLXRoIG91dHB1dCByb3cuIEl0IGlzIGFsc28gbWlzc2luZyB0aGUgZmlyc3QgQyBudW1iZXIgYW5kIHRoZSBsYXN0IEQgbnVtYmVycyBpbiBhbGwgcm93cy48XC9wPlxyXG5cclxuPHA+SGUgbm93IHdvbmRlcnMgaG93IG1hbnkgcm93cyBvbiB0aGF0IHBpZWNlIG9mIHBhcGVyIGhhdmUgdGhlIHByb3BlcnR5IHRoYXQgYWxsIG51bWJlcnMgaW4gdGhlIHJvdywgdGhhdCBhcmUgc3RpbGwgb24gdGhlIHBhcGVyLCBhcmUgaW4gdGhlIGV4YWN0IHNhbWUgc3BvdCB0aGV5IHdlcmUgYmVmb3JlIGFsbCB0aGUgc2h1ZmZsaW5nIGJlZ2FuLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgaW50ZWdlcnMgTiwgQSwgQiwgQyBhbmQgRCBpbiB0aGF0IG9yZGVyKDEgJmxlOyBOICZsZTsgNTAwIDAwMCwgQSAmbGU7IEIgJmxlOyAxMF4xMiwgMCAmbGU7IEMsIEQgJmxlOyBOLCBDICsgRCAmbHQ7IE4pLjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgdGhlIHNodWZmbGUgc2VxdWVuY2UuIFRoZSBzZXF1ZW5jZSBpcyBnaXZlbiBhcyBhIHBlcm11dGF0aW9uIG9mIG51bWJlcnMgMSB0byBOLiBJZiB0aGUgay10aCBudW1iZXIgaW4gdGhlIHNodWZmbGUgc2VxdWVuY2UgaXMgeCwgYWZ0ZXIgZWFjaCBzaHVmZmxlIHRoZSBrLXRoIGVsZW1lbnQgaW4gdGhlIHJlc3VsdGluZyBzZXF1ZW5jZSBpcyB0aGUgeC10aCBlbGVtZW50IGluIHRoZSBwcmV2aW91cyBzZXF1ZW5jZS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SW4gdGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2YgaW5wdXQgcHJpbnQgdGhlIG51bWJlciBvZiByb3dzIHRoYXQgaGF2ZSB0aGUgcHJvcGVydHkgTWlya28gaXMgbG9va2luZyBmb3IuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2009/2010 > Contest #1 5번

  • 문제를 번역한 사람: arine
  • 어색한 표현을 찾은 사람: kks227
  • 빠진 조건을 찾은 사람: zych1751