题目描述

小明的牧场外面围着一排栅栏，一共 $n$ 块木板，从左到右编号为 $1 \sim n$。第 $i$ 块木板的状态用 $a_i$ 表示：

• $a_i = 0$：这块木板破损了；
• $a_i = 1$：这块木板完好。

昨天夜里狼来过，栅栏上留下了几处破损。小明决定去买补丁来修补。

商店里卖的补丁按长度计价：一块长度为 $L$ 的补丁可以一次性盖住连续的 $L$ 块木板，售价为 $\lfloor \sqrt{L} \rfloor$ 元。

• 补丁允许盖在已经完好的木板上，多盖不加钱；
• 补丁必须完整地落在栅栏内：若一块长度为 $L$ 的补丁盖住区间 $[l,\ l + L - 1]$，则必须满足 $1 \le l$ 且 $l + L - 1 \le n$。

小明希望花的钱最少，使每一块破损的木板都至少被某一块补丁盖住。请你求出最小总花费。

输入格式

从文件 sheep.in 读入数据。 第一行一个整数 $n$，表示木板数量。

第二行一个长度为 $n$ 的字符串 $s$，仅由字符 0 和 1 组成，其中第 $i$ 个字符即为 $a_i$。

输出格式

输出到文件 sheep.out。 输出一行一个整数，表示最小总花费。

样例1&2

7
1011101

2

10
1010101010

3

解释

在第一组数据中，破损的木板是第 $2$ 块和第 $6$ 块。用一块长度为 $5$ 的补丁盖住区间 $[2, 6]$，花费 $\lfloor \sqrt{5} \rfloor = 2$ 元；也可以用两块长度为 $1$ 的补丁分别盖 $[2,2]$ 和 $[6,6]$，花费 $1 + 1 = 2$ 元。最小花费为 $2$。

在第二组数据中，破损的木板是第 $2, 4, 6, 8, 10$ 块。一块长度为 $9$ 的补丁盖住 $[2, 10]$，花费 $\lfloor \sqrt{9} \rfloor = 3$ 元。逐块单独盖需要 $5$ 元，所以最小花费为 $3$。

样例 3-7

见下发文件。

数据规模与约定

下发文件分别对应子任务 $1,2,3,4,5$。

对于 $100\%$ 的数据：保证 $1 \leq n \leq 10^{7},s_i \in \{0,1\}$。