CF1175F The Number of Subpermutations

You have an array $ a_1, a_2, \dots, a_n $ . Let's call some subarray $ a_l, a_{l + 1}, \dots , a_r $ of this array a subpermutation if it contains all integers from $ 1 $ to $ r-l+1 $ exactly once. For example, array $ a = [2, 2, 1, 3, 2, 3, 1] $ contains $ 6 $ subarrays which are subpermutations: $ [a_2 \dots a_3] $ , $ [a_2 \dots a_4] $ , $ [a_3 \dots a_3] $ , $ [a_3 \dots a_5] $ , $ [a_5 \dots a_7] $ , $ [a_7 \dots a_7] $ . You are asked to calculate the number of subpermutations.

N/A

N/A

There are $ 7 $ subpermutations in the first test case. Their segments of indices are $ [1, 4] $ , $ [3, 3] $ , $ [3, 6] $ , $ [4, 7] $ , $ [6, 7] $ , $ [7, 7] $ and $ [7, 8] $ . In the second test case $ 6 $ subpermutations exist: $ [1, 1] $ , $ [2, 2] $ , $ [2, 3] $ , $ [3, 4] $ , $ [4, 4] $ and $ [4, 5] $ .