Máy trạng thái hai trạng thái (Two-State Toggle Machine)

Nguồn: Phước Hưng OJ

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

Đề bài

Máy có trạng thái 0 hoặc 1, ban đầu 0. Có n lệnh theo thứ tự: lệnh 0 giữ nguyên trạng thái, lệnh 1 đảo trạng thái. In trạng thái sau tất cả lệnh và số lần chuyển từ 0 sang 1 (không đếm chiều 1 sang 0). Khi n=0, cả hai kết quả đều là 0.

Input

Số nguyên n, sau đó đúng n lệnh nguyên 0 hoặc 1.

Output

In trang_thai dem_0_sang_1 cách nhau một dấu cách.

Subtask

• Subtask 1 (20%): 0 ≤ n ≤ 20.

• Subtask 2 (30%): 0 ≤ n ≤ 1000.

• Subtask 3 (50%): 0 ≤ n ≤ 100000.

Ví dụ

Ví dụ 1

Input:

5
1 0 1 1 1

Output:

0 2

Giải thích: Các trạng thái sau lệnh là 1,1,0,1,0; có hai lần 0→1.

Ví dụ 2

Input:

0

Output:

0 0

Giải thích: Không có lệnh.