AND PLUS OR

시간 제한3초메모리 제한1024 MB

요약

길이가 2^N인 배열에서 A[i] + A[j] < A[i AND j] + A[i OR j]를 만족하는 두 인덱스 i, j를 찾고, 없으면 -1을 출력한다.

난이도: 보통10점 중 7점
유형: 비트 연산, 분할 정복, 배열, 수학
정답자: 아직 제출이 없습니다

문제

음이 아닌 정수 $a, b$ 에 대해 $a \wedge b$ 는 비트 AND, $a \vee b$ 는 비트 OR을 나타낸다.

음이 아닌 정수로 이루어진 길이 $2^N$ 의 배열 $A_0, A_1, \ldots, A_{2^N - 1}$ 이 주어진다. $A_{i} + A_{j} < A_{i \wedge j} + A_{i \vee j}$ 를 만족하는 두 인덱스 $0 \le i, j \le 2^N - 1$ 의 쌍을 찾거나, 그러한 쌍이 존재하지 않음을 밝혀라. 그러한 쌍이 여러 개라면 아무거나 출력한다.

입력

첫째 줄에 정수 $N$ 이 주어진다.

둘째 줄에 $2^N$ 개의 정수, 즉 배열 $A$ 가 순서대로 주어진다.

출력

답이 존재하면 답을 나타내는 두 정수 $i, j$ 를 공백으로 구분해 출력한다. $i, j$ 는 $[0, 2^N - 1]$ 범위여야 한다. 그렇지 않으면 -1을 출력한다.

제한

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

예제2

예제 1
입력
```
2
0 1 1 2
```
예상 출력
```
-1
```
예제 2
입력
```
2
0 1 1 3
```
예상 출력
```
1 2
```