Question B

question.txt

Deskripsi
Masyarakat Indonesia terkenal akan kegabutannya. Sehingga tidak jarang kita melihat hal-hal aneh disekitar kita. Mulai dari kalangan anak muda maupun kalangan lansia kegabutannya hakiki.

Suatu saat, seorang warga dengan gabutnya mengumpulkan N buah bilangan bulat positif hingga menjadi suatu array A. Temannya yang sama gabutnya menanyakan Q buah pertanyaan kepada warga tersebut. Setiap pertanyaan berisi 2 buah bilangan bulat L dan R. Pertanyaannya adalah: "Carilah nilai dari suatu pasang bilangan dengan indeks yang berbeda yang menghasilkan nilai minimum untuk persamaan:

(bilangan1 | bilangan2) - (bilangan1 & bilangan2)

diantara bilangan dari indeks ke-L hingga indeks ke-R inklusif, jika tidak terdapat suatu pasangan bilangan yang memenuhi, keluarkan -1" 

Karena anda juga gabut. Maka anda setuju untuk membuatkan program terkait deskripsi diatas.

*Note : "|" adalah operasi bitwise or dan "&" adalah operasi bitwise and.

Format Masukan
Baris pertama berisi sebuah bilangan bulat N yang menyatakan banyaknya bilangan pada array A yang terdapat di deskripsi.

Baris selanjutnya berisi N buah bilangan bulat yang dipisahkan oleh spasi yang menyatakan elemen array A.

Baris selanjutnya berisi sebuah bilangan bulat Q yang menyatakan banyaknya pertanyaan.

Q baris berikutnya berisi 2 buah bilangan bulat L dan R secara berturut-turut sesuai deskripsi.

Format Keluaran
Q baris bilangan bulat sesuai jawaban pada deskripsi.

Contoh Masukan
3
5 1 3
3
1 2
2 3
1 3
Contoh Keluaran
4
2
2
Subsoal
Untuk setiap subsoal berlaku 1 ≤ Ai ≤ 109, 1 ≤ L ≤ R ≤ N

Subsoal 1 (10 Poin)
1 ≤ N ≤ 100, 1 ≤ Q ≤ 1000
Subsoal 2 (20 Poin)
1 ≤ N ≤ 300, 1 ≤ Q ≤ 30000
Subsoal 3 (30 Poin)
1 ≤ N ≤ 300, 1 ≤ Q ≤ 100000
Subsoal 4 (40 Poin)
1 ≤ N ≤ 2000, 1 ≤ Q ≤ 100000