Alice and Bob decided to play the following game on $$$n$$$ piles of stones where the $$$i^{th}(1 \le i \le n)$$$ pile contains $$$p_i$$$ stones, with Alice starting first :

• On his/her turn, he/she will choose any $$$k(1 \le k \le n)$$$ distinct arbitrary piles which have a positive number of stones(note that $$$k$$$ can be chosen arbitrarily by the current player). Now the player will remove exactly one stone each from all selected $$$k$$$ piles.

The player who cannot make a move loses. Note that both Alice and Bob are intelligent, so they always play optimally.

Now your task is to count the number of permutations$$$^\dagger$$$ $$$p$$$ of length $$$n$$$ such that the number of pairs ($$$l, r$$$)($$$1 \le l \le r \le n$$$), where Alice will win if both players play the game on piles $$$l, l+1, ..., r-1, r$$$, is maximum possible.

$$$^\dagger$$$ A permutation is an array of length $$$n$$$, where each number from $$$1$$$ to $$$n$$$ appears exactly once.