4454. sort

【题目背景】

传闻有一种神奇的排序算法：奇迹排序。

只需要把待排序的数组放在那里，等待一束宇宙射线射向数组，使数组自动排好序。

可惜的是，这个算法的时间复杂度太大了，所以还是来研究冒泡排序吧。

【题目描述】

给定一个 $1\sim n$ 的排列，下标从 $1$ 开始，现在又一段对 $a$ 进行冒泡排序的伪代码。

01: Algorithm BubbleSort(a, n)
02:    for i ← 1 to n do
03:       for j ← 1 to n - i do
04:          if a[j] > a[j + 1] then
05:             Swap(a[j], a[j + 1])
06:          end if
07:       end for
08:    end for
09: end Algorithm

由于宇宙射线的影响，导致第 4 行的 if 语句在执行时，恰好有一次其的执行结果相反（即执行相反的分支）。

现在给出 $n,a$，求出在宇宙射线影响下，运行 BubbleSort(a,n) 后，本质不同的 $a$ 的个数（称两个排列 $p,q$ 本质不同，当且仅当存在 $ i\in [1,n],p_i\ne q_i$）。

【输入格式】

第一行，一个正整数 $n$。

第二行，$n$ 个用空格隔开的正整数，表示排列 $a$。

【输出格式】

一行，一个正整数，表示答案。

【样例输入1】

3
2 3 1

【样例输出1】

3

【样例输入2】

5
1 4 2 3 5

【样例输出2】

5

【样例说明】

对于第一个样例，可能的 $a$ 有：$[1,3,2],[2,3,1],[2,1,3]$。

大样例。

【数据规模与约定】

【来源】

在此键入。