#P1092. 四元组计数

四元组计数

题目描述

给一个打乱的1~n的排列aia_i(1in1\le i \le n),要求计数形如(i,j,p,q)(i,j,p,q)的位置四元组数量。 其中要求:

  1. 1i<j<p<qn1 \le i<j<p<q \le n
  2. ai<ap<aj<aqa_i<a_p<a_j<a_q

一个简单的例子:例如n=4时,排列{1,3,2,4}具备一个这样的位置四元组。

输入格式

第一行一个正整数nn,表示排列的长度。

接下来一行nn个正整数,表示这个打乱的排列。其中保证11~nn各出现一次。

输出格式

一行一个整数表示有几个这样的四元组

5
1 3 2 4 5

2

数据规模与约定

测试点编号 数据范围
1-3 1n501 \le n \le 50
4-5 1n5001 \le n \le 500
5-10 1n50001 \le n\le 5000

大样例

大样例下载