Doctor Strange and the Swap

Interview

Time limit2sMemory limit1024 MB

Summary

Find two positions whose swap puts even numbers on even positions and odd numbers on odd positions, or report -1 -1 if no swap works.

Level: Easy2 of 10
Topics: Implementation, Brute force, Array
Solved: No attempts yet

Problem

Doctor Strange has a garden where $n$ flower pots are lined up in a row. Each pot has a number written on it. The pot at position $i$ has the number $a_i$ , so the pots form an array $a$ .

On the weekend, Doctor Strange swaps the pots at two different positions $i$ and $j$ ( $i \neq j$ ). He likes patterns, so he wants even positions to hold even numbers and odd positions to hold odd numbers after the swap.

Determine whether exactly one swap of two elements at different positions can turn $a$ into an array that satisfies this condition.

Input

The first line contains a natural number $n$ ( $2 \le n \le 1000$ ). The next line contains $n$ natural numbers $a_i$ ( $1 \le a_i \le 10^9$ ), the numbers written on the pots.

Output

Print $i$ and $j$ , the positions of the two elements to swap, so that the condition holds. If there are several answers, print any of them. If no swap achieves this, print -1 -1.

Examples3

Example 1
Input
```
2
2 1
```
Expected output
```
1 2
```
Example 2
Input
```
3
1 2 3
```
Expected output
```
1 3
```
Example 3
Input
```
4
2 1 4 6
```
Expected output
```
-1 -1
```