$\text{RT.}$

已知原本数据不存在输出 -1 的情况。

本题输出为 -1 的情况有三种：

• 前缀和数组中出现相同的数
• 前缀和数组中出现负数
• 前缀和数组中最后一位并非最大

接下来为这三种不能取的证明：

以下前缀和数组用 $s$ 代替

1：$s$ 中出现相同的数

根据这题的普遍做法，将原数组取前缀和后使其单调升才能使交换后的原序列全是正。

那么如果 $s$ 中出现相同的数，那么无论怎么交换都是不能做到使其单调升的。

数据：

3
1 -1 1

-1

2：$s$ 中出现负数

因为在结束时 $s$ 数组是单调升的，根据前缀和的定义：$s_1 = a_1$ 可以得出结束时 $a_1$ 的值。

那么如果 $s$ 中有负数的话，排序后的 $s_1$ 一定为负数，相对应的 $a_1$ 就是负数，不符合题意。

数据：

3
1 -2 1000

-1

3：$s_n \neq max (s)$

因为每次操作的 $l, r$ 的条件为 $1 < l \le r < n$。而前缀和交换时是交换 $s_{l-1}$ 和 $s_r$。

不难发现第 $n$ 个位置是无法被交换到的，那么如果最后一位不是最大，那么无法将其交换到相对应的位置。

数据：

4
1 3 -2 1

-1

以上。