TheJobOverflow | Sorted Binary Array |

Sorted Binary Array :

Author

admin

Difficulty Level : Easy

Submissions : 354

Asked In :

Marks :10

: 4 | : 0

You are given a sorted (in ascending order) binary array (consisting only of 0's and 1's). Print the index(0-based) of the first 1 and last 0 in the array. If no 0's exist, print -1 instead of the index of the last 0. If no 1's exist, print N instead of the index of the first 1.

Only attempt to solve this in logN complexity.

Input

The first line of input contains N - the size of the array. The second line of input contains N integers - that can be either 0 or 1. The N integers are guaranteed to be sorted in ascending order.

1 <= N <= 100000

Output

The output should consist of two space separated integers in a line. First integer should be 0-based index of first 1 in the array. If no 1's exist, print N instead of the index of the first 1. Second integer should be 0-based index of last 0 in the array. If no 0's exist, print -1 instead of the index of the last 0.

Examples

Input

5
0 0 0 1 1

Output

3 2

Input

5
0 0 0 0 0

Output

5 4

Input

5
1 1 1 1 1

Output

0 -1

Input

5
0 1 1 1 1

Output

1 0

Input

5
0 0 0 0 1

Output

4 3

Input

5
0 0 1 1 1

Output

2 1

Input

4
0 0 0 0

Output

4 3

Input

4
0 0 0 1

Output

3 2

Input

4
0 0 1 1

Output

2 1

Input

4
0 1 1 1

Output

1 0

Input

4
1 1 1 1

Output

0 -1

Input

1
1

Output

0 -1

Input

1
0

Output

1 0

You need to login to view your submissions.

You need to login to view all submissions.

Language

Result : Executed

Result : Accepted

Test Cases :