410473: GYM104024 E Diameter

Aqua and Hiyori love the longest diameter.

Aqua has a sequence $$$a$$$ of length $$$n$$$, and Hiyori want to construct a complete undirected graph which has $$$n$$$ vertices based on the sequence $$$a$$$, which means that the length of edge between $$$u$$$ and $$$v$$$ is $$$\min_{i=\min(u,v)}^{\max(u,v)} a_i$$$. In Aqua's mind, $$$d(u,v)$$$ is described as the longest simple path from $$$u$$$ to $$$v$$$ and she want to know $$$\max_{1\leq u<v\leq n} d(u,v)$$$. But she is stupid, could you help her?

There are two lines in the input.

The first line contains a integer $$$n\ (1\leq n\leq 10^6)$$$, represents the number of the piles.

The second line contains $$$n$$$ integers $$$a_1,a_2,...,a_n\ (1\leq a_i\leq 10^9)$$$, represents the sequence $$$a$$$.

Output a single integer — $$$\max_{1\leq u<v\leq n} d(u,v)$$$.

3
1 1 1

2