← 返回题目列表

AtCoder · nikkei2019_2_final_a

A. 计数三元组

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

配点 : 200 点

問題文

高桥君 A_1, A_2, \cdots, A_N 的 N 由元素组成的整数序列 我有 A 。 求

A_i < A_j > A_k 满足 (i, j, k) (1 \leq i < j < k \leq N) 中的对数。

制約

  • 3 \leq N \leq 5000
  • 0 \leq A_i \leq 10^9
  • 所有输入均为整数 打印对数

入力

输入是按以下格式从标准输入给出的。

N
A_1 A_2 \cdots A_N

出力

A_i < A_j > A_k 满足 (i, j, k) (1 \leq i < j < k \leq N) 。


入力例 1

4
1 2 3 2

出力例 1

2

满足条件的集合为 有 (i, j, k) = (1, 3, 4), (2, 3, 4) 的 2 。 没有对


入力例 2

3
2 2 2

出力例 2

0

A_i < A_j > A_k 满足 (i, j, k) 。


入力例 3

10
0 7 7 6 9 8 1 3 2 0

出力例 3

57