题目描述

一条防线上依次排列着 $n$ 座哨塔，编号为 $1,2,\dots,n$。第 $i$ 座哨塔的强度为 $i$。 每座哨塔属于以下两种类型之一。一个长度为 $n$ 的 01 字符串 $s$ 描述了所有哨塔的类型：

• 若 $s_i=0$，第 $i$ 座哨塔提供 $i$ 点进攻值；
• 若 $s_i=1$，第 $i$ 座哨塔提供 $i$ 点防守值。

选择一个整数 $pos\ (0\le pos \le n)$，把编号在 $[1,pos]$ 内的哨塔划入左区，其余哨塔划入右区。 记左区中所有 0 型哨塔的进攻值之和为 $w$，右区中所有 1 型哨塔的防守值之和为 $v$。

求所有划分方案中 $|w-v|$ 的最小值。

输入格式

第一行输入一个整数 $n$。 第二行输入一个长度为 $n$、仅由字符 0 和 1 组成的字符串。

输出格式

输出一个整数，表示 $|w-v|$ 的最小值。

样例输入 #1

7
1000101

样例输出 #1

2

样例1解释：取 $pos=5$ 时，左区的进攻值为 $2+3+4=9$，右区的防守值为 $7$，两者之差的绝对值为 $2$。

数据范围

• 对于20%的数据，$1 \le n \le 10$
• 对于40%的数据，$1 \le n \le 10^3$
• 对于全部数据，$1 \le n \le 10^{5}$

共10个测试点，每个测试点10分。