seuOJ418 - 构造数据

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：256 MiB
• 题目标签：冬季, 校赛, 初赛, 2022

题目描述

算法课的作业是完成一个统计数组$a$中逆序对数目的代码。

如果$i<j$，并且$a[i]>a[j]$,那么$a[i]$和$a[j]$就组成了一个逆序对。

LCL.作为助教，要帮忙生成测试数据来检查代码是否正确。LCL.发现有个同学的代码有点奇怪。

int ans = 0;
for(int i=1;i<=n;i++)
{
    for(int j=i+1;j<=n;j++)
    {
        if(a[i]>a[j])
        {
            swap(a[i],a[j]);
            ans++;
        }
    }
}
return ans;

很明显，这个代码是有问题的，但是，LCL.很忙，不想去纠错，只想生成一组数据让这个程序报错就好了。

LCL.生成数据的方式很简单粗暴，就是先生成$n$个数字，然后随机打乱这$n$个数字的顺序，生成若干个不同的序列。如果两个序列当中，存在一个数字不同，则认为这两个序列是不同的。LCL.发现，对于很多序列，这个代码能得到正确的答案。所以，LCL.想知道，对于已经生成的这$n$个数字，至少要生成多少个序列才能保证一定存在一个序列让这个学生的代码得到错误的答案。

如果，无法生成一个序列使得学生的代码得到错误的答案，则输出 Impossible! 。否则，输出LCL.最少要生产的序列数，由于这个数字可能很大，所以答案对 19260817 取模即可。

输入格式

第一行一个整数$n$,代表生成数字的个数。

第二行$n$个整数，表示生成的数字。

输出格式

输出一行，若无法生成一个序列使得学生的代码得到错误的答案，则输出 Impossible! 。

否则，输出一个整数，表示LCL.最少要生产的序列数，保证一定存在一个序列让这个学生的代码得到错误的答案。

样例

样例输入1

4
2 3 2 1

样例输出1

9

样例输入2

1
20221207

样例输出2

Impossible!

样例解释

对于样例1：   
一共有12个不同的序列，其中
2 2 1 3
2 2 3 1
2 3 2 1
3 2 2 1
这4个序列会使得学生代码得到错误的答案，所以至少要9个序列才能保证包含至少一个序列在这4个序列之中。

数据范围与提示

$1 \leq n \leq 10^5$

$0 \leq a_i \leq 10^9$