CF1861C Queries for the Array

Monocarp 有一个由整数构成的数组 $a$。最开始，这个数组是空的。 Monocarp 对这个数组执行了三种操作： - 选择一个整数，将其添加到数组末尾。每次执行这种操作时，Monocarp 会写下一个字符 $+$； - 移除数组的最后一个元素。每次执行这种操作时，Monocarp 会写下一个字符 $-$。Monocarp 从不会在空数组上执行此操作； - 检查数组是否为非递减排序，即 $a_1 \le a_2 \le \dots \le a_k$，其中 $k$ 是当前数组的元素个数。任何元素个数小于 $2$ 的数组都被认为是有序的。如果数组在执行该操作时是有序的，Monocarp 会写下字符 $1$，否则写下字符 $0$。 现在给定一个长度为 $q$ 的字符串 $s$，由 $0$、$1$、$+$ 和 $-$ 组成。这是 Monocarp 按顺序写下的字符序列。 你需要判断，这个序列是否是可能的，也就是说，Monocarp 是否有可能通过上述操作，写下恰好为 $s$ 的字符序列。

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例包含一行字符串 $s$（$1 \le |s| \le 2 \times 10^5$）。该字符串由 $0$、$1$、$+$ 和 $-$ 组成，表示 Monocarp 按顺序写下的字符序列。 输入还满足以下额外约束： - 对于 $s$ 的每一个前缀，字符 $+$ 的数量不少于字符 $-$ 的数量。换句话说，Monocarp 不会在空数组上执行移除操作； - 所有测试用例中 $|s|$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，如果存在一种操作方式使得 Monocarp 写下的字符序列恰好为 $s$，输出 YES，否则输出 NO。 你可以以任意大小写输出答案。

在第一个测试用例中，Monocarp 可以执行如下操作： - 添加整数 $13$； - 添加整数 $37$； - 检查当前数组 $[13, 37]$ 是否为非递减排序（确实有序）。 在第五个测试用例中，Monocarp 可以执行如下操作： - 添加整数 $3$； - 添加整数 $2$； - 检查当前数组 $[3, 2]$ 是否为有序（不是有序的）； - 移除最后一个元素； - 添加整数 $3$； - 检查当前数组 $[3, 3]$ 是否为有序（是有序的）； - 移除最后一个元素； - 添加整数 $-5$； - 检查当前数组 $[3, -5]$ 是否为有序（不是有序的）。 在示例测试的其他测试用例中，不可能通过上述操作写下 $s$。 由 ChatGPT 4.1 翻译