Phân loại dữ liệu (Data Classification)

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

Đề bài

Một hệ thống lưu trữ $N$ bản ghi theo thứ tự thời gian. Mỗi bản ghi được gán một nhãn là $0$ hoặc $1$.

Người quản trị cần chọn một vị trí phân cách $k$, với $0 \le k \le N$, để chia các bản ghi thành hai nhóm:

• các bản ghi có chỉ số từ $1$ đến $k$ được xếp vào nhóm $0$;
• các bản ghi có chỉ số từ $k+1$ đến $N$ được xếp vào nhóm $1$.

Một bản ghi được xem là phân loại sai nếu nhãn hiện tại của nó khác với nhóm mà nó được xếp vào.

Nói cách khác:

• trong đoạn từ $1$ đến $k$, mọi bản ghi mang nhãn $1$ đều phải đổi nhãn;
• trong đoạn từ $k+1$ đến $N$, mọi bản ghi mang nhãn $0$ đều phải đổi nhãn.

Hãy tìm số bản ghi cần đổi nhãn ít nhất.

Nếu có nhiều vị trí $k$ cho cùng số lần đổi nhãn nhỏ nhất, hãy chọn giá trị $k$ nhỏ nhất.

Input

Dòng đầu tiên chứa số nguyên dương $N$ — số lượng bản ghi.

Dòng thứ hai chứa xâu $S$ gồm đúng $N$ ký tự, không chứa dấu cách. Với mọi $1 \le i \le N$, ký tự $S_i$ thuộc tập $\{0,1\}$ và biểu diễn nhãn hiện tại của bản ghi thứ $i$.

Output

In ra hai số nguyên $E$ và $K$, cách nhau bởi một dấu cách, trong đó:

• $E$ là số bản ghi cần đổi nhãn ít nhất;
• $K$ là vị trí phân cách nhỏ nhất đạt được giá trị $E$.

Quy ước:

• $K=0$ nghĩa là nhóm $0$ rỗng và tất cả bản ghi được xếp vào nhóm $1$;
• $K=N$ nghĩa là nhóm $1$ rỗng và tất cả bản ghi được xếp vào nhóm $0$.

Subtask

• Subtask 1 — 30%: $1 \le N \le 2000$.
• Subtask 2 — 70%: $1 \le N \le 2\cdot10^5$.

Ví dụ

Ví dụ 1

Input

8
00110111

Output

1 2

Giải thích

Chọn $k=2$.

Hai bản ghi đầu tiên có nhãn 0, nên đều phù hợp với nhóm $0$.

Các bản ghi từ vị trí $3$ đến $8$ có nhãn:

110111

Trong đoạn này chỉ có bản ghi tại vị trí $5$ mang nhãn 0, trong khi nó được xếp vào nhóm $1$.

Vì vậy chỉ cần đổi đúng $1$ nhãn.

Không tồn tại vị trí phân cách nhỏ hơn $2$ cũng đạt được $1$ lần đổi nhãn, nên kết quả là $E=1$ và $K=2$.

Ví dụ 2

Input

4
1111

Output

0 0

Giải thích

Chọn $k=0$, khi đó nhóm $0$ rỗng và cả $4$ bản ghi đều được xếp vào nhóm $1$.

Tất cả bản ghi đều đã mang nhãn 1, vì vậy không cần đổi bất kỳ nhãn nào.

Do đó $E=0$ và $K=0$.