SSHS 프로토콜

SSHS 프로토콜은 0과 1로만 이루어진 짝수 길이의 데이터를 전송할 수 있는 프로토콜이다. SSHS 프로토콜로 데이터를 전송하면 다음 방식으로 비용이 청구된다.

• 전송할 데이터를 0과 1로 이루어진 길이 $2k$의 수열 $T$라고 하자. (단, $k \ge 1$)
• 청구 비용은 $\left( \sum_{i=1}^{k} T_i 2^{k-i} \right) \times \left( \sum_{i=k+1}^{2k} T_i 2^{2k-i} \right)$이다.
• 즉, $T$를 절반으로 나눈 뒤 각 부분을 이진법 수로 보았을 때, 두 값의 곱만큼 비용이 청구된다.

데이터가 길수록 비용이 기하급수적으로 늘어난다. 그래서 데이터를 나눠서 보내는 경우가 많다. 데이터를 나눠 보내면 전체 비용은 나뉜 조각들의 비용의 합이다. 길이 $N$의 데이터 $S$가 주어졌을 때, 전체 비용의 최솟값을 구하여라.

정확한 정의는 다음과 같다.

• 데이터 $T$의 청구 비용을 $f(T)$라고 정의한다.
• 0과 1로 이루어진 길이 $N$의 데이터 $S$가 주어진다. (단, $N$은 짝수)
• $1 = i_0 < i_1 < i_2 < \cdots < i_p < i_{p+1} = N+1$을 만족하고, 모든 정수 $j$ ($0 \le j \le p$)에 대해 $i_{j+1}-i_j$가 짝수가 되도록 정수 $i_1, i_2, \cdots, i_p$를 고른다. (단, $p$는 0 이상의 정수)
• 이때 전체 비용은 $g(\{ i_1, i_2, \cdots, i_p \}) = \sum_{j=0}^{p} f(S_{i_j : (i_{j+1}-1)})$이다. ($s_{l : r}$은 $s$의 부분수열 $(s_l, s_{l+1}, \cdots, s_r)$을 뜻한다.)
• 전체 비용 $g$의 최솟값을 구하여라.

데이터를 나누지 않고 그대로 보내는 것도 가능하다. 즉, $g(\emptyset)=f(S)$의 비용으로 $S$를 전송할 수 있다.

첫 번째 줄에 데이터의 길이 $N$이 주어진다.

두 번째 줄에 0과 1로 이루어진 길이 $N$의 데이터 $S$가 공백 없이 주어진다.

$S$를 보낼 때 전체 비용의 최솟값을 출력한다.

• $2 \le N \le 2 \times 10^5$
• $N$은 짝수