The seven-legged spiders living in Byteland build webs with a very regular structure. Such a web consists of a central node, where the spider usually rests, and $d$ rings, numbered from 1 to $d$. Each ring is a cycle composed of nodes connected by threads.

Each node, except for those on ring $d$, is connected by threads to seven other nodes. The central node is connected to all seven nodes of ring 1. Each node in ring $i$ is connected to $k \in \{1, 2\}$ nodes in ring $i - 1$, two adjacent nodes in ring $i$, and $l = 5 - k$ subsequent nodes in ring $i + 1$. The first and last of these $l$ nodes are connected to two adjacent nodes in ring $i$, while the others are connected to only one. The network can always be drawn on a plane such that the threads do not intersect. The situation is shown in the figure below.

Such networks are very effective. Recently, Bytazar observed a spider's walk on a web with $d = 10^{9}$ rings. The spider started at the central node and then, moving along the threads, returned to the starting point without passing through any node more than once. A fly was caught in every node inside the polygon along whose boundary the spider moved. Bytazar noted the spider's consecutive moves during the walk and would like to calculate how many flies were caught.

Input

The first line of input contains a single integer $n$ ($3 \le n \le 7\,777\,777$) representing the length of the spider's walk, i.e., the number of nodes visited.

The second line contains a sequence of $n$ integers $z_{i}$ ($1 \le z_{i} \le 6$). It describes the consecutive turns the spider made during the walk. From the $i$-th node on the path, the spider exited via the $z_{i}$-th thread in clockwise order, where the thread the spider entered the node from is considered thread 0. The value $z_{1}$ applies to the first node encountered after leaving the central node, while $z_{n}$ describes the turn the spider would have to make at the central node if it wanted to traverse the entire route once more.

Output

Your program should output a single integer - the number of network nodes inside the polygon traversed by the spider.

Examples

Input 1

10
2 2 2 2 3 2 2 2 2 3

Output 1

2

Note

The polygon in the figure represents the spider's route. There are two nodes inside the polygon. Note that we do not count the nodes on the boundary of the polygon.