Maximum Element after At Most One Rotation

You are given an array of n integers. You are allowed to perform at most one rotation on the array. In a rotation, you may move a prefix of the array to the end while preserving its order.

Your task is to determine the maximum element in the array. Note that since a rotation does not change the set of elements, the answer is simply the maximum value among the elements.

Formally, given an array \(a_1,a_2,\dots,a_n\), output \(\max\{a_1,a_2,\dots,a_n\}\).

inputFormat

The input is given via standard input and consists of two lines:

• The first line contains a single integer \(n\) (\(1 \leq n \leq 10^5\)), which denotes the number of elements in the array.
• The second line contains \(n\) space-separated integers, representing the elements of the array.

outputFormat

Output a single integer, which is the maximum element in the array after at most one rotation.

5
3 -1 5 2 9

9