D - Kadomatsu Subsequence 解説 /

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

配点 : 425 点

問題文

長さ N の整数列 A=(A_1,A_2,\dots,A_N) が与えられます。
以下を全て満たす整数の 3 つ組 (i,j,k) がいくつあるか求めてください。

  • 1 \le i,j,k \le N
  • A_i : A_j : A_k = 7:5:3
  • \min(i,j,k) = j または \max(i,j,k) = j

制約

  • 入力は全て整数
  • 1 \le N \le 3 \times 10^5
  • 1 \le A_i \le 10^9

入力

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

N
A_1 A_2 \dots A_N

出力

答えを出力せよ。

入力例 1

10
3 10 7 10 7 6 7 6 5 14

出力例 1

7

条件を満たす整数の 3 つ組 (i,j,k) は以下の 7 個です。

  • (3,9,1)
    • A_i : A_j : A_k = 7:5:3 であり、 \max(i,j,k) = j です。
  • (5,9,1)
    • A_i : A_j : A_k = 7:5:3 であり、 \max(i,j,k) = j です。
  • (7,9,1)
    • A_i : A_j : A_k = 7:5:3 であり、 \max(i,j,k) = j です。
  • (10,2,6)
    • A_i : A_j : A_k = 14:10:6 = 7:5:3 であり、 \min(i,j,k) = j です。
  • (10,2,8)
    • A_i : A_j : A_k = 14:10:6 = 7:5:3 であり、 \min(i,j,k) = j です。
  • (10,4,6)
    • A_i : A_j : A_k = 14:10:6 = 7:5:3 であり、 \min(i,j,k) = j です。
  • (10,4,8)
    • A_i : A_j : A_k = 14:10:6 = 7:5:3 であり、 \min(i,j,k) = j です。

入力例 2

6
210 210 210 210 210 210

出力例 2

0

入力例 3

21
49 30 50 21 35 15 21 70 35 9 50 70 21 49 30 50 70 15 9 21 30

出力例 3

34

Score : 425 points

Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N.
Find the number of triples of integers (i,j,k) that satisfy all of the following:

  • 1 \le i,j,k \le N
  • A_i : A_j : A_k = 7:5:3
  • \min(i,j,k) = j or \max(i,j,k) = j.

Constraints

  • All input values are integers.
  • 1 \le N \le 3 \times 10^5
  • 1 \le A_i \le 10^9

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Output the answer.

Sample Input 1

10
3 10 7 10 7 6 7 6 5 14

Sample Output 1

7

The seven triples of integers (i,j,k) that satisfy the conditions are:

  • (3,9,1)
    • A_i : A_j : A_k = 7:5:3, and \max(i,j,k) = j.
  • (5,9,1)
    • A_i : A_j : A_k = 7:5:3, and \max(i,j,k) = j.
  • (7,9,1)
    • A_i : A_j : A_k = 7:5:3, and \max(i,j,k) = j.
  • (10,2,6)
    • A_i : A_j : A_k = 14:10:6 = 7:5:3, and \min(i,j,k) = j.
  • (10,2,8)
    • A_i : A_j : A_k = 14:10:6 = 7:5:3, and \min(i,j,k) = j.
  • (10,4,6)
    • A_i : A_j : A_k = 14:10:6 = 7:5:3, and \min(i,j,k) = j.
  • (10,4,8)
    • A_i : A_j : A_k = 14:10:6 = 7:5:3, and \min(i,j,k) = j.

Sample Input 2

6
210 210 210 210 210 210

Sample Output 2

0

Sample Input 3

21
49 30 50 21 35 15 21 70 35 9 50 70 21 49 30 50 70 15 9 21 30

Sample Output 3

34