JAVA题解：

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        int[] h = Arrays.stream(br.readLine().trim().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        
        System.out.println(maxRectangleAreaAfterSwap(n, h));
    }
    
    public static int maxRectangleAreaAfterSwap(int n, int[] h) {
        // 1) 基准：单调栈求最大矩形面积（不交换）
        int base = maxAreaNoSwap(h);
        
        // 2) 构建稀疏表 RMQ（区间最小值查询）
        int LOG = 32 - Integer.numberOfLeadingZeros(n);
        int[][] st = new int[LOG][n];
        
        // 初始化稀疏表第一层
        System.arraycopy(h, 0, st[0], 0, n);
        
        // 构建稀疏表
        for (int k = 1; k < LOG; k++) {
            for (int i = 0; i + (1 << k) <= n; i++) {
                st[k][i] = Math.min(st[k-1][i], st[k-1][i + (1 << (k-1))]);
            }
        }
        
        // 预计算log2
        int[] log2 = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            log2[i] = log2[i / 2] + 1;
        }
        
        // 3) 排序统计 >= H 的数量
        int[] hs = h.clone();
        Arrays.sort(hs);
        
        int ans = base;
        
        for (int i = 0; i < n; i++) {
            int H = h[i];
            
            // 中心最大区间 [l0..r0]
            int l0 = findLeftmost(0, i, H, st, log2);
            int r0 = findRightmost(i, n - 1, H, st, log2);
            
            if (l0 == -1 || r0 == -1) continue;
            
            int w0 = r0 - l0 + 1;
            
            // 左侧延伸
            int wLeft = 0;
            if (l0 >= 2) {
                int end = l0 - 2;
                int stl = findLeftmost(0, end, H, st, log2);
                if (stl != -1) {
                    wLeft = end - stl + 1;
                }
            }
            
            // 右侧延伸
            int wRight = 0;
            if (r0 + 2 <= n - 1) {
                int stp = findRightmost(r0 + 2, n - 1, H, st, log2);
                if (stp != -1) {
                    wRight = stp - (r0 + 2) + 1;
                }
            }
            
            int totalGood = countGreaterOrEqual(hs, H);
            int w = w0 + 1 + Math.max(wLeft, wRight);
            w = Math.min(w, totalGood);
            
            ans = Math.max(ans, w * H);
        }
        
        return ans;
    }
    
    // 单调栈求最大矩形面积
    private static int maxAreaNoSwap(int[] heights) {
        int n = heights.length;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int maxArea = 0;
        
        for (int i = 0; i <= n; i++) {
            int current = (i == n) ? 0 : heights[i];
            while (stack.peek() != -1 && heights[stack.peek()] >= current) {
                int height = heights[stack.pop()];
                int width = i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        
        return maxArea;
    }
    
    // RMQ查询
    private static int rmq(int l, int r, int[][] st, int[] log2) {
        int k = log2[r - l + 1];
        return Math.min(st[k][l], st[k][r - (1 << k) + 1]);
    }
    
    // 二分查找最左边满足条件的位置
    private static int findLeftmost(int L, int R, int H, int[][] st, int[] log2) {
        int ans = -1;
        int l = L, r = R;
        
        while (l <= r) {
            int m = (l + r) / 2;
            if (rmq(m, R, st, log2) >= H) {
                ans = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        
        return ans;
    }
    
    // 二分查找最右边满足条件的位置
    private static int findRightmost(int L, int R, int H, int[][] st, int[] log2) {
        int ans = -1;
        int l = L, r = R;
        
        while (l <= r) {
            int m = (l + r) / 2;
            if (rmq(L, m, st, log2) >= H) {
                ans = m;
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        
        return ans;
    }
    
    // 计算数组中大于等于x的元素个数
    private static int countGreaterOrEqual(int[] sorted, int x) {
        int idx = Arrays.binarySearch(sorted, x);
        if (idx < 0) {
            idx = -(idx + 1);
        } else {
            // 找到第一个大于等于x的位置
            while (idx > 0 && sorted[idx - 1] == x) {
                idx--;
            }
        }
        return sorted.length - idx;
    }
}