問題文

ある正整数列 $C=(C_1,C_2,\dots,C_k)$ を使って以下のゲームを行います。

最初 $k$ 個の石の山が左右一列に並んでおり、左から $i$ 番目の石の山には $C_i$ 個の石があります。 $2$ 人のプレイヤーが交互に次の操作を行います。

• 石が $1$ 個以上残っている山のうち最も左にあるものを選び、選んだ山から $1$ 個以上の石を取り除く。
• 操作後に全ての山についての石の個数のビットごとの排他的論理和が $0$ ならば操作を行ったプレイヤーが勝利し、ゲームは終了する。

ここで、 $2$ 人のプレイヤーが最善な操作を行った時のゲーム終了までの $2$ 人の操作回数の和を $f(C)$ とします。
ただし、最善な操作とは、勝利できるならそのうち操作回数の和が最小となる操作、勝利できないなら操作回数の和が最大となる操作します。

長さ $N$ の正整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます。
$A$ の空でない連続する部分列 $A_{l,\,r}=(A_l,A_{l+1},\dots,A_r)$ として考えられるものは $\displaystyle \frac{N(N+1)}{2}$ 通りありますが、それらに対する $f(A_{l,\,r})$ の総和を求めてください。

制約

• 入力は全て整数
• $1\le N\le 10^5$
• $1\le A_i\le 10^6\quad(1\le i\le N)$

入力

$N$
$A_1$ $A_2$ $\dots$ $A_N$

出力

答えとなる整数を $1$ 行で出力してください。

サンプル

3
1 2 3

12

10
3 1 4 1 5 9 2 6 5 3

170