#P18879. [2026多校联测]中庸数

[2026多校联测]中庸数

中庸数

题目背景

仙尊发现在三个数字中,第二大的数吸收了天地混元之气,而另外两个数字为灵珠和魔丸。

题目描述

仙尊给你一个长度为 nn 的序列 aa,然后进行 qq 次询问,每次给出一个目标数字 kk,你需要进行如下操作若干次,使得序列 aa 的 nn 个元素都为 kk。

  • 选择三个连续数字 ai−1,ai,ai+1,i∈[2,n−1]a_{i-1},a_i,a_{i+1},i\in[2,n-1],满足其中至少有一个数字为 kk。
  • 修改 $a_{i-1}=a_i=a_{i+1}=\text{median}(a_{i-1},a_i,a_{i+1})$。

其中 median(a,b,c)\text{median}(a,b,c) 表示 a,b,ca,b,c 三个数字的中位数。

输入格式

第一行一个整数 TT,为数据组数。

对于每组数据:

第一行两个正整数 n,qn, q,表示序列长度和询问次数。

第二行 nn 个正整数 a1,a2,⋯ ,ana_1, a_2, \cdots, a_n 。

接下来 qq 行,每行一个整数 kk,表示一次询问,询问目标数字为 kk。

输出格式

对于每组数据中的每次询问,输出一行一个整数,表示将所有数字都变为 kk 所需要使用的最少操作次数。

如果无论如何都无法将所有数都变为 kk,输出 -1。

输入输出样例 #1

2
6 2
1 10 1 10 5 4
4
1
8 2
10 10 7 4 6 10 8 7
10
6
-1
4
5
6

说明/提示

数据规模与约定

测试点编号 n,q≤n,q \leq ∑n,∑q≤\sum n,\sum q \leq 特殊性质
11 1010 1×1031 \times 10^{3} 无
2∼52\sim 5 200200 2×1032 \times 10^{3}
6,76,7 20002000 2×1042 \times 10^{4} A\text{A}
8,98,9 2×1042\times10^4 B\text{B}
10∼1210\sim 12 无
13∼1513 \sim 15 2×1052 \times 10^{5} 10610^{6} A\text{A}
16∼2016\sim 20 2×1052\times10^5 10610^6 B\text{B}
21∼2521\sim 25 无

特殊性质 A\text{A}:q≤10q\leq 10。

特殊性质 B\text{B}:初始 aa 序列中所有数字都互不相同。

对于所有测试点保证 $3 \leq n \leq 2 \times 10^5, 1 \leq q \leq 2 \times 10^5,\sum n \leq 10^6, \sum q \leq 10^6,1 \leq a_i \leq 2 \times 10^5,1\leq k \leq 2\times 10^5$。