Winning Strategy in Divisor-Multiple Game

In this game, there are N cards, each containing an integer. Two players take turns picking one card. The rule is that the number on the card chosen by the next player must be either a divisor or a multiple of the number on the card chosen by the previous player. In other words, if the previous card has number \(a\), then the next card’s number \(b\) must satisfy

[ a \mid b \quad\text{or}\quad b \mid a ]

If a player cannot pick any card meeting this condition when it is their turn, that player loses. Your task is to determine the digit to choose first (i.e. the starting move) that guarantees a win assuming both players play optimally. If there are several winning moves, output the smallest such number. If no winning move exists, output \(-1\).

inputFormat

The first line contains an integer \(N\) representing the number of cards. The second line contains \(N\) space-separated integers representing the numbers on the cards.

outputFormat

Output a single integer: the card number to choose first that guarantees a win, or \(-1\) if no winning move exists.

sample

3
2 3 6

2