Maximum Non-Adjacent Product

You are given an array of n integers. Your task is to find the maximum product of two distinct elements such that they are non-adjacent (i.e. they do not appear consecutively in the array).

Formally, if the array is \( a_0, a_1, \dots, a_{n-1} \), you need to choose two indices \( i \) and \( j \) with \( j \ge i+2 \) and maximize \( a_i \times a_j \).

If there is no valid pair, you can assume that the input will always have at least 3 elements.

inputFormat

The first line contains an integer n denoting the number of elements in the array.

The second line contains n space-separated integers representing the array.

outputFormat

Output a single integer which is the maximum product of two distinct non-adjacent elements from the array.

6
3 6 1 9 4 7

63