시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB180504333.858%

문제

상근이는 두 손자에게 크리스마스 선물을 주려고 한다. 오늘 상근이는 선물 N개를 구매했고, 손자들이 스스로 나누어 가지게 하려고 한다. 아이들은 번갈아가면서 선물을 하나씩 가져가고, 나이가 많은 손자(형) 먼저 시작한다. 상근이의 손자들은 순수함을 잃었기 때문에, 항상 남아있는 선물 중에서 가장 비싼 선물을 가져갈 것이다.

형이 가져간 선물 가격의 총 합이 동생의 합보다 적어도 A만큼 높지 않으면 형은 행복하지 않을 것이다. 또, 동생이 가져간 선물 가격의 총 합이 형의 합보다 많아야 B만큼 낮지 않으면 동생은 행복하지 않을 것이다. 즉, 두 손자를 행복하게 하기 위해서는 가져간 선물 가격의 총 합의 차이가 A와 B 안에 있어아 한다.

선물의 가격은 모두 양의 정수이다. 각 선물의 가격은 포장지에 붙여져 있다. 상근이는 쇼핑을 마치고 선물을 나누어 주기 전에 선물 하나에 가짜 가격을 붙이려고 한다. 이 가짜 가격도 자연수이어야 한다. 

N개의 선물 중 가격이 붙어있는 선물 N-1개의 가격이 주어진다. 이때, 두 손자를 행복하게 할 수 있는 가짜 가격의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, N이 주어진다. (1 ≤ A ≤ B ≤ 109, 1 ≤ N ≤ 100,000)

다음 N-1개 줄에는 선물의 가격이 한 줄에 하나씩 주어진다. 모든 가격은 109보다 작은 자연수이고, 내림차순으로 정렬되어져 있다. 가격이 붙어져 있지 않은 선물의 가격은 입력으로 주어지지 않는다.

출력

두 손자를 행복하게 만들 수 있는 가짜 가격의 수를 출력한다. 

예제 입력 1

3 3 4
5
5
5

예제 출력 1

2

예제 입력 2

50 60 3
100
20

예제 출력 2

22

예제 입력 3

6 15 7
17
13
10
10
6
2

예제 출력 3

23
W3sicHJvYmxlbV9pZCI6IjMxMzEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQwNmNcdWI5YWNcdWMyYTRcdWI5YzhcdWMyYTQgXHVjMTIwXHViYjNjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViNDUwIFx1YzE5MFx1Yzc5MFx1YzVkMFx1YWM4YyBcdWQwNmNcdWI5YWNcdWMyYTRcdWI5YzhcdWMyYTQgXHVjMTIwXHViYjNjXHVjNzQ0IFx1YzhmY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzYyNFx1YjI5OCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMTIwXHViYjNjIE5cdWFjMWNcdWI5N2MgXHVhZDZjXHViOWU0XHVkNTg4XHVhY2UwLCBcdWMxOTBcdWM3OTBcdWI0ZTRcdWM3NzQgXHVjMmE0XHVjMmE0XHViODVjIFx1YjA5OFx1YjIwNFx1YzViNCBcdWFjMDBcdWM5YzBcdWFjOGMgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNTQ0XHVjNzc0XHViNGU0XHVjNzQwIFx1YmM4OFx1YWMwOFx1YzU0NFx1YWMwMFx1YmE3NFx1YzExYyBcdWMxMjBcdWJiM2NcdWM3NDQgXHVkNTU4XHViMDk4XHVjNTI5IFx1YWMwMFx1YzgzOFx1YWMwMFx1YWNlMCwgXHViMDk4XHVjNzc0XHVhYzAwIFx1YjljZVx1Yzc0MCBcdWMxOTBcdWM3OTAoXHVkNjE1KSBcdWJhM2NcdWM4MDAgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVjMTkwXHVjNzkwXHViNGU0XHVjNzQwIFx1YzIxY1x1YzIxOFx1ZDU2OFx1Yzc0NCBcdWM3ODNcdWM1YzhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWQ1NmRcdWMwYzEgXHViMGE4XHVjNTQ0XHVjNzg4XHViMjk0IFx1YzEyMFx1YmIzYyBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YmU0NFx1YzJmYyBcdWMxMjBcdWJiM2NcdWM3NDQgXHVhYzAwXHVjODM4XHVhYzA4IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNjE1XHVjNzc0IFx1YWMwMFx1YzgzOFx1YWMwNCBcdWMxMjBcdWJiM2MgXHVhYzAwXHVhY2E5XHVjNzU4IFx1Y2QxZCBcdWQ1NjlcdWM3NzQgXHViM2Q5XHVjMGRkXHVjNzU4IFx1ZDU2OVx1YmNmNFx1YjJlNCBcdWM4MDFcdWM1YjRcdWIzYzQgQVx1YjljY1x1ZDA3YyBcdWIxOTJcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTc0IFx1ZDYxNVx1Yzc0MCBcdWQ1ODlcdWJjZjVcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzQ0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViNjEwLCBcdWIzZDlcdWMwZGRcdWM3NzQgXHVhYzAwXHVjODM4XHVhYzA0IFx1YzEyMFx1YmIzYyBcdWFjMDBcdWFjYTlcdWM3NTggXHVjZDFkIFx1ZDU2OVx1Yzc3NCBcdWQ2MTVcdWM3NTggXHVkNTY5XHViY2Y0XHViMmU0IFx1YjljZVx1YzU0NFx1YzU3YyBCXHViOWNjXHVkMDdjIFx1YjBhZVx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzQgXHViM2Q5XHVjMGRkXHVjNzQwIFx1ZDU4OVx1YmNmNVx1ZDU1OFx1YzljMCBcdWM1NGFcdWM3NDQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM5ODksIFx1YjQ1MCBcdWMxOTBcdWM3OTBcdWI5N2MgXHVkNTg5XHViY2Y1XHVkNTU4XHVhYzhjIFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWNcdWIyOTQgXHVhYzAwXHVjODM4XHVhYzA0IFx1YzEyMFx1YmIzYyBcdWFjMDBcdWFjYTlcdWM3NTggXHVjZDFkIFx1ZDU2OVx1Yzc1OCBcdWNjMjhcdWM3NzRcdWFjMDAgQVx1YzY0MCBCIFx1YzU0OFx1YzVkMCBcdWM3ODhcdWM1YjRcdWM1NDQgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMjBcdWJiM2NcdWM3NTggXHVhYzAwXHVhY2E5XHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LiBcdWFjMDEgXHVjMTIwXHViYjNjXHVjNzU4IFx1YWMwMFx1YWNhOVx1Yzc0MCBcdWQzZWNcdWM3YTVcdWM5YzBcdWM1ZDAgXHViZDk5XHVjNWVjXHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzFmY1x1ZDU1MVx1Yzc0NCBcdWI5YzhcdWNlNThcdWFjZTAgXHVjMTIwXHViYjNjXHVjNzQ0IFx1YjA5OFx1YjIwNFx1YzViNCBcdWM4ZmNcdWFlMzAgXHVjODA0XHVjNWQwIFx1YzEyMFx1YmIzYyBcdWQ1NThcdWIwOThcdWM1ZDAgXHVhYzAwXHVjOWRjIFx1YWMwMFx1YWNhOVx1Yzc0NCBcdWJkOTlcdWM3NzRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzQgXHVhYzAwXHVjOWRjIFx1YWMwMFx1YWNhOVx1YjNjNCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5OXHVhYzFjXHVjNzU4IFx1YzEyMFx1YmIzYyBcdWM5MTEgXHVhYzAwXHVhY2E5XHVjNzc0IFx1YmQ5OVx1YzViNFx1Yzc4OFx1YjI5NCBcdWMxMjBcdWJiM2MgTi0xXHVhYzFjXHVjNzU4IFx1YWMwMFx1YWNhOVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHViNDUwIFx1YzE5MFx1Yzc5MFx1Yjk3YyBcdWQ1ODlcdWJjZjVcdWQ1NThcdWFjOGMgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjOWRjIFx1YWMwMFx1YWNhOVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIEEsIEIsIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEEgJmxlOyBCICZsZTsgMTA8c3VwPjk8XC9zdXA+LCAxICZsZTsgTiAmbGU7IDEwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOLTFcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzEyMFx1YmIzY1x1Yzc1OCBcdWFjMDBcdWFjYTlcdWM3NzQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVhYzAwXHVhY2E5XHVjNzQwIDEwPHN1cD45PFwvc3VwPlx1YmNmNFx1YjJlNCBcdWM3OTFcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHVhY2UwLCBcdWIwYjRcdWI5YmNcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVjODE1XHViODJjXHViNDE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAwXHVhY2E5XHVjNzc0IFx1YmQ5OVx1YzViNFx1YzgzOCBcdWM3ODhcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YzEyMFx1YmIzY1x1Yzc1OCBcdWFjMDBcdWFjYTlcdWM3NDAgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViNDUwIFx1YzE5MFx1Yzc5MFx1Yjk3YyBcdWQ1ODlcdWJjZjVcdWQ1NThcdWFjOGMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjOWRjIFx1YWMwMFx1YWNhOVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjMxMzEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQT0tMT04iLCJkZXNjcmlwdGlvbiI6IjxwPkdyYW5kbWEgaGFzIHR3byBncmFuZGNoaWxkcmVuIHdobyBzaGUgbGlrZXMgdG8gZ2l2ZSBnaWZ0cyB0by4gVG9kYXkgc2hlIGJvdWdodCB0aGVtIE4gZ2lmdHMgb2YgdmFyaW91cyBwcmljZXMsIHdoaWNoIHRoZSBjaGlsZHJlbiBoYXZlIHRvIGRpdmlkZSBhbW9uZyB0aGVtc2VsdmVzLiBUaGUgY2hpbGRyZW4gYWx0ZXJuYXRlIGluIHRha2luZyBvbmUgZ2lmdCBlYWNoLCBzdGFydGluZyB3aXRoIHRoZSBvbGRlciBjaGlsZC4gR3JlZWR5IGFzIGtpZHMgYXJlLCB0aGV5IGFsd2F5cyB0YWtlIHRoZSBtb3N0IGV4cGVuc2l2ZSByZW1haW5pbmcgZ2lmdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+R3JhbmRtYSBrbm93cyB0aGF0IHRoZSBvbGRlciBjaGlsZCB3aWxsIG5vdCBiZSBoYXBweSB1bmxlc3MgdGhlIHRvdGFsIHZhbHVlIG9mIGhpcyBnaWZ0cyBpcyBhdCBsZWFzdCBBIG1vcmUgdGhhbiB0aGUgb3RoZXIga2lkJiMzOTtzLiBUaGUgeW91bmdlciBjaGlsZCB3aWxsIG5vdCBiZSBoYXBweSBpZiB0aGUgdmFsdWUgb2YgdGhlIG9sZGVyIGtpZCYjMzk7cyBnaWZ0cyBpcyBtb3JlIHRoYW4gQiBtb3JlIGhpcyBvd24uIEluIG90aGVyIHdvcmRzLCB0aGUgZGlmZmVyZW5jZSBvZiB0aGUgdG90YWwgdmFsdWVzIG9mIGdpZnRzIG11c3QgYmUgYmV0d2VlbiBBIGFuZCBCLCBpbmNsdXNpdmUsIHRvIG1ha2UgYm90aCBraWRzIGhhcHB5LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgdmFsdWVzIG9mIGdpZnRzIGFyZSBwb3NpdGl2ZSBpbnRlZ2Vycy4gVGhlIHZhbHVlIG9mIGVhY2ggZ2lmdCBpcyBjbGVhcmx5IHByaW50ZWQgb24gdGhlIGdpZnQsIGV4cGVjdCBvbiBvbmUgZ2lmdC4gQWZ0ZXIgc2hvcHBpbmcsIGJ1dCBiZWZvcmUgYnJpbmdpbmcgdGhlIGdpZnRzIGhvbWUsIGdyYW5kbWEgZGVjaWRlZCB0byBzdGljayBhIHBob255IHByaWNlIHRhZyBvbnRvIHRoYXQgb25lIGdpZnQgc28gdGhhdCBib3RoIGtpZHMgYXJlIGhhcHB5IGFmdGVyIHRoZXkgaGF2ZSBzcGxpdCB0aGUgZ2lmdHMuIE9mIGNvdXJzZSwgdGhlIHBob255IHByaWNlIG11c3QgYWxzbyBiZSBhbiBpbnRlZ2VyIChvciB0aGUga2lkcyB3aWxsIGZpbmQgaXQgc3VzcGljaW91cykuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGRldGVybWluZXMgaG93IG1hbnkgZGlmZmVyZW50IHByaWNlcyBzaGUgY2FuIHB1dCBvbiB0aGUgdW5sYWJlbGVkIGdpZnQuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0aHJlZSBpbnRlZ2VycyBBLCBCIGFuZCBOICgxICZsZTsgQSAmbGU7IEIgJmxlOyAxMDxzdXA+OTxcL3N1cD4sIDEgJmxlOyBOICZsZTsgMTAwIDAwMCkgc2VwYXJhdGVkIGJ5IHNwYWNlcy4gVGhlIG51bWJlcnMgQSBhbmQgQiByZXByZXNlbnQgdGhlIGtpZHMmIzM5OyBjb25kaXRpb25zLCB3aGlsZSB0aGUgbnVtYmVyIE4gaXMgdGhlIG51bWJlciBvZiBnaWZ0cy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4mbWludXM7MSBsaW5lcyBjb250YWlucyB0aGUgcHJpY2Ugb2Ygb25lIGdpZnQuIEFsbCBwcmljZXMgYXJlIGludGVnZXJzIGxlc3MgdGhhbiAxMDxzdXA+OTxcL3N1cD4uIFRoZSBwcmljZXMgd2lsbCBiZSBzb3J0ZWQgaW4gZGVzY2VuZGluZyBvcmRlci4gVGhlIHVubGFiZWxlZCBnaWZ0IGRvZXMgbm90IGFwcGVhciBpbiB0aGUgaW5wdXQsIG9mIGNvdXJzZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgYSBzaW5nbGUgaW50ZWdlciAmbmRhc2g7IHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IHByaWNlIHRhZ3MgZ3JhbmRtYSBjYW4gY2hvb3NlLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=