O(N)

首先检查数组 $a$ 是否已经满足条件。如果是那么答案显然为 $0$ 。否则这意味着所有的 $i$ 都是 $|a_i−a_{i+1}|≥2$ 。

接下来，假设数组是非递减序列，无论选择哪个区间合并都无法得到最美丽的数组。

即对任意的 $1 \leq l < r \leq n$, 合并 $a_l, a_{l + 1} ... a_r$, 新数字 $x$ 的取值为 $[a_l, a_r]$ ,数组变为 $a_1, ... , a_{l - 1}, x, a_{r + 1}, ..., a_n$ 。此时数组对任意的 i 都是 $a_{i+1}−a_{i}≥2$ ，无法使数组变的优美。 对非递增序列同理。

结论：只要存在极点则一定可以通过一次操作使数组变得美丽

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<LL, LL> PII;

#define x first
#define y second

const int N = 5e3 + 10, mod = 1e9 + 7;

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i = 0; i < n; i ++) cin >> a[i];
    
    int ans = n;
    for(int i = 1; i < n; i ++)
    {
        if(abs(a[i] - a[i - 1]) <= 1) ans = 0;
        if(i > 1 && (a[i] > a[i - 1] && a[i - 1] < a[i - 2] || a[i] < a[i - 1] && a[i - 1] > a[i - 2]))
            ans = min(ans, 1);
    }
    cout << (ans == n ? -1 : ans) << endl;
}

int main()
{
    int t = 1;
    scanf("%d", &t);
    while(t --)
        solve();
}