链接: https://cses.fi/problemset/task/1162

板块: Additional Problems I

时限: 1.00 s ｜ 内存: 512 MB

题目描述

以下是一些可以将数组元素按升序排序的方法：

1. 每一步，选择两个相邻元素并交换它们。
2. 每一步，选择任意两个元素并交换它们。
3. 每一步，选择任意元素并将其移动到另一个位置。
4. 每一步，选择任意元素并将其移动到数组的最前面。

给定一个由数字 $1,2,\ldots,n$ 组成的排列，计算使用上述每种方法将数组排序所需的最少步数。

输入

第一行输入包含一个整数 $n$。

第二行包含 $n$ 个描述该排列的整数。

输出

输出四个数字：使用每种方法所需的最少步数。

数据范围

$1 \le n \le 2 \cdot 10^5$

样例输入

8
7 8 2 6 5 1 3 4

样例输出

20 6 5 6