#CF2266H. Deque Malfunction

Deque Malfunction

题目描述

Vihaan 自己实现了一个双端队列(deque),但它有时会发生故障。

Vihaan 希望最终双端队列中的内容从前到后为 [1,2,…,n][1,2,\ldots,n]。

给定一个长度为 mm 的数组 bb。元素按 b1,b2,…,bmb_1,b_2,\ldots,b_m 的顺序依次到达。

每当一个元素 bib_i 到达时,Vihaan 必须执行以下操作之一:

  • 将 bib_i 推入双端队列的 front(前端)。
  • 将 bib_i 推入双端队列的 back(后端)。
  • 让双端队列发生故障,将 bib_i 插入到双端队列中任意他选择的位置。

此外,Vihaan 还可以在任意时刻执行以下操作之一:

  • 移除双端队列 front(前端)的元素。
  • 移除双端队列 back(后端)的元素。

在所有 mm 个元素都到达并且所有操作都执行完毕后,双端队列必须恰好包含 [1,2,…,n][1,2,\ldots,n],且顺序一致。

求使得双端队列发生故障的最少次数,以得到 [1,2,…,n][1,2,\ldots,n];若不可能,则判定为不可能。

输入格式

第一行包含一个整数 tt (1≤t≤1041 \le t \le 10^4)—测试用例的数量。

每个测试用例的第一行包含两个整数 nn 和 mm (1≤n≤m≤2⋅1051 \le n \le m \le 2 \cdot 10^5)—目标双端队列的长度和到达元素的数量。

第二行包含 mm 个整数 b1,b2,…,bmb_1,b_2,\ldots,b_m (1≤bi≤n1 \le b_i \le n)—元素到达的顺序。

保证所有测试用例中 mm 的总和不超过 2⋅1052 \cdot 10^5。

输出格式

对于每个测试用例,输出一个整数—双端队列必须发生故障的最少次数。

如果无法得到目标双端队列,输出 −1-1。

样例

9
1 3
1 1 1
3 4
2 1 1 2
4 4
1 4 2 3
4 5
4 3 4 2 1
5 8
1 3 2 5 4 3 1 2
6 6
1 6 5 4 3 2
4 6
1 3 2 3 4 3
6 8
2 6 3 5 2 1 4 2
6 8
1 6 2 5 1 5 3 4
0
-1
2
0
1
4
0
2
3

说明

在第一个测试用例中,Vihaan 可以执行以下操作:

  1. 将第一个 11 推入前端:
[]→[1].[] \to [\color{red}{1}].

然后,立即将其弹出:

[1]→[].[1] \to [].
  1. 将第二个 11 推入前端:
[]→[1].[] \to [\color{red}{1}].

然后,立即将其弹出:

[1]→[].[1] \to [].
  1. 将最后一个 11 推入后端:
[]→[1].[] \to [\color{red}{1}].

因此,不需要任何故障操作。

在第二个测试用例中,值 33 从未在 bb 中出现,因此不可能得到目标双端队列。

在第三个测试用例中,Vihaan 可以执行以下操作:

  1. 将 11 推入后端:
[]→[1].[] \to [\color{red}{1}].
  1. 将 44 推入后端:
[1]→[1,4].[1] \to [1,\color{red}{4}].
  1. 让双端队列发生故障,并将 22 插入到 11 和 44 之间:
[1,4]→[1,2,4].[1,4] \to [1,\color{red}{2},4].
  1. 让双端队列发生故障,并将 33 插入到 22 和 44 之间:
[1,2,4]→[1,2,3,4].[1,2,4] \to [1,2,\color{red}{3},4].

可以证明,使用少于 2 次故障操作的任何操作序列都无法得到目标双端队列。因此,最小值为 2。

在第四个测试用例中,Vihaan 可以执行以下操作:

  1. 将第一次出现的 44 推入前端:
[]→[4].[] \to [\color{red}{4}].

然后,立即将其弹出:

[4]→[].[4] \to [].
  1. 将 33 推入后端:
[]→[3].[] \to [\color{red}{3}].
  1. 将第二次出现的 44 推入后端:
[3]→[3,4].[3] \to [3,\color{red}{4}].
  1. 将 22 推入前端:
[3,4]→[2,3,4].[3,4] \to [\color{red}{2},3,4].
  1. 将 11 推入前端:
[2,3,4]→[1,2,3,4].[2,3,4] \to [\color{red}{1},2,3,4].

因此,不需要任何故障操作。

来源

导入自 Codeforces — Codeforces Round 1122 (Div. 3)。