You are given a string of digits from 1 to 8, each digit represents one of the 8 directions in clockwise order as shown in the following picture. The picture also states the changes in the X and Y coordinates for each direction.
Count the number of substrings such that if you start at (0, 0) and follow the directional moves in the substring, you will draw one closed convex polygon, that is, you need to finish at (0, 0), all interior angles should be less than or equal to 180°, and the polygon should not intersect itself.
The first line of input contains a single integer n (1 ≤ n ≤ 3 × 105), the length of the string.
The second line contains a string of n digits from 1 to 8.
Output on a single line with the number of substrings that draw out one closed convex polygon.
In the first sample test, substrings (1, 4), (2, 5), and (3, 6) draws the three convex polygons from left to right, respectively.
In the second sample test, the whole string represents a convex polygon, any other substring will be open, so the answer is 1.
In the third sample test, the whole string represents a closed polygon but it is not convex, other substrings draw open polygons, so the answer is 0.
## Input
The first line of input contains a single integer n (1 ≤ n ≤ 3 × 105), the length of the string.The second line contains a string of n digits from 1 to 8.
## Output
Output on a single line with the number of substrings that draw out one closed convex polygon.
[samples]
## Note
In the first sample test, substrings (1, 4), (2, 5), and (3, 6) draws the three convex polygons from left to right, respectively.In the second sample test, the whole string represents a convex polygon, any other substring will be open, so the answer is 1.In the third sample test, the whole string represents a closed polygon but it is not convex, other substrings draw open polygons, so the answer is 0.
**Definitions**
Let $ s \in \{1, 2, \dots, 8\}^n $ be a string of length $ n $, where each digit represents a direction in clockwise order on the 8-cardinal grid.
Define direction vectors $ \vec{d}_i \in \mathbb{Z}^2 $ for $ i \in \{1, \dots, 8\} $ as:
$$
\vec{d}_1 = (1,0),\ \vec{d}_2 = (1,1),\ \vec{d}_3 = (0,1),\ \vec{d}_4 = (-1,1),\ \vec{d}_5 = (-1,0),\ \vec{d}_6 = (-1,-1),\ \vec{d}_7 = (0,-1),\ \vec{d}_8 = (1,-1)
$$
For a substring $ s[i:j] $ (1-indexed, inclusive), define the displacement:
$$
\Delta(i,j) = \sum_{k=i}^{j} \vec{d}_{s[k]}
$$
Define the path $ P(i,j) = \left( \sum_{k=i}^{m} \vec{d}_{s[k]} \right)_{m=i}^{j} $ as the sequence of points visited starting from $ (0,0) $.
**Constraints**
1. $ 1 \le n \le 3 \times 10^5 $
2. $ s[k] \in \{1, 2, \dots, 8\} $ for all $ k \in \{1, \dots, n\} $
**Objective**
Count the number of substrings $ s[i:j] $ such that:
1. $ \Delta(i,j) = (0,0) $ (closed path),
2. The path $ P(i,j) $ does not self-intersect,
3. All interior angles of the polygon formed are $ \le 180^\circ $ (convexity).