Bitwise OR Sum of All Subarrays

Given a sequence \(a\) of length \(n\), compute the sum of the bitwise \(OR\) over all subarrays of \(a\). In other words, for every subarray \(a[l\ldots r]\), compute \(\text{OR}(a_l, a_{l+1}, \dots, a_r)\) and sum these values.

The formula can be written as:

\[ S=\sum_{l=1}^{n}\sum_{r=l}^{n}\left(\bigvee_{i=l}^{r}a_{i}\right), \]

where \(\bigvee\) denotes the bitwise \(OR\) operation.

inputFormat

The first line contains a single integer \(n\) representing the length of the sequence.

The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\), which form the sequence \(a\).

outputFormat

Output a single integer, the sum of the bitwise \(OR\) of all subarrays of \(a\).

sample

2
1 2

6