CF2101D Mani and Segments

An array $ b $ of length $ |b| $ is cute if the sum of the length of its Longest Increasing Subsequence (LIS) and the length of its Longest Decreasing Subsequence (LDS) $ ^{\text{∗}} $ is exactly one more than the length of the array. More formally, the array $ b $ is cute if $ \operatorname{LIS}(b) + \operatorname{LDS}(b) = |b| + 1 $ . You are given a permutation $ a $ of length $ n $ $ ^{\text{†}} $ . Your task is to count the number of non-empty subarrays $ ^{\text{‡}} $ of permutation $ a $ that are cute. $ ^{\text{∗}} $ A sequence $ x $ is a subsequence of a sequence $ y $ if $ x $ can be obtained from $ y $ by the deletion of several (possibly, zero or all) element from arbitrary positions. The longest increasing (decreasing) subsequence of an array is the longest subsequence such that its elements are ordered in strictly increasing (decreasing) order. $ ^{\text{†}} $ A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ appears twice in the array), and $ [1,3,4] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array). $ ^{\text{‡}} $ An array $ x $ is a subarray of an array $ y $ if $ x $ can be obtained from $ y $ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1\le n\le 2 \cdot 10^5 $ ) — the length of permutation $ a $ . The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le n $ ) — the elements of permutation $ a $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, output the number of cute non-empty subarrays of permutation $ a $ .

In the first test case, all of the $ 6 $ non-empty subarrays are cute: - $ [3] $ : $ \operatorname{LIS}([3]) + \operatorname{LDS}([3]) = 1 + 1 = 2 $ . - $ [1] $ : $ \operatorname{LIS}([1]) + \operatorname{LDS}([1]) = 1 + 1 = 2 $ . - $ [2] $ : $ \operatorname{LIS}([2]) + \operatorname{LDS}([2]) = 1 + 1 = 2 $ . - $ [3, 1] $ : $ \operatorname{LIS}([3, 1]) + \operatorname{LDS}([3, 1]) = 1 + 2 = 3 $ . - $ [1, 2] $ : $ \operatorname{LIS}([1, 2]) + \operatorname{LDS}([1, 2]) = 2 + 1 = 3 $ . - $ [3, 1, 2] $ : $ \operatorname{LIS}([3, 1, 2]) + \operatorname{LDS}([3, 1, 2]) = 2 + 2 = 4 $ . In the second test case, one of the cute subarrays is $ [2, 3, 4, 5, 1] $ as $ \operatorname{LIS}([2, 3, 4, 5, 1]) = 4 $ and $ \operatorname{LDS}([2, 3, 4, 5, 1]) = 2 $ , which satisfies $ 4 + 2 = 5 + 1 $ .