Two-State Toggle Machine

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

A machine starts in state 0. Command 0 leaves the state intact; command 1 toggles it. Print final state and number of transitions specifically from 0 to 1.

Input

Integer n followed by n commands from {0,1}.

Output

Print final_state transitions_0_to_1.

Subtasks

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

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

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

Examples

Example 1

Input:

5
1 0 1 1 1

Output:

0 2

Explanation: State sequence is 1,1,0,1,0; exactly two 0-to-1 transitions.

Example 2

Input:

0

Output:

0 0

Explanation: There are no state transitions.