题解：CF2155C The Ancient Wizards' Capes

此题解由 codeforces 官方题解翻译而来。

关键性质

假设哈利的列表至少对应一种斗篷安排。主要结论是：列表中任意两个连续值的差最多为 1。

当哈利从位置

i

走到位置

i + 1

时，巫师

1

到

i - 1

以及

i + 2

到

n

的可见性不受影响。对于巫师

i

和

i + 1

，存在四种可能情况：

情况	巫师 $i$	巫师 $i+1$	$a_{i + 1} - a_i$	说明
1	左侧	左侧	$+1$	巫师 $i+1$ 变得可见，巫师 $i$ 仍然可见
2	右侧	右侧	$-1$	巫师 $i+1$ 保持可见，巫师 $i$ 变得不可见
3	左侧	右侧	$0$	两个巫师都保持可见
4	右侧	左侧	$0$	巫师 $i+1$ 变得可见，巫师 $i$ 变得不可见

这决定了整个斗篷安排的一种唯一可能性（可能无效），该可能性仅基于巫师

1

披斗篷的方式，前提是对于所有

1 \leq i < n

，满足

|a_{i+1} - a_i| < 2

。

因此，巫师斗篷的安排最多有两种可能。我们可以构建这两种安排，并检查它们是否与哈利的列表一致。

O(n)

只需要扫两遍数组即可。

注：本文由 deepseek 直接翻译，作者修改格式并检查错误。