U296426 [NEERC 2022 H] Pines

[原题面](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-team-spb-2022-statements-english.pdf)

一条道路上有 $n+1$ 棵松树和 $n$ 个路灯，由松树开始一一交替排列，第 $i$ 棵松树高度为 $i$。路灯有 A 和 B 两类，每个路灯有其对应的种类。其中 B 类灯永远发白光，A 类则在其左侧树比右侧高时发红光，反之发蓝光。 现在需要你对 $n+1$ 棵松树进行重排列，使得发红光的灯数 $r$ 与发蓝光的灯数 $b$ 的差值（绝对值）尽可能小，即最小化 $|r-b|$。输出这个排列。

第一行一个整数 $n$。 第二行 $n$ 个字符，第 $i$ 个表示第 $i$ 盏灯的种类。

一行，$n+1$ 个整数，表示最终答案。 第 $i$ 个数 $x_i$ 表示在第 $i$ 盏灯前放上高度 $x_i$ 的树。

对于 $100\%$ 的数据，$1\le n\le 2\times 10^5$。