题解思路

目标与操作

我们要使最终数组 没有任何元素落在区间 $[l,r]$ 内；允许四种操作：对任意一个元素 $\pm 1$，或从两端删除一个元素；数组必须保持非空。

关键转化

只能从两端删除 ⇒ 保留的部分必是一个非空连续子数组 $[i..j]$。

题目内容

给定一个长度为 $n$ 的整数数组 {$a_1,a_2,...,a_n$}。Tk 想通过若干次操作，使得最终数组 中不存在任何落在区间 $[l,r]$ 内的元素 。操作结束后，数组必须为非空。每次操作只能在以下四种中任选一种：

选择当前数组中的个某个元素 $a_i$ ，将其数值减 $1$ ；

选择当前数组中的个某个元素 $a_i$ ，将其数值加 $1$ ；

删除当前数组最左端的元素；

删除当前数组最右端的元素。

请计算并输出，使数组不再包含区间 $[l,r]$ 内元素所需的 最少操作次数 。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≦T≦10^4)$ 代表数据组数，每组测试数据描述如下：

第一行输入三个整数 $n,l,r(1≦l≦r≦n≤2×10^5)$ 表示数组长度以及区间端点。

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1 ≦ a_i≦ n)$ 表示数组元素。

除此之外，保证单个测试文件中 $n$ 的总和不超过 $2×10^5$ 。

输出描述

对于每一组测试数据，新起一行，输出一个整数，代表最少操作次数。

样例1

输入

2
1 1 1
1
5 2 4
3 1 1 5 3

输出

1
2

说明

在一组样例中，数组仅有一个元素 $1$ ，它位于区间 $[1,1]$ 内。通过一次“将该元素减 $1$ "操作，可将其变为 $0$ ，满足条件，答案为 $1$ 。

在第二组样例中，原数组为 {$3,1,1,5,3$} ，区间为 $[2,4]$ 。可以先删除最左端元素 $3$ (操作 $3$ )，再删除最右端元素 $3$ (操作 $4$ )，得到 {$1,1,5$} ，其中所有元素均不在 $[2,4]$ 内，共需 $2$ 次操作。