Find max min-plus-max over all subarrays

You are given an array arr of n integers.

A subarray is a contiguous non-empty segment of the array. For any subarray arr[l..r] (0-indexed), define:

$X(l, r) = \min(arr[l..r]) + \max(arr[l..r])$

Your task is to compute the maximum possible value of X(l, r) over all subarrays of arr.

Input

• An integer n (the length of the array).
• An array arr of n integers (can be positive, zero, or negative).

Output

• A single integer: the maximum value of min(subarray) + max(subarray) over all possible non-empty contiguous subarrays.

Requirements

• Describe an efficient algorithm and its time and space complexity.
• Aim for better than $O(n^2)$ time for large n (e.g., n up to around 2 * 10^5 ).