Sau một chuỗi thua cược vì tụt rank liên tục, SPyofgame đang mắc một khoản nợ. Nhưng vì mải dùng tiền mua quà cho bạn gái nên giờ SPyofgame đã hết tiền để trả nợ. Vì thế, SPyofgame phải chơi một trò chơi do chủ nợ đưa ra. Nếu chiến thắng, số tiền nợ sẽ được giảm một nửa, còn nếu không, SPyofgame sẽ phải nhường bạn gái cho chủ nợ. Trò chơi được mô tả như sau:

Người chủ nợ sẽ đặt \(N\) số nguyên dương vào một vòng tròn và thực hiện các yêu cầu sau:

Người chơi đầu sẽ chọn một số nguyên dương bất kỳ
Người chơi thứ hai lấy một trong hai số liền kề với số mà người chơi thứ nhất đã lấy.
Người chơi tiếp theo sẽ lấy một số liền kề với bất kỳ số đã lấy trước đây. Trò chơi tiếp diễn cho đến khi hai người lấy hết được toàn bộ số trong vòng tròn. Người thắng cuộc là người lấy được nhiều số lẻ hơn (số chia \(2\) dư \(1\)).
Biết rằng SPyofgame sẽ luôn chơi tối ưu, nhưng anh ta không biết thực lực cụ thể của chủ nợ. Vì là người có quyền, chủ nợ sẽ luôn là người chơi trước. Chủ nợ muốn nhờ bạn tính xem có bao nhiêu cách chọn số đầu tiên để người chiến thắng là chủ nợ (đến đây chắc ai cũng biết chủ nợ là ai rồi)

Input

• Dòng đầu tiên chứa số nguyên dương \(N(1 \leq N \leq 100)\), là số lượng số được đặt trên vòng tròn. Dòng thứ hai gồm \(N\) số nguyên dương, số thứ \(i\) có giá trị \(a[i]\) là giá trị của vị trí thứ \(i\) trên hình tròn. \((1 \leq a[i] \leq 1000)\)

Output

• Một dòng duy nhất là kết quả của bài toán.

Example

3
3 1 5 

3