给出数列 {an}\{a_n\}{an}，设 f(l,r) = (r−l+1)×max{al,…,ar}×min{al,…,ar}f(l,r)\ =\ (r-l+1)\times max\{a_l,\ldots,a_r\}\times min\{a_l,\ldots,a_r\}f(l,r) = (r−l+1)×max{al,…,ar}×min{al,…,ar}。
求 max{f(i,j)}max\{f(i,j)\}max{f(i,j)}，其中 1≤i≤j≤n1\leq i\leq j\leq n1≤i≤j≤n。
第一行一个数 n(1≤n≤106)n(1\leq n\leq 10^6)n(1≤n≤106)。
第二行 nnn 个数,第 iii 个数表示 ai(1≤ai≤106)a_i(1\leq a_i\leq 10^6)ai(1≤ai≤106)。
一行一个数字代表最大值。
5 1 2 3 4 5
45
f(3,5)=3×5×3=45f(3,5) = 3 \times 5 \times 3 = 45f(3,5)=3×5×3=45 为所有子区间的最大值。
