AT_abc452_g [ABC452G] 221 Substring

正整数からなる数列 $ X = (X_1, \dots, X_n) $ に対し、その連長圧縮の任意の (長さ・値) ペアにおいて長さと値が等しいとき、かつそのときに限り、 $ X $ を **221 数列** と呼びます。より厳密には、以下の条件を満たす数列を 221 数列であるとします。 - $ 1 \leq l \leq r \leq n $ を満たす整数組 $ (l, r) $ が以下の $ 3 $ つの条件をすべて満たすならば、必ず $ (r-l+1) = X_l $ が成り立つ。 - $ l = 1 $ または ( $ l \geq 2 $ かつ $ X_{l-1} \neq X_l $ ) - $ r = n $ または ( $ r \leq n-1 $ かつ $ X_{r+1} \neq X_r $ ) - $ X_l = X_{l+1} = \dots = X_r $ たとえば、 $ (2,2,3,3,3,1,2,2) $ は 221 数列ですが、 $ (1,1) $ や $ (4,4,1,4,4) $ は 221 数列ではありません。 長さ $ N $ の正整数列 $ A = (A_1, \dots, A_N) $ が与えられます。 $ A $ の空でない**連続部分列**として現れる 221 数列としてあり得るものの個数を求めてください。 ただし、異なる位置から取り出した連続部分列であっても、数列として一致するものは区別せずまとめて $ 1 $ 通りとして数えます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $

答えを $ 1 $ 行に出力せよ。

### Sample Explanation 1 $ A $ の空でない連続部分列として現れる 221 数列は、以下の $ 14 $ 通りです。 - $ (1) $ - $ (1,2,2) $ - $ (1,3,3,3) $ - $ (1,3,3,3,1) $ - $ (1,3,3,3,1,2,2) $ - $ (1,4,4,4,4) $ - $ (2,2) $ - $ (2,2,1) $ - $ (2,2,3,3,3) $ - $ (2,2,3,3,3,1) $ - $ (3,3,3) $ - $ (3,3,3,1) $ - $ (3,3,3,1,2,2) $ - $ (4,4,4,4) $ ### Sample Explanation 2 $ A $ の空でない連続部分列として現れる 221 数列は存在しません。 ### Constraints - $ 1 \leq N \leq 500\,000 $ - $ 1 \leq A_i \leq 9 $ - 入力される値はすべて整数