Description

Xiao Che wants to choose a perfect location to build a luxury villa for Xiao Meng. He has set his sights on a circular mountain range in the dreamland.

The mountain range is divided into $n$ segments, indexed from $1$ to $n$. Each segment has an altitude $a_i$. The spatial relationship is defined as follows: for any $2 \le i \le n$, the segment to the left of the $i$-th segment is the $(i-1)$-th segment, and the segment to the right of the $(i-1)$-th segment is the $i$-th segment. Specifically, the segment to the left of the $1$-st segment is the $n$-th segment, and the segment to the right of the $n$-th segment is the $1$-st segment.

Xiao Meng requires that the villa's location must not be on a slope. It must be either a peak or a valley. Specifically, the altitude of the chosen segment must be either strictly higher than the altitudes of both adjacent segments or strictly lower than both of them.

Xiao Che wants to know: how many such suitable locations exist?

Due to the limited capability of the problem setter, Little W, a complete terrain dataset could not be retrieved. Instead, the data is patched together from various sources. Some altitudes are provided in decimal, some in hexadecimal, and others in octal. Please refer to the Input Format for parsing details.

Input Format

The input consists of $n+1$ lines.

The first line contains a positive integer $n$, as described in the problem statement.

The next $n$ lines each contain a string representing the altitude $a_i$. The parsing rules are as follows:

• If the string ends with a digit, then $a_i$ is a standard decimal number.
• Otherwise, the last character indicates the base:
  • H or h: The number is in Hexadecimal (Base 16).
  • O or o: The number is in Octal (Base 8).
  • D or d: The number is in Decimal (Base 10).
  • The characters preceding the suffix represent the numerical value in that base.

It is guaranteed that all input strings represent valid numbers.

Note: Hexadecimal numbers may use uppercase letters, lowercase letters, or a mix of both (i.e., a/A represent $10$, ..., f/F represent $15$).

Output Format

A single line containing a single integer denoting the answer.

5
10aH
73o
60d
1
Abh

4

Hint

This problem uses bundled testing.

::cute-table{tuack}

For all test cases, it satisfies that $1\le n \le 5\times 10^4$ and $1\leq a_i\leq 10^{18}$.