CF2165F Arctic Acquisition

You are given a permutation $ ^{\text{∗}} $ $ a_1,a_2,\ldots,a_n $ of length $ n $ . An interval $ [l,r] $ ( $ 1\le l\le r\le n $ ) is jagged if and only if it contains a 21435-subsequence; that is, there exist integers $ i_1,i_2,i_3,i_4,i_5 $ such that $ l\le i_1

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\le10^6 $ ) — the length of the permutation. The second line of each test case contains $ n $ distinct integers $ a_1,a_2,\ldots,a_n $ ( $ 1\le a_i\le n $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^6 $ .

For each test case, output the number of jagged subarrays.

In the first test case, the only jagged subarray is $ [1,5] $ , containing $ [2,1,4,3,5] $ as a subsequence. In the third test case, the subarray $ [1,8] $ is jagged because it contains $ [9,6,11,10,13] $ as a subsequence, which is a 21435-subsequence.