[ABC346] D - Gomamayo Sequence

D - Gomamayo Sequence

Time Limit: 2 sec / Memory Limit: 1024 MB

题面

给定一个长度为 的仅由 0 和 1 组成的字符串 。

一个长度为 且仅由 0 和 1 组成的字符串 被称为好字符串，当且仅当满足以下条件：

• 存在唯一整数 ，使得 ，并且 的第 和第 个字符相同。

对于每个 ，你可以选择是否执行以下操作：

• 如果 的第 个字符是 0，则将其替换为 1，反之亦然。如果执行此操作，其成本为 。

找到使得 成为好字符串所需的最小总成本。

限制条件

• 是一个长度为 且仅由 0 和 1 组成的字符串。
• 和 为整数。

---

输入

输入数据从标准输入中读取，格式如下：

输出

输出答案。

---

输入样例 1

5
00011
3 9 2 6 4

输出样例 1

7

在 处执行操作，在 处不执行操作，使得 10010，这是一个好字符串。此时产生的成本为 ，且无法以少于 的成本使 成为好字符串，因此输出 。

---

输入样例 2

4
1001
1 2 3 4

输出样例 2

0

---

输入样例 3

11
11111100111
512298012 821282085 543342199 868532399 690830957 973970164 928915367 954764623 923012648 540375785 925723427

输出样例 3

2286846953