【IDEA】试卷排序

U227762 试卷排序

题目背景

期末考试临近了，yz 和 zzw 收到了来自老师的试卷关爱，但是试卷太多了，足足有 \(10^{6}\) 张，他们已经无法排好试卷了。

所以在 zzy 的建议下，他们把这个问题交给了你。

题目描述

给定一个页码总数为 \(n\) 的试卷堆，每张试卷都有一个正整数编号 \(a_i\)（保证互不相同且属于 \(1\le a_i\le n\)），现要求你将它进行排序，你有如下两种操作：

1. 选定一张试卷，将之置于试卷堆顶部；

2. 选定一张试卷，将之置于试卷堆底部。

但由于 yz 和 zzw 的能力不同，所以你需要分别处理。

yz 希望能将试卷页码从小到大排列且操作次数最少，但只能实行操作 \(1\) ;

zzw 的希望与 yz 相同，但可以进行操作 \(1\) 和操作 \(2\) 。

输入格式

第一行一个整数 \(n\)。

第二行一个字符串 \(s\)，表示你将为谁进行试卷排序。

第三行共 \(n\) 个整数，分别为 \(a_1,a_2,\cdots,a_n\)，表示试卷页码的当前状态。

输出格式

输出共一行一个整数，为最少的操作次数。

输入输出样例 #1

输入 #1

5
yz
5 1 2 4 3

输出 #1

4

输入输出样例 #2

输入 #2

5
zzw
5 1 2 4 3

输出 #2

2

说明/提示

【数据范围】

对所有测试点保证 \(1 \leq n \leq 10^{6}\)，\(1 \leq a_i \leq n\)，\(a_i\) 互不相同。

测试点	\(n\)	\(s\)
\(1 \sim 2\)	\(=10\)	\(=\tt{yz}\)
\(3 \sim 4\)	\(=10^{3}\)	\(=\tt{yz}\)
\(5 \sim 8\)	\(=10^{6}\)	\(=\tt{yz}\)
\(9 \sim 10\)	\(=10\)	\(=\tt{zzw}\)
\(11 \sim 12\)	\(=10^{3}\)	\(=\tt{zzw}\)
\(13 \sim 20\)	\(=10^{6}\)	\(=\tt{zzw}\)

【本题来源】

• Idea & 题面：zzw；
• 数据：yz；
• 标程：njy；
• 验题：lhz；
• 题解：zzy。