Для масиву визначимо його вагу як кількість елементів, які не зміняться після сортування. Наприклад, вага масиву [7, 3, 1, 10] дорівнює : після сортування він стане рівним [1, 3, 7, 10], тому другий і четвертий елементи не зміняться, а інші два зміняться.
Вам дано перестановку цілих чисел від до . Знайдіть суму ваг всіх її \frac{n(n+1)}{2} підмасивів.
Тут під підмасивом мається на увазі послідовний відрізок масиву. Наприклад, масив [7, 3, 1, 10] має підмасивів: [7], [3], [1], [10], [7, 3], [3, 1], [1, 10], [7, 3, 1], [3, 1, 10], [7, 3, 1, 10].
Перший рядок містить одне ціле число (1 \le t \le 10^4) — кількість тестових наборів. Далі йде опис тестових наборів.
Перший рядок кожного тестового набору містить одне ціле число (1 \leq n \leq 2000) — довжину перестановки.
Другий рядок кожного тестового набору містить цілих чисел p_1, p_2, \ldots, p_n (1 \le p_i \le n, всі p_i попарно різні) — елементи перестановки.
Гарантується, що сума n^2 по всіх тестових наборах не перевищує 4\cdot 10^6.
Для кожного тесту виведіть одне ціле число — суму ваг всіх його \frac{n(n+1)}{2} підмасивів.
Приклад
У першому тестовому наборі для кожного підмасиву всі його елементи після сортування залишаться незмінними. Тому відповідь дорівнює 1\cdot 4 + 2\cdot 3 + 3\cdot 2 + 4\cdot 1 = 20, оскільки є підмасиви довжиною , підмасиви довжиною , підмасиви довжиною і підмасив довжиною .