Thêm vào đầu và cuối (Prepend and Append)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Ban đầu, Timur có một chuỗi nhị phân $s$. Chuỗi ban đầu có thể rỗng.

Sau đó, Timur thực hiện thao tác sau một số lần tùy ý, có thể bằng $0$.

Trong mỗi thao tác, Timur:

• thêm ký tự 0 vào một đầu của chuỗi;
• đồng thời thêm ký tự 1 vào đầu còn lại.

Nói cách khác, trong mỗi thao tác, Timur có thể thực hiện một trong hai cách:

• thêm 0 vào đầu trái và 1 vào đầu phải;
• thêm 1 vào đầu trái và 0 vào đầu phải.

Vì vậy, hai ký tự được thêm vào trong cùng một thao tác luôn khác nhau.

Ví dụ, từ chuỗi:

1011

sau một thao tác có thể thu được:

010111

hoặc:

110110.

Bạn được cho chuỗi cuối cùng mà Timur thu được.

Hãy xác định độ dài nhỏ nhất có thể của chuỗi ban đầu trước khi Timur thực hiện các thao tác.

Chuỗi nhị phân là một chuỗi, có thể rỗng, trong đó mỗi ký tự là 0 hoặc 1.

Input

Dòng đầu tiên chứa số nguyên $n$ — độ dài của chuỗi cuối cùng.

Dòng thứ hai chứa chuỗi nhị phân $s$ gồm đúng $n$ ký tự.

Output

In ra một số nguyên không âm — độ dài nhỏ nhất có thể của chuỗi ban đầu của Timur.

Nếu chuỗi ban đầu có thể là chuỗi rỗng, in ra $0$.

Subtask

• Subtask 1 — 30% — Time Limit: 1.00 s: $1 \le n \le 2000$; $s$ là chuỗi nhị phân có độ dài $n$.
• Subtask 2 — 70% — Time Limit: 1.00 s: $1 \le n \le 2\cdot10^5$; $s$ là chuỗi nhị phân có độ dài $n$.

Ví dụ

Ví dụ 1

Input

3
100

Output

1

Giải thích

Chuỗi cuối cùng là 100.

Timur có thể bắt đầu với chuỗi:

0

sau đó thêm 1 vào đầu trái và 0 vào đầu phải:

0 $\rightarrow$ 100.

Vì vậy, chuỗi ban đầu có thể có độ dài $1$.

Không thể có chuỗi ban đầu ngắn hơn, nên đáp án là $1$.

Ví dụ 2

Input

4
0111

Output

2

Giải thích

Chuỗi ban đầu có thể là:

11.

Timur thêm 0 vào đầu trái và 1 vào đầu phải:

11 $\rightarrow$ 0111.

Do đó độ dài nhỏ nhất có thể của chuỗi ban đầu là $2$.

Ví dụ 3

Input

5
10101

Output

5

Giải thích

Chuỗi cuối cùng là 10101.

Hai ký tự ngoài cùng đều là 1.

Trong một thao tác, hai ký tự mới được thêm vào hai đầu bắt buộc phải là một 0 và một 1. Vì vậy, hai ký tự 1 ở hai đầu không thể đồng thời là hai ký tự được thêm vào trong thao tác cuối cùng.

Do đó không thể loại bỏ một thao tác nào khỏi quá trình tạo chuỗi.

Timur có thể đã bắt đầu trực tiếp với chuỗi 10101 và thực hiện $0$ thao tác.

Vì vậy đáp án là $5$.

Ví dụ 4

Input

6
101010

Output

0

Giải thích

Chuỗi 101010 có thể được tạo từ chuỗi rỗng.

Một quá trình hợp lệ là:

chuỗi rỗng $\rightarrow$ 10 $\rightarrow$ 0101 $\rightarrow$ 101010.

Ở mỗi bước, một 0 và một 1 được thêm vào hai đầu của chuỗi.

Vì chuỗi ban đầu có thể rỗng nên độ dài nhỏ nhất là $0$.

Ví dụ 5

Input

7
1010110

Output

3

Giải thích

Xét ngược quá trình tạo chuỗi.

Chuỗi:

1010110

có hai ký tự ngoài cùng là 1 và 0, nên chúng có thể là hai ký tự được thêm vào trong cùng một thao tác. Bỏ hai ký tự này, ta còn:

01011.

Hai ký tự ngoài cùng của 01011 là 0 và 1, nên tiếp tục có thể loại bỏ chúng, còn lại:

101.

Lúc này hai ký tự ngoài cùng của 101 đều là 1.

Hai ký tự giống nhau không thể là cặp ký tự được thêm vào trong cùng một thao tác.

Do đó không thể tiếp tục rút ngắn chuỗi.

Chuỗi ban đầu ngắn nhất có thể là 101, có độ dài $3$.

Vì vậy đáp án là $3$.