Optimal Reduction

题意翻译

给定一个正整数 $n$ 以及一个长度为 $n$ 的数组 $a$。 你可以对数组 $a$ 进行以下操作： - 选两个数 $l$，$r$（$1\le l\le r\le n$），然后令 $a_l,a_{l+1},\dots,a_r$ 全部 $-1$。 设 $f(a)$ 为将 $a$ 中所有元素变为 $0$ 所需的最少操作。 判断是否对于 $a$ 的所有排列 $b$，保证 $f(a)\le f(b)$。

题目描述

Consider an array $ a $ of $ n $ positive integers. You may perform the following operation: - select two indices $ l $ and $ r $ ( $ 1 \leq l \leq r \leq n $ ), then - decrease all elements $ a_l, a_{l + 1}, \dots, a_r $ by $ 1 $ . Let's call $ f(a) $ the minimum number of operations needed to change array $ a $ into an array of $ n $ zeros. Determine if for all permutations $ ^\dagger $ $ b $ of $ a $ , $ f(a) \leq f(b) $ is true. $ ^\dagger $ An array $ b $ is a permutation of an array $ a $ if $ b $ consists of the elements of $ a $ in arbitrary order. For example, $ [4,2,3,4] $ is a permutation of $ [3,2,4,4] $ while $ [1,2,2] $ is not a permutation of $ [1,2,3] $ .

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. The first line of each test case contains a single integer $ n $ ( $ 1 \leq n \leq 10^5 $ ) — the length of the array $ a $ . The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — description of the array $ a $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

输出格式

For each test case, print "YES" (without quotes) if for all permutations $ b $ of $ a $ , $ f(a) \leq f(b) $ is true, and "NO" (without quotes) otherwise. You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).

输入输出样例

输入样例 #1

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

输出样例 #1

YES
YES
NO

说明

In the first test case, we can change all elements to $ 0 $ in $ 5 $ operations. It can be shown that no permutation of $ [2, 3, 5, 4] $ requires less than $ 5 $ operations to change all elements to $ 0 $ . In the third test case, we need $ 5 $ operations to change all elements to $ 0 $ , while $ [2, 3, 3, 1] $ only needs $ 3 $ operations.

**最优减少**

**题意翻译**
给定一个正整数 $n$ 以及一个长度为 $n$ 的数组 $a$。你可以对数组 $a$ 进行以下操作：

- 选两个数 $l$、$r$（$1 \le l \le r \le n$），然后令 $a_l, a_{l+1}, \dots, a_r$ 全部减1。

设 $f(a)$ 为将 $a$ 中所有元素变为 $0$ 所需的最少操作。

判断是否对于 $a$ 的所有排列 $b$，保证 $f(a) \le f(b)$。

**题目描述**
考虑一个包含 $n$ 个正整数的数组 $a$。

你可以执行以下操作：

- 选择两个索引 $l$ 和 $r$（$1 \leq l \leq r \leq n$），然后
- 将所有元素 $a_l, a_{l+1}, \dots, a_r$ 减1。

称 $f(a)$ 为将数组 $a$ 变为 $n$ 个0的最少操作数。

判断是否对于 $a$ 的所有排列 $b$，$f(a) \leq f(b)$ 始终成立。

**输入输出格式**

**输入格式**
第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）——测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）——数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）——数组 $a$ 的描述。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

**输出格式**
对于每个测试用例，如果对于所有 $a$ 的排列 $b$，$f(a) \leq f(b)$ 成立，则打印 "YES"（不带引号），否则打印 "NO"（不带引号）。

你可以以任何大小写组合输出 "YES" 和 "NO"（例如，"yEs"、"yes" 和 "Yes" 都会被认为是肯定的响应）。

**输入输出样例**

**输入样例 #1**
```
3
4
2 3 5 4
3
1 2 3
4
3 1 3 2
```

**输出样例 #1**
```
YES
YES
NO
```

**说明**
在第一个测试用例中，我们可以用5次操作将所有元素变为0。可以证明，没有任何 $[2, 3, 5, 4]$ 的排列需要少于5次操作来将所有元素变为0。

在第三个测试用例中，我们需要5次操作将所有元素变为0，而 $[2, 3, 3, 1]$ 只需要3次操作。**最优减少** **题意翻译** 给定一个正整数 $n$ 以及一个长度为 $n$ 的数组 $a$。你可以对数组 $a$ 进行以下操作： - 选两个数 $l$、$r$（$1 \le l \le r \le n$），然后令 $a_l, a_{l+1}, \dots, a_r$ 全部减1。 设 $f(a)$ 为将 $a$ 中所有元素变为 $0$ 所需的最少操作。 判断是否对于 $a$ 的所有排列 $b$，保证 $f(a) \le f(b)$。 **题目描述** 考虑一个包含 $n$ 个正整数的数组 $a$。 你可以执行以下操作： - 选择两个索引 $l$ 和 $r$（$1 \leq l \leq r \leq n$），然后 - 将所有元素 $a_l, a_{l+1}, \dots, a_r$ 减1。 称 $f(a)$ 为将数组 $a$ 变为 $n$ 个0的最少操作数。 判断是否对于 $a$ 的所有排列 $b$，$f(a) \leq f(b)$ 始终成立。 **输入输出格式** **输入格式** 第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）——测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）——数组 $a$ 的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）——数组 $a$ 的描述。 保证所有测试用例的 $n$ 之和不超过 $10^5$。 **输出格式** 对于每个测试用例，如果对于所有 $a$ 的排列 $b$，$f(a) \leq f(b)$ 成立，则打印 "YES"（不带引号），否则打印 "NO"（不带引号）。 你可以以任何大小写组合输出 "YES" 和 "NO"（例如，"yEs"、"yes" 和 "Yes" 都会被认为是肯定的响应）。 **输入输出样例** **输入样例 #1** ``` 3 4 2 3 5 4 3 1 2 3 4 3 1 3 2 ``` **输出样例 #1** ``` YES YES NO ``` **说明** 在第一个测试用例中，我们可以用5次操作将所有元素变为0。可以证明，没有任何 $[2, 3, 5, 4]$ 的排列需要少于5次操作来将所有元素变为0。 在第三个测试用例中，我们需要5次操作将所有元素变为0，而 $[2, 3, 3, 1]$ 只需要3次操作。