D - スタンプラリー 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君は、一直線のコースで行われるスタンプラリーに参加しています。

コース上には N 箇所のチェックポイントがあり、スタート側から順にチェックポイント 1, 2, \dots, N と番号が付けられています。

チェックポイントで押すことができるスタンプは全部で 7 種類あり、1 以上 7 以下の整数で表されます。チェックポイント i (1 \le i \le N) を訪れると、種類 C_i のスタンプを 1 つ押すことができます。

高橋君は、連続する区間のチェックポイントを訪れて全 7 種類のスタンプをすべて集めたいと考えています。

形式的には、1 \le l \le r \le N を満たす整数の組 (l, r) であって、チェックポイント l, l+1, \dots, r を順に訪れたときに押せるスタンプの中に種類 1 から種類 7 までのスタンプがすべて含まれる（すなわち、集合 \{C_l, C_{l+1}, \dots, C_r\} が \{1, 2, 3, 4, 5, 6, 7\} と一致する）ものの総数を求めてください。

制約

  • 1 \le N \le 10^6
  • 1 \le C_i \le 7 (1 \le i \le N)
  • 入力はすべて整数

入力

入力は以下の形式で与えられる。

N
C_1 C_2 \dots C_N

出力

条件を満たす組 (l, r) の総数を 1 行に出力してください。

なお、答えは 32 bit 整数型に収まらない場合があることに注意してください。

入力例 1

8
1 2 3 4 5 6 7 1

出力例 1

3

入力例 2

9
1 2 3 4 5 6 1 2 3

出力例 2

0

入力例 3

24
3 7 1 2 4 5 6 2 3 1 7 4 5 6 6 5 4 3 2 1 7 1 2 3

出力例 3

145

入力例 4

70
3 1 4 1 5 7 2 6 5 3 5 7 1 2 4 6 3 2 7 1 5 4 6 2 3 7 1 4 5 6 1 2 3 4 5 6 7 7 6 5 4 3 2 1 1 3 5 7 2 4 6 2 4 6 1 3 5 7 7 5 3 1 6 4 2 1 2 3 4 5

出力例 4

1950

入力例 5

1
1

出力例 5

0

Score : 366 pts

Problem Statement

Takahashi is participating in a stamp rally held on a straight course.

There are N checkpoints along the course, numbered 1, 2, \dots, N in order from the start.

There are 7 types of stamps that can be collected at the checkpoints, represented by integers from 1 through 7. When visiting checkpoint i (1 \le i \le N), one can collect one stamp of type C_i.

Takahashi wants to collect all 7 types of stamps by visiting a contiguous range of checkpoints.

Formally, find the number of pairs of integers (l, r) satisfying 1 \le l \le r \le N such that the stamps collected when visiting checkpoints l, l+1, \dots, r in order contain all stamp types from 1 through 7 (that is, the set \{C_l, C_{l+1}, \dots, C_r\} equals \{1, 2, 3, 4, 5, 6, 7\}).

Constraints

  • 1 \le N \le 10^6
  • 1 \le C_i \le 7 (1 \le i \le N)
  • All input values are integers.

Input

The input is given in the following format:

N
C_1 C_2 \dots C_N

Output

Print the total number of pairs (l, r) that satisfy the condition in a single line.

Note that the answer may not fit in a 32-bit integer.

Sample Input 1

8
1 2 3 4 5 6 7 1

Sample Output 1

3

Sample Input 2

9
1 2 3 4 5 6 1 2 3

Sample Output 2

0

Sample Input 3

24
3 7 1 2 4 5 6 2 3 1 7 4 5 6 6 5 4 3 2 1 7 1 2 3

Sample Output 3

145

Sample Input 4

70
3 1 4 1 5 7 2 6 5 3 5 7 1 2 4 6 3 2 7 1 5 4 6 2 3 7 1 4 5 6 1 2 3 4 5 6 7 7 6 5 4 3 2 1 1 3 5 7 2 4 6 2 4 6 1 3 5 7 7 5 3 1 6 4 2 1 2 3 4 5

Sample Output 4

1950

Sample Input 5

1
1

Sample Output 5

0