AND PLUS OR

Time limit3sMemory limit1024 MB

Summary

Given an array of length 2^N, find indices i, j with A[i] + A[j] < A[i AND j] + A[i OR j], or report that none exist.

Level: Medium7 of 10
Topics: Bit manipulation, Divide and conquer, Array, Math
Solved: No attempts yet

Problem

For two nonnegative integers $a, b$ , let $a \wedge b$ denote their bitwise AND and $a \vee b$ their bitwise OR.

You are given an array $A_0, A_1, \ldots, A_{2^N - 1}$ of length $2^N$ consisting of nonnegative integers. Find a pair of indices $0 \le i, j \le 2^N - 1$ such that $A_{i} + A_{j} < A_{i \wedge j} + A_{i \vee j}$ , or state that no such pair exists. If more than one such pair exists, print any of them.

Input

The first line contains an integer $N$ .

The second line contains $2^N$ integers, the array $A$ given in order.

Output

If an answer exists, output two integers $i, j$ denoting the answer, separated by a space. $i, j$ must be in the range $[0, 2^N - 1]$ . Otherwise, output -1.

Constraints

$0 \leq N \leq 20$
$0 \leq A_i \leq 10^7$

Examples2

Example 1
Input
```
2
0 1 1 2
```
Expected output
```
-1
```
Example 2
Input
```
2
0 1 1 3
```
Expected output
```
1 2
```