시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 128 MB195534938.583%

문제

준규는 천재다. 하지만 준규의 발명품은 용도가 좀 애매하다. 준규의 최신 발명품인 '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

예제 입력 2

7 3 8 1 2
2 3 1 6 4 7 5

예제 출력 2

0

예제 입력 3

6 2 11 3 0
6 3 5 4 2 1

예제 출력 3

1
W3sicHJvYmxlbV9pZCI6IjI5MjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNjOWNcdWM3YWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzkwMFx1YWRkY1x1YjI5NCBcdWNjOWNcdWM3YWNcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWM5MDBcdWFkZGNcdWM3NTggXHViYzFjXHViYTg1XHVkNDg4XHVjNzQwIFx1YzZhOVx1YjNjNFx1YWMwMCBcdWM4ODAgXHVjNTYwXHViOWU0XHVkNTU4XHViMmU0LiBcdWM5MDBcdWFkZGNcdWM3NTggXHVjZDVjXHVjMmUwIFx1YmMxY1x1YmE4NVx1ZDQ4OFx1Yzc3OCZuYnNwOyYjMzk7U2h1ZmZsZS1vLW1hdGljIDMxNzUmIzM5OyBcdWM1ZWRcdWMyZGMgXHVjODgwIFx1YzU2MFx1YjllNFx1ZDU1OFx1YjJlNC4mbmJzcDtTaHVmZmxlLW8tbWF0aWNcdWM3NDAgXHVjNTQ0XHVjOGZjIFx1ZDJiOVx1YmNjNFx1ZDU1YyBcdWJjMjlcdWMyZGRcdWM3M2NcdWI4NWMgXHVjMGFjXHVjNmE5XHViNDFjXHViMmU0LiBcdWJhM2NcdWM4MDAgMVx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWM4MDFcdWQ3OGMgTlx1YWMxY1x1Yzc1OCBcdWNlNzRcdWI0ZGNcdWI5N2MgXHVjNzc0IFx1YWUzMFx1YWNjNFx1YzVkMCBcdWM3MDRcdWM1ZDAgXHViMTkzXHViMjk0XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIFx1YzE1NFx1ZDUwYyBcdWMyMThcdWM1ZjRcdWM3NDQgXHVjNzg1XHViODI1XHVkNTU4XHVhY2UwIFx1Yzc5MVx1YjNkOSBcdWJjODRcdWQyYmNcdWM3NDQgXHViMjA0XHViOTc0XHViYTc0LCBcdWFlMzBcdWFjYzRcdWFjMDAgXHVjNzkwXHViM2Q5XHVjNzNjXHViODVjIFx1Y2U3NFx1YjRkY1x1Yzc1OCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjNzdkXHVjNWI0XHVjMTFjIFx1YWRmOCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVkMTRjXHVjNzg1XHVjNWQwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhZGY4IFx1ZDZjNCBcdWFlMzBcdWFjYzRcdWIyOTQgXHVjMTU0XHVkNTBjIFx1YzIxOFx1YzVmNFx1YjMwMFx1Yjg1YyBcdWNlNzRcdWI0ZGNcdWI5N2MgXHVjMTFlXHVjNzQwIFx1ZDZjNCBcdWNlNzRcdWI0ZGNcdWM3NTggXHVjMjJiXHVjNzkwXHViOTdjIFx1Yzc3ZFx1YzViNCBcdWQxNGNcdWM3ODVcdWM3NTggXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWMxOVx1Yzc0MCBcdWJjMjlcdWMyZGRcdWM3M2NcdWI4NWMgXHVkNTVjIFx1YmM4OCBcdWIzNTQgXHVjMTU0XHVkNTBjIFx1YzIxOFx1YzVmNFx1YjMwMFx1Yjg1YyBcdWNlNzRcdWI0ZGNcdWI5N2MgXHVjMTFlXHVhY2UwIFx1YjJlNFx1YzJkYyBcdWNlNzRcdWI0ZGNcdWM3NTggXHVjMjE4XHViOTdjIFx1ZDE0Y1x1Yzc4NVx1Yzc1OCBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVkMTRjXHVjNzg1XHVjNzc0IFx1YjJlNCBcdWI1YThcdWM1YjRcdWM5YzggXHViNTRjIFx1YWU0Y1x1YzljMCBcdWM3NzQgXHVhY2ZjXHVjODE1XHVjNzQ0IFx1YmMxOFx1YmNmNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOTAwXHVhZGRjXHViMjk0IFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWJjMWNcdWJhODVcdWQ0ODhcdWM3NDQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1ZDU3NCBcdWJjZjggXHVkNmM0IFx1Yzg4MCBcdWMyNmNcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWFkZjhcdWI3ZWNcdWIyZTQgXHVjZDljXHViODI1IFx1ZDE0Y1x1Yzc4NVx1Yzc1OCBcdWQ1NWMgXHVjODcwXHVhYzAxXHVjNzQ0IFx1YmMxY1x1YWNhY1x1ZDU4OFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YmFhOFx1YjRlMCBcdWM5MDRcdWM3NDAgXHVjNTVlXHVjNWQwXHVjMTFjXHViZDgwXHVkMTMwIENcdWFjMWNcdWM3NTggXHVjMjE4XHVjNjQwIFx1YjRhNFx1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMCBEXHVhYzFjXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWM5YzBcdWM2Y2NcdWM4MzggXHVjNzg4XHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM5MDBcdWFkZGNcdWIyOTQgXHVjMTFlXHVhZTMwIFx1YzgwNFx1Yzc1OCBcdWMyMThcdWM1ZjRcdWM3NDQgMVx1YmM4OFx1YzlmOCBcdWMyMThcdWM1ZjRcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTg4XHVjNzQ0XHViNTRjLCBBXHViYzg4XHVjOWY4IFx1YzIxOFx1YzVmNFx1YzVkMFx1YzExYyBCXHViYzg4XHVjOWY4IFx1YzIxOFx1YzVmNFx1YWU0Y1x1YzljMFx1Yzc1OCBcdWMyMThcdWM1ZjQgXHVjOTExIFx1YjllOCBcdWNjOThcdWM3NGMgXHVjMTFlXHVhZTMwIFx1YzgwNFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWM2NDAgXHVjODAxXHVkNzhjIFx1YmQ4MFx1YmQ4NFx1Yzc3NCBcdWJhYThcdWI0NTAgXHVjNzdjXHVjZTU4XHVkNTU4XHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWJhODcgXHVhYzFjXHVjNzc4XHVjOWMwIFx1YWQ4MVx1YWUwOFx1ZDU3NFx1Yzg0Y1x1YjJlNC4mbmJzcDtcdWM3NzRcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MTVcdWMyMTgmbmJzcDtOLCBBLCBCLCBDLCBEICgxICZsZTsgTiAmbGU7IDUwMCAwMDAsIEEgJmxlOyBCICZsZTsgMTBeMTIsIDAgJmxlOyBDLCBEICZsZTsgTiwgQyArIEQgJmx0OyBOKVx1YWMwMCBcdWNjMjhcdWI4NDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzE1NFx1ZDUwYyBcdWMyMThcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHVjMjE4XHVjNWY0XHVjNWQwXHViMjk0IDFcdWJkODBcdWQxMzAgTlx1YWU0Y1x1YzljMFx1Yzc1OCBcdWMyMThcdWFjMDAgXHVkNTVjIFx1YmM4OFx1YzUyOSBcdWI0ZjFcdWM3YTVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWMyMThcdWM1ZjRcdWM3NTgga1x1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWFjMDAgeFx1Yjc3Y1x1YmE3NCwgXHVjNzc0XHViMjk0IFx1Y2U3NFx1YjRkY1x1Yjk3YyBcdWMxMWVcdWM3NDQgXHViNTRjIGtcdWJjODhcdWM5ZjggXHVjMjE4XHViOTdjIHhcdWJjODhcdWM5ZjhcdWI4NWMgXHVjNjJlXHVhZTM0XHViMmU0XHViMjk0IFx1Yzc1OFx1YmJmOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM5MDBcdWFkZGNcdWFjMDAgXHVjYzNlXHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI5MjQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHRU5JSkFMQUMiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGlzIGEgZ2VuaXVzLiBCdXQgdGhlIHB1cnBvc2Ugb2YgaGlzIGludmVudGlvbnMgaXMgbm90IGFsd2F5cyBvYnZpb3VzLiBIaXMgbGF0ZXN0IGludmVudGlvbiwgdGhlIFNodWZmbGUtby1tYXRpYyAzMTc1LCBpcyBvbmUgb2YgdGhvc2UuIFRoZSBTaHVmZmxlLW8tbWF0aWMgaXMgdXNlZCBpbiBhIHZlcnkgc3BlY2lhbCB3YXkuIEZpcnN0IE1pcmtvIHBsYWNlcyBOIHBhcGVyIGNhcmRzLCB3aXRoIG51bWJlcnMgMSB0byBOIHByaW50ZWQgb24gdGhlbSwgb24gdGhlIFNodWZmbGUtby1tYXRpYyB3b3JraW5nIHN1cmZhY2UuIFRoZW4gaGUgaW5wdXRzIHRoZSBzaHVmZmxlIHNlcXVlbmNlIGluIHRoZSBzcGVjaWFsIGlucHV0IGNvbnNvbGUgYW5kIGhpdHMgdGhlIGdvIGJ1dHRvbi4gVGhlIG1hY2hpbmUgdGhhbiByZWFkcyB0aGUgcGFwZXIgY2FyZHMgYW5kIG91dHB1dHMgdGhlIHJlYWQgc2VxdWVuY2Ugb2YgbnVtYmVycyBvbiBpdHMgb3V0cHV0IHRhcGUuIEl0IHRoYW4gc2h1ZmZsZXMgdGhlIGNhcmRzIGFjY29yZGluZyB0byB0aGUgc2h1ZmZsZSBzZXF1ZW5jZS4gQWZ0ZXIgdGhhdCBpdCByZWFkcyB0aGUgbmV3bHkgb2J0YWluZCBzZXF1ZW5jZSBhbmQgd3JpdGVzIGl0IG9udG8gYSBuZXcgbGluZSBvbiBpdHMgb3V0cHV0IHRhcGUuIFRoZW4gaXQgcHJvY2VkZXMgdG8gc2h1ZmZsZSB0aGUgY2FyZHMgYWdhaW4gYWNvcmRpbmcgdG8gdGhlIHNhbWUgc2h1ZmZsZSBzZXF1ZW5jZSwgc2NhbnMgYW5kIHdyaXRlcyB0aGUgb3V0cHV0IHRvIHRoZSB0YXBlLiBUaGUgbWFjaGluZSBkb2VzIHRoaXMgdW50aWwgaXQgcnVucyBvdXQgb2YgdGFwZS48XC9wPlxyXG5cclxuPHA+QWZ0ZXIgZXhwZXJpbWVudGluZyB3aXRoIHRoZSBtYWNoaW5lIE1pcmtvIGRlY2lkZWQgdG8gcmVzdCBhIGJpdCBvbiB0aGUgZmxvb3IuIFRoZXJlIGhlIG5vdGljZWQgYSBwaWVjZSBvZiBvdXRwdXQgdGFwZS4gVGhlIHBpZWNlIGlzIG5lYXRseSBjdXQganVzdCBiZWZvcmUgdGhlIEEtdGggb3V0cHV0IHJvdyBuYWQganVzdCBhZnRlciB0aGUgQi10aCBvdXRwdXQgcm93LiBJdCBpcyBhbHNvIG1pc3NpbmcgdGhlIGZpcnN0IEMgbnVtYmVyIGFuZCB0aGUgbGFzdCBEIG51bWJlcnMgaW4gYWxsIHJvd3MuPFwvcD5cclxuXHJcbjxwPkhlIG5vdyB3b25kZXJzIGhvdyBtYW55IHJvd3Mgb24gdGhhdCBwaWVjZSBvZiBwYXBlciBoYXZlIHRoZSBwcm9wZXJ0eSB0aGF0IGFsbCBudW1iZXJzIGluIHRoZSByb3csIHRoYXQgYXJlIHN0aWxsIG9uIHRoZSBwYXBlciwgYXJlIGluIHRoZSBleGFjdCBzYW1lIHNwb3QgdGhleSB3ZXJlIGJlZm9yZSBhbGwgdGhlIHNodWZmbGluZyBiZWdhbi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGludGVnZXJzIE4sIEEsIEIsIEMgYW5kIEQgaW4gdGhhdCBvcmRlcigxICZsZTsgTiAmbGU7IDUwMCAwMDAsIEEgJmxlOyBCICZsZTsgMTBeMTIsIDAgJmxlOyBDLCBEICZsZTsgTiwgQyArIEQgJmx0OyBOKS48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIHRoZSBzaHVmZmxlIHNlcXVlbmNlLiBUaGUgc2VxdWVuY2UgaXMgZ2l2ZW4gYXMgYSBwZXJtdXRhdGlvbiBvZiBudW1iZXJzIDEgdG8gTi4gSWYgdGhlIGstdGggbnVtYmVyIGluIHRoZSBzaHVmZmxlIHNlcXVlbmNlIGlzIHgsIGFmdGVyIGVhY2ggc2h1ZmZsZSB0aGUgay10aCBlbGVtZW50IGluIHRoZSByZXN1bHRpbmcgc2VxdWVuY2UgaXMgdGhlIHgtdGggZWxlbWVudCBpbiB0aGUgcHJldmlvdXMgc2VxdWVuY2UuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkluIHRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIGlucHV0IHByaW50IHRoZSBudW1iZXIgb2Ygcm93cyB0aGF0IGhhdmUgdGhlIHByb3BlcnR5IE1pcmtvIGlzIGxvb2tpbmcgZm9yLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

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