특성의 합

길이 $n$인 배열 $a$가 주어진다. 각 원소는 $1$부터 $n$까지의 정수이며, 의사 난수 생성기가 각 원소를 서로 독립적으로 균일하게 뽑은 값이다. 부분 구간 $[\ell, r]$의 특성은 다음과 같이 정의한다. $C(\ell, r) = \min_{\ell \le i < j \le r} \max(a_i + j, a_j + i)$ 다음 합을 구하라. $\sum_{\ell = 1}^n \sum_{r = \ell + 1}^n C(\ell, r)$

첫 줄에 테스트 케이스의 개수 $t$ ($1 \le t \le 3 \cdot 10^5$)가 주어진다. 각 테스트 케이스의 첫 줄에는 배열의 크기 $n$ ($1 \le n \le 3 \cdot 10^5$)이 주어지고, 다음 줄에는 배열의 원소 $n$개가 주어진다. 모든 테스트 케이스의 $n$ 합은 $3 \cdot 10^5$을 넘지 않는다.

각 테스트 케이스마다 모든 부분 구간의 특성 합을 한 줄에 출력한다.