← 返回题目列表

AtCoder · abc439_d

G. 门松子序列

中文机器翻译题面 查看原题

分数: 425 点

问题陈述

给你一个整数序列 A=(A_1,A_2,\dots,A_N) 长度 N.
求整数三元组的个数 (i,j,k) 满足以下所有条件:

  • 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.

约束

  • 所有输入值均为整数。
  • 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

七个整数三元组 (i,j,k) 满足条件的是:

  • (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