시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 53 11 10 33.333%

문제

상근이는 두 손자에게 크리스마스 선물을 주려고 한다. 오늘 상근이는 선물 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
W3sicHJvYmxlbV9pZCI6IjMxMzEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQwNmNcdWI5YWNcdWMyYTRcdWI5YzhcdWMyYTQgXHVjMTIwXHViYjNjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViNDUwIFx1YzE5MFx1Yzc5MFx1YzVkMFx1YWM4YyBcdWQwNmNcdWI5YWNcdWMyYTRcdWI5YzhcdWMyYTQgXHVjMTIwXHViYjNjXHVjNzQ0IFx1YzhmY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzYyNFx1YjI5OCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMTIwXHViYjNjIE5cdWFjMWNcdWI5N2MgXHVhZDZjXHViOWU0XHVkNTg4XHVhY2UwLCBcdWMxOTBcdWM3OTBcdWI0ZTRcdWM3NzQgXHVjMmE0XHVjMmE0XHViODVjIFx1YjA5OFx1YjIwNFx1YzViNCBcdWFjMDBcdWM5YzBcdWFjOGMgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNTQ0XHVjNzc0XHViNGU0XHVjNzQwIFx1YmM4OFx1YWMwOFx1YzU0NFx1YWMwMFx1YmE3NFx1YzExYyBcdWMxMjBcdWJiM2NcdWM3NDQgXHVkNTU4XHViMDk4XHVjNTI5IFx1YWMwMFx1YzgzOFx1YWMwMFx1YWNlMCwgXHViMDk4XHVjNzc0XHVhYzAwIFx1YjljZVx1Yzc0MCBcdWMxOTBcdWM3OTAoXHVkNjE1KSBcdWJhM2NcdWM4MDAgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVjMTkwXHVjNzkwXHViNGU0XHVjNzQwIFx1YzIxY1x1YzIxOFx1ZDU2OFx1Yzc0NCBcdWM3ODNcdWM1YzhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWQ1NmRcdWMwYzEgXHViMGE4XHVjNTQ0XHVjNzg4XHViMjk0IFx1YzEyMFx1YmIzYyBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YmU0NFx1YzJmYyBcdWMxMjBcdWJiM2NcdWM3NDQgXHVhYzAwXHVjODM4XHVhYzA4IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNjE1XHVjNzc0IFx1YWMwMFx1YzgzOFx1YWMwNCBcdWMxMjBcdWJiM2MgXHVhYzAwXHVhY2E5XHVjNzU4IFx1Y2QxZCBcdWQ1NjlcdWM3NzQgXHViM2Q5XHVjMGRkXHVjNzU4IFx1ZDU2OVx1YmNmNFx1YjJlNCBcdWM4MDFcdWM1YjRcdWIzYzQgQVx1YjljY1x1ZDA3YyBcdWIxOTJcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTc0IFx1ZDYxNVx1Yzc0MCBcdWQ1ODlcdWJjZjVcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzQ0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViNjEwLCBcdWIzZDlcdWMwZGRcdWM3NzQgXHVhYzAwXHVjODM4XHVhYzA0IFx1YzEyMFx1YmIzYyBcdWFjMDBcdWFjYTlcdWM3NTggXHVjZDFkIFx1ZDU2OVx1Yzc3NCBcdWQ2MTVcdWM3NTggXHVkNTY5XHViY2Y0XHViMmU0IFx1YjljZVx1YzU0NFx1YzU3YyBCXHViOWNjXHVkMDdjIFx1YjBhZVx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzQgXHViM2Q5XHVjMGRkXHVjNzQwIFx1ZDU4OVx1YmNmNVx1ZDU1OFx1YzljMCBcdWM1NGFcdWM3NDQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM5ODksIFx1YjQ1MCBcdWMxOTBcdWM3OTBcdWI5N2MgXHVkNTg5XHViY2Y1XHVkNTU4XHVhYzhjIFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWNcdWIyOTQgXHVhYzAwXHVjODM4XHVhYzA0IFx1YzEyMFx1YmIzYyBcdWFjMDBcdWFjYTlcdWM3NTggXHVjZDFkIFx1ZDU2OVx1Yzc1OCBcdWNjMjhcdWM3NzRcdWFjMDAgQVx1YzY0MCBCIFx1YzU0OFx1YzVkMCBcdWM3ODhcdWM1YjRcdWM1NDQgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMjBcdWJiM2NcdWM3NTggXHVhYzAwXHVhY2E5XHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LiBcdWFjMDEgXHVjMTIwXHViYjNjXHVjNzU4IFx1YWMwMFx1YWNhOVx1Yzc0MCBcdWQzZWNcdWM3YTVcdWM5YzBcdWM1ZDAgXHViZDk5XHVjNWVjXHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzFmY1x1ZDU1MVx1Yzc0NCBcdWI5YzhcdWNlNThcdWFjZTAgXHVjMTIwXHViYjNjXHVjNzQ0IFx1YjA5OFx1YjIwNFx1YzViNCBcdWM4ZmNcdWFlMzAgXHVjODA0XHVjNWQwIFx1YzEyMFx1YmIzYyBcdWQ1NThcdWIwOThcdWM1ZDAgXHVhYzAwXHVjOWRjIFx1YWMwMFx1YWNhOVx1Yzc0NCBcdWJkOTlcdWM3NzRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzQgXHVhYzAwXHVjOWRjIFx1YWMwMFx1YWNhOVx1YjNjNCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5OXHVhYzFjXHVjNzU4IFx1YzEyMFx1YmIzYyBcdWM5MTEgXHVhYzAwXHVhY2E5XHVjNzc0IFx1YmQ5OVx1YzViNFx1Yzc4OFx1YjI5NCBcdWMxMjBcdWJiM2MgTi0xXHVhYzFjXHVjNzU4IFx1YWMwMFx1YWNhOVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHViNDUwIFx1YzE5MFx1Yzc5MFx1Yjk3YyBcdWQ1ODlcdWJjZjVcdWQ1NThcdWFjOGMgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjOWRjIFx1YWMwMFx1YWNhOVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIEEsIEIsIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEEgJmxlOyBCICZsZTsgMTA8c3VwPjk8XC9zdXA+LCAxICZsZTsgTiAmbGU7IDEwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOLTFcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzEyMFx1YmIzY1x1Yzc1OCBcdWFjMDBcdWFjYTlcdWM3NzQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0Llx1YmFhOFx1YjRlMCBcdWFjMDBcdWFjYTlcdWM3NDAgMTA8c3VwPjk8XC9zdXA+XHViY2Y0XHViMmU0IFx1Yzc5MVx1Yzc0MCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NzRcdWFjZTAsIFx1YjBiNFx1YjliY1x1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM4MTVcdWI4MmNcdWI0MThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDBcdWFjYTlcdWM3NzQgXHViZDk5XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM3NDAgXHVjMTIwXHViYjNjXHVjNzU4IFx1YWMwMFx1YWNhOVx1Yzc0MCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWI0NTAgXHVjMTkwXHVjNzkwXHViOTdjIFx1ZDU4OVx1YmNmNVx1ZDU1OFx1YWM4YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWM5ZGMgXHVhYzAwXHVhY2E5XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzEzMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBPS0xPTiIsImRlc2NyaXB0aW9uIjoiPHA+R3JhbmRtYSBoYXMgdHdvIGdyYW5kY2hpbGRyZW4gd2hvIHNoZSBsaWtlcyB0byBnaXZlIGdpZnRzIHRvLiBUb2RheSBzaGUgYm91Z2h0IHRoZW0gTiBnaWZ0cyBvZiB2YXJpb3VzIHByaWNlcywgd2hpY2ggdGhlIGNoaWxkcmVuIGhhdmUgdG8gZGl2aWRlIGFtb25nIHRoZW1zZWx2ZXMuIFRoZSBjaGlsZHJlbiBhbHRlcm5hdGUgaW4gdGFraW5nIG9uZSBnaWZ0IGVhY2gsIHN0YXJ0aW5nIHdpdGggdGhlIG9sZGVyIGNoaWxkLiBHcmVlZHkgYXMga2lkcyBhcmUsIHRoZXkgYWx3YXlzIHRha2UgdGhlIG1vc3QgZXhwZW5zaXZlIHJlbWFpbmluZyBnaWZ0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5HcmFuZG1hIGtub3dzIHRoYXQgdGhlIG9sZGVyIGNoaWxkIHdpbGwgbm90IGJlIGhhcHB5IHVubGVzcyB0aGUgdG90YWwgdmFsdWUgb2YgaGlzIGdpZnRzIGlzIGF0IGxlYXN0IEEgbW9yZSB0aGFuIHRoZSBvdGhlciBraWQmIzM5O3MuIFRoZSB5b3VuZ2VyIGNoaWxkIHdpbGwgbm90IGJlIGhhcHB5IGlmIHRoZSB2YWx1ZSBvZiB0aGUgb2xkZXIga2lkJiMzOTtzIGdpZnRzIGlzIG1vcmUgdGhhbiBCIG1vcmUgaGlzIG93bi4gSW4gb3RoZXIgd29yZHMsIHRoZSBkaWZmZXJlbmNlIG9mIHRoZSB0b3RhbCB2YWx1ZXMgb2YgZ2lmdHMgbXVzdCBiZSBiZXR3ZWVuIEEgYW5kIEIsIGluY2x1c2l2ZSwgdG8gbWFrZSBib3RoIGtpZHMgaGFwcHkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSB2YWx1ZXMgb2YgZ2lmdHMgYXJlIHBvc2l0aXZlIGludGVnZXJzLiBUaGUgdmFsdWUgb2YgZWFjaCBnaWZ0IGlzIGNsZWFybHkgcHJpbnRlZCBvbiB0aGUgZ2lmdCwgZXhwZWN0IG9uIG9uZSBnaWZ0LiBBZnRlciBzaG9wcGluZywgYnV0IGJlZm9yZSBicmluZ2luZyB0aGUgZ2lmdHMgaG9tZSwgZ3JhbmRtYSBkZWNpZGVkIHRvIHN0aWNrIGEgcGhvbnkgcHJpY2UgdGFnIG9udG8gdGhhdCBvbmUgZ2lmdCBzbyB0aGF0IGJvdGgga2lkcyBhcmUgaGFwcHkgYWZ0ZXIgdGhleSBoYXZlIHNwbGl0IHRoZSBnaWZ0cy4gT2YgY291cnNlLCB0aGUgcGhvbnkgcHJpY2UgbXVzdCBhbHNvIGJlIGFuIGludGVnZXIgKG9yIHRoZSBraWRzIHdpbGwgZmluZCBpdCBzdXNwaWNpb3VzKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgZGV0ZXJtaW5lcyBob3cgbWFueSBkaWZmZXJlbnQgcHJpY2VzIHNoZSBjYW4gcHV0IG9uIHRoZSB1bmxhYmVsZWQgZ2lmdC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRocmVlIGludGVnZXJzIEEsIEIgYW5kIE4gKDEgJmxlOyBBICZsZTsgQiAmbGU7IDEwPHN1cD45PFwvc3VwPiwgMSAmbGU7IE4gJmxlOyAxMDAgMDAwKSBzZXBhcmF0ZWQgYnkgc3BhY2VzLiBUaGUgbnVtYmVycyBBIGFuZCBCIHJlcHJlc2VudCB0aGUga2lkcyYjMzk7IGNvbmRpdGlvbnMsIHdoaWxlIHRoZSBudW1iZXIgTiBpcyB0aGUgbnVtYmVyIG9mIGdpZnRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiZtaW51czsxIGxpbmVzIGNvbnRhaW5zIHRoZSBwcmljZSBvZiBvbmUgZ2lmdC4gQWxsIHByaWNlcyBhcmUgaW50ZWdlcnMgbGVzcyB0aGFuIDEwPHN1cD45PFwvc3VwPi4gVGhlIHByaWNlcyB3aWxsIGJlIHNvcnRlZCBpbiBkZXNjZW5kaW5nIG9yZGVyLiBUaGUgdW5sYWJlbGVkIGdpZnQgZG9lcyBub3QgYXBwZWFyIGluIHRoZSBpbnB1dCwgb2YgY291cnNlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBhIHNpbmdsZSBpbnRlZ2VyICZuZGFzaDsgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgcHJpY2UgdGFncyBncmFuZG1hIGNhbiBjaG9vc2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==