CF2184E Exquisite Array

We call an array of numbers $ k $ -exquisite if it has at least two elements and any two adjacent numbers differ by at least $ k $ . You are given a permutation $ ^{\text{∗}} $ $ p $ of length $ n $ . For each $ k $ from $ 1 $ to $ n - 1 $ , find the number of $ k $ -exquisite subarrays $ ^{\text{†}} $ . $ ^{\text{∗}} $ A permutation of length $ n $ is an array that contains each integer from $ 1 $ to $ n $ exactly once, in any order. $ ^{\text{†}} $ A subarray of an array is a sequence of one or more consecutive elements of the array.

Each test consists of several test cases. The first line contains a single integer $ t $ $ (1 \le t \le 25000) $ — the number of test cases. The descriptions of the test cases follow. In the first line of each test case, an integer $ n $ is given — the length of the permutation $ (2 \le n \le 10^5) $ . In the second line of each test case, $ n $ integers $ p_i $ are given — the elements of the permutation $ (1 \le p_i \le n) $ . It is guaranteed that $ p_i $ are distinct. It is guaranteed that the sum of $ n $ across all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, output the number of $ k $ -exquisite subarrays for all $ k $ from $ 1 $ to $ n - 1 $ .