For a sequence of integers $$$[x_1, x_2, \dots, x_k]$$$, let's define its decomposition as follows:

Process the sequence from the first element to the last one, maintaining the list of its subsequences. When you process the element $$$x_i$$$, append it to the end of the first subsequence in the list such that the bitwise AND of its last element and $$$x_i$$$ is greater than $$$0$$$. If there is no such subsequence in the list, create a new subsequence with only one element $$$x_i$$$ and append it to the end of the list of subsequences.

For example, let's analyze the decomposition of the sequence $$$[1, 3, 2, 0, 1, 3, 2, 1]$$$:

processing element $$$1$$$, the list of subsequences is empty. There is no subsequence to append $$$1$$$ to, so we create a new subsequence $$$[1]$$$;
processing element $$$3$$$, the list of subsequences is $$$[[1]]$$$. Since the bitwise AND of $$$3$$$ and $$$1$$$ is $$$1$$$, the element is appended to the first subsequence;
processing element $$$2$$$, the list of subsequences is $$$[[1, 3]]$$$. Since the bitwise AND of $$$2$$$ and $$$3$$$ is $$$2$$$, the element is appended to the first subsequence;
processing element $$$0$$$, the list of subsequences is $$$[[1, 3, 2]]$$$. There is no subsequence to append $$$0$$$ to, so we create a new subsequence $$$[0]$$$;
processing element $$$1$$$, the list of subsequences is $$$[[1, 3, 2], [0]]$$$. There is no subsequence to append $$$1$$$ to, so we create a new subsequence $$$[1]$$$;
processing element $$$3$$$, the list of subsequences is $$$[[1, 3, 2], [0], [1]]$$$. Since the bitwise AND of $$$3$$$ and $$$2$$$ is $$$2$$$, the element is appended to the first subsequence;
processing element $$$2$$$, the list of subsequences is $$$[[1, 3, 2, 3], [0], [1]]$$$. Since the bitwise AND of $$$2$$$ and $$$3$$$ is $$$2$$$, the element is appended to the first subsequence;
processing element $$$1$$$, the list of subsequences is $$$[[1, 3, 2, 3, 2], [0], [1]]$$$. The element $$$1$$$ cannot be appended to any of the first two subsequences, but can be appended to the third one.

The resulting list of subsequences is $$$[[1, 3, 2, 3, 2], [0], [1, 1]]$$$.

Let $$$f([x_1, x_2, \dots, x_k])$$$ be the number of subsequences the sequence $$$[x_1, x_2, \dots, x_k]$$$ is decomposed into.

Now, for the problem itself.

You are given a sequence $$$[a_1, a_2, \dots, a_n]$$$, where each element is an integer from $$$0$$$ to $$$3$$$. Let $$$a[i..j]$$$ be the sequence $$$[a_i, a_{i+1}, \dots, a_j]$$$. You have to calculate $$$\sum \limits_{i=1}^n \sum \limits_{j=i}^n f(a[i..j])$$$.

Input

The first line contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 3$$$).

Output

Print one integer, which should be equal to $$$\sum \limits_{i=1}^n \sum \limits_{j=i}^n f(a[i..j])$$$.

Decomposition

Examples