题目描述

最近，Sempr 痴迷于一个名为“疯狂五数”的问题。给定 N（1 ≤ N ≤ 50000）个不超过 10⁹ 的数字，“疯狂五数”指满足以下条件的五元组 {i, j, k, l, m}：

1. 1 ≤ i < j < k < l < m ≤ N
2. A_i < A_j < A_k < A_l < A_m

例如，在序列 {2, 1, 3, 4, 5, 7, 6} 中，共有四个疯狂五数组合：{1, 3, 4, 5, 6}、{2, 3, 4, 5, 6}、{1, 3, 4, 5, 7} 和 {2, 3, 4, 5, 7}。

请你帮助 Sempr 统计每个序列中疯狂五数的数量。

输入

输入包含多个测试用例。每个测试用例的第一行是整数 N，第二行是 N 个数字。

输出

对每个测试用例，输出疯狂五数的数量。

输入示例 1

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

输出示例 1

1  
4  
21  

题目来源

POJ Monthly--2007.09.09, tdzl2003