题目描述
如果一个长度为 n 的序列存在一个位置 k(1≤k≤n),使得 ai<ai+1 对所有 1≤i<k 成立,并且 ai>ai+1 对所有 k≤i<n 成立,则称这个序列为单峰序列。
一个序列的权值是将它变成单峰序列所需的最少相邻交换次数。一次操作交换两个相邻的元素。
给定一个长度为 n 的排列 a1,a2,…,an。根据测试点类型,求整个排列或排列每个前缀的权值。
输入格式
第一行两个整数 n,t,分别表示排列长度和测试点类型。
第二行 n 个整数 a1,a2,…,an,表示 1 到 n 的一个排列。
原题文件名为 seq.in 和 seq.out。
输出格式
若 t=0,输出一行一个非负整数,表示整个排列的权值。
若 t=1,输出 n 行。第 i 行是前缀 a1,a2,…,ai 的权值。
样例
10 1
2 10 5 1 3 7 4 9 6 8
0
0
0
0
1
4
6
8
9
11
数据范围
1≤n≤5×105,t∈{0,1}。
| 测试点 |
n 的上限 |
t |
| 1–2 |
20 |
1 |
| 3–4 |
100 |
| 5–6 |
500 |
| 7–8 |
1000 |
| 9–10 |
5000 |
0 |
| 11–12 |
1 |
| 13–15 |
5×105 |
0 |
| 16–20 |
2×105 |
1 |
| 21–25 |
5×105 |