A1646. 最佳还原
编程题
普及-
知识点
题目描述
给了一个 $n$ 个数的数组 $a$，你可以执行以下操作：
+ 选择 $l,r(1 \leq l \leq r \leq n)$，然后把 $a_l,a_{l+1},..,a_r$ 的值都减去 $1$。
定义 $f(a)$ 为把数组 $a$ 全部变为 $0$ 时的最小操作次数。
你需要告诉我对于任意的一个 $a$ 的排列 $b$，都有$f(a) \leq f(b)$ 是否成立。
+ 选择 $l,r(1 \leq l \leq r \leq n)$，然后把 $a_l,a_{l+1},..,a_r$ 的值都减去 $1$。
定义 $f(a)$ 为把数组 $a$ 全部变为 $0$ 时的最小操作次数。
你需要告诉我对于任意的一个 $a$ 的排列 $b$，都有$f(a) \leq f(b)$ 是否成立。
输入格式
第一行一个整数 $n(1 \leq n \leq 1e5)$。
接下来 $n$ 整数 $a_1,a_2,...,a_n(1 \leq a_i \leq 1e9)$。
接下来 $n$ 整数 $a_1,a_2,...,a_n(1 \leq a_i \leq 1e9)$。
输出格式
如果成立输出 $"YES"$,否则输出 $"NO"$。
输入输出样例
输入 #1
4 2 3 5 4
输出 #1
YES
输入 #2
3 1 2 3
输出 #2
YES
输入 #3
4 3 1 3 2
输出 #3
NO