Uolevi ja Maija pelaavat seuraavaa peliä:

Pelissä on joukko tikkukasoja. Jokaisella siirrolla pelaaja saa valita yhden kasan ja poistaa siitä minkä tahansa määrän tikkuja. Pelin voittaja on se, joka poistaa viimeisen tikun.

Maija aloittaa pelin ja molemmat pelaavat optimaalisesti. Mutta ennen peliä Uolevi saa valita, mitkä tikkukasat ovat. Tarjolla on n vierekkäistä kasaa ja Uolevi valitsee niistä jonkin välin kaikki kasat. Kasoja täytyy olla ainakin yksi.

Kuinka monta tapaa Uolevilla on valita kasat niin, että hän voittaa pelin?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: kasojen määrä.

Tämän jälkeen syötteessä on n kokonaislukua x_1,x_2,\ldots,x_n: montako tikkua kussakin kasassa on.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: monellako tavalla Uolevi voi valita kasat niin, että hän voittaa pelin.

Rajat

• 1 \le n \le 10^5
• 1 \le x_i \le 10^9

Esimerkki

Syöte:

6
2 4 4 5 3 6

Tuloste:

3

Selitys: Uolevi voi valita kasat [4, 4], [5, 3, 6] tai [4, 4, 5, 3, 6].