Longest Concave Subsequence

Problem Overview

• Determine the length of the longest concave subsequence: endpoints greater than all middle elements.
• Input: arr of n elements, a permutation of 1..n; Output: integer length of such a subsequence.
• Constraints: 1 ≤ n ≤ 1e5; arr[i] in 1..n; subsequence preserves original order.
• Context: sequence pattern detection in arrays; asked in TikTok coding interviews, a common interview question and algorithmic problem.