Our social:

CodeChef | A Good Problem | August Challenge | Answer

Given an array A consisting of N integers - A1, A2....AN. You have to find the value of Σ MAX(i,j) * F(i,j)where 1 ≤ i < j ≤ N.

Image result for codechef


MAX(i,j) is defined as max(Ai,Ai+1...Aj).
F(i,j) is defined as:
  • F(i,j) will be 1 if (Ai&Aj) = Aj or (Ai&Aj) = Ai
  • F(i,j) will be 0, otherwise.
Here & denotes the bitwise AND operator.

Input

The first line of input will consist of integer N.
The next line of input will consists of N integers A1, A2....AN.

Output

Output the value of the above mentioned expression in a single line.

Constraints and Subtasks

Subtask #1 : (40 points)
  • 1 ≤ N ≤ 103
  • 0 ≤ Ai < 214

Subtask #2 : (60 points)

  • 1 ≤ N ≤ 105
  • 0 ≤ Ai < 214

Example

Input:
5
2 3 7 4 1
Output:
38

Explanation

The value of F(i,j) will be 1 for (1,2),(1,3),(2,3),(2,5),(3,4),(3,5).Therefore, answer will be MAX(1,2) + MAX(1,3) + MAX(2,3) + MAX(2,5) + MAX(3,4) + MAX(3,5) = 38.


                                                          ANSWER