Ana şi Bogdan au primit de la bunica N cadouri. Acum ei împart cadourile, luând alternativ câte un cadou. Primul cadou îl ia Ana. Când îi vine rândul, fiecare copil va lua un cadou cu preţul cel mai mare dintre cele rămase. Bunica ştie că Ana nu va fi mulţumită decât dacă valoarea totală a cadourilor ei este cu cel puţin A mai mare decât valoarea totală a cadourilor lui Bogdan. În acelaşi timp, Bogdan nu va fi mulţumit decât dacă valoarea totală a cadourilor Anei este cu cel mult B mai mare decât valoarea totală a cadourilor sale. Mai exact, diferenţa dintre valoarea totală a cadourilor Anei şi valoarea totală a cadourilor lui Bogdan trebuie să fie în intervalul [A, B].
Preţurile cadourilor sunt numere naturale, fiecare cadou având o etichetă cu preţul. Când se întoarce de la cumpărături, bunica alege un cadou şi lipeşte pe el un preţ fictiv (de asemenea număr natural), astfel încât ambii copii să fie mulţumiţi după împărţirea cadourilor.
Cerinţă
Scrieţi un program care să determine câte preţuri fictive distincte pot fi alese pentru etichetarea cadoului ales.
Date de intrare
Fişierul de intrare cadou.in conţine pe prima linie trei numere naturale A B N, cu semnificaţia din enunţ, separate prin spaţii. Pe următoarele N-1 linii sunt scrise preţurile celor N-1 cadouri, câte un preţ pe o linie. Evident, preţul cadoului care va fi etichetat de bunica nu este scris. Preţurile sunt specificate în ordine descrescătoare.
Date de ieşire
Fişierul de ieşire cadou.out va conţine o singură linie pe care va fi scris un număr natural reprezentând numărul de preţuri fictive distincte ce pot fi alese pentru etichetarea cadoului.
Restricţii
1 ≤A ≤B ≤109
1 ≤N ≤100 000
Preţurile cadourilor sunt ≤109
Pentru teste valorând în total 50 de puncte, N ≤ 100
Pentru teste valorând în total 80 de puncte A, N ≤10 000.
Exemple
cadou.in
cadou.out
Explicaţii
3 3 4
5
5
5
2
Diferenţa dintre valoarea totală a cadourilor Anei şi valoarea totală a cadourilor lui Bogdan trebuie să fie exact 3.
Preţurile fictive posibile sunt 2 şi 8.