P1036 The Couple Tokens

Problem Background

As we all know, the GCOI that Cui2010 leads and the (Republic of) AOCode that AppOfficer leads are competing in collecting tokens.

This time, someone told both of them that one kind of tokens, named the Couple Token, is very valuable and special. It’s owned by a classmate in AppOfficer’s class, named lyf. So AppOfficer get the Tokens easily.

Cui2010 is not very satisfied. he wants that kind of tokens too! So he asks lyf to give some of them to him. But lyf, also an OIer, asks Cui2010 to answer a question from her.

Can you help Cui2010 answer the problem?

Problem Statement

Here’s the question lyf give Cui2010:

There’re \(n\) students in Class \(x\) Junior 1 in the NFLS (Nasty Fluffy Lost School). The students have different genders. Student \(i\) (\(1 \le i \le n\)) has a gender of \(G_i\). Here, we use 0 to present a GIRL, 1 to present a BOY, 2 to present a HUMONSTER (sexless human), 3 to present an INTERSEX HUMAN, 4 to present a NON-HUMAN CREATURE. The students are ranged by their school numbers.

If there’re two students, with their school numbers \(i\) and \(j\) (\(1 \le i < j \le n\)), they’ll be considered as a couple if they satisfy all the conditions below:

• \(j-i \le \left\lfloor\dfrac{n}{2}\right\rfloor\).
• \((G_i=1 \land G_j=0) \lor (G_i=2 \land G_j=3) \lor (G_i=3 \land G_j=2) \lor (G_i=G_j=4)\).

Find out the number of couples that can be formed in Class \(x\) Junior 1.

Input

\(n\)
\(G_1\ G_2\ G_3\ \cdots\ G_n\)

Output

Only one line with the number of couples that can be formed.

Constraints

• For the first \(20\%\) test cases, \(n=52\).
  • For the \(50\%\) in the first \(20\%\), \(G=\left\{1,1,1,\cdots,1,0,0,0,\cdots,0\right\}\).
• For the second \(20\%\) test cases, \(G_i=0,1\ (1 \le i \le n)\).
• For all test cases:
  • \(52 \le n \le 100000\).
  • \(G_i=0,1,2,3,4\ (1 \le i \le n)\).

Samples

Input 1

52
1 1 1 1 1 1 1 1 1 1 2 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 3 1 1 1 1 1 1 1 4 1 1 0 0 0 0 0 0 0 0 0 0 0 0

Output 1

300

(NOTES: The sample INPUT 1 is the real gender description of NFLS Class 10 Junior 1 (202110).)

Some of the possible couples:

• No. \(28\) and No. \(50\).
• No. \(35\) and No. \(47\). (lyf: Oh NO!)

But the couples below are not available:

• No. \(8\) and No. \(44\).
• No. \(30\) and No. \(37\).
• No. \(31\) and No. \(32\).

Count all available couples, the answer is \(300\).

Input 2

53
1 1 1 1 4 1 3 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 4 1 1 4 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 2 1 1 0 0 0 3 0 0

Output 2

260

(NOTES: The sample INPUT 2 is the real gender description of NFLS Class 12 Junior 1 (202112).)

Some of the possible couples:

• No. \(12\) and No. \(36\).
• No. \(24\) and No. \(40\).
• No. \(27\) and No. \(52\).

But the couples below are not available:

• No. \(10\) and No. \(31\).
• No. \(14\) and No. \(44\).
• No. \(15\) and No. \(43\).

Count all available couples, the answer is \(260\).

\[\Huge\color{red}\textbf{WARNING}:\\\huge\color{black}-------------------------\\\color{black}\large\text{The story is NOT REAL!!!}\\\large\color{black}\large\text{And we suggests NOT TO GOSSIP in school!!!}\\\huge\color{black}-------------------------\]