2870:身高排序

时间限制:4 S   /  内存限制:65536 KB
AC:70   /  Submit:86
描述

涂涂想把参加竞赛的队员们按身高从低到高排序排成一列纵队,也就是任意一对相邻的队员,排前面的队员身高总是小于等于后面的队员。

但他不想把这个问题变得如此简单,于是他给了自己一个例外的特权,允许在排序时,可以最多存在一对相邻的队员,排在前面的队员反而比后面的队员高。

已知所有队员的身高,问涂涂有多少种合理的排队方法?

注意:如果两个队员身高相同,他们之间交换位置,也算作另一种排队方法。涂涂可以选择不使用特权,就按顺序排序。

输入

多组案例。

一个正整数n,表示案例的数量。

每组案例中,第一行是正整数m,表示队员的数量。第二行是m个正整数,表示每个队员的身高。(m<=10)

输出

每组案例,输出一个正整数,表示合理的排队方法数量。输出后换行。

样例输入复制样例

2

3

170 180 185

3

175 175 190

样例输出

5

6

提示说明

第一组案例,合法的排序有:170 180 185、170 185 180、180 170 185、180 185 170、185 170 180

第二组案例,合法的排序有:175(1) 175(2) 190、175(2) 175(1) 190、175(1) 190 175(2)、175(2) 190 175(1)、190 175(1) 175(2)、190 175(2) 175(1)

相关

19-20(2)第6次线上赛

题单#6(全排列、二进制枚举)


Copyright 2016 - 2023 XUJC ACM Team
闽ICP备2020022076号-1