#P16126. [2026年山东集训一轮]第一题

[2026年山东集训一轮]第一题

题目描述

给定一个 1∼n1\sim n 的排列 aa。

对于一个 1∼n1\sim n 的排列 bb,定义权值 f(b)f(b) 为:最少进行多少次如下操作,才能把 aa 变成 bb:

  • 交换两个位置相邻但值不相邻的元素,即若当前排列中相邻两个元素为 x,yx,y,只有当 ∣x−y∣≥2|x-y|\ge 2 时,才允许交换它们。

特别地,若不可能把 aa 变成 bb,则定义 f(b):=0f(b):=0。

请计算所有排列 bb 的 f(b)f(b) 之和,并对 109+710^9+7 取模。

输入格式

第一行一个正整数 nn。

第二行 nn 个整数,表示排列 a1,a2,…,ana_1,a_2,\dots,a_n。

输出格式

输出一行一个整数,表示答案。

样例 1 输入

4
3 1 2 4

样例 1 输出

6

样例 2 输入

4
1 2 3 4

样例 2 输出

0

样例 3 输入

9
1 9 2 6 8 7 5 4 3

样例 3 输出

7206

数据范围与约定

子任务编号 分值 数据范围
1 15 n≤8n\le 8
2 20 n≤15n\le 15
3 30 n≤30n\le 30
4 20 n≤50n\le 50
5 15 n≤100n\le 100