Фіксовані точки#12910

Фіксовані точки

1 секунда
256 мегабайтів
Складна

Для масиву визначимо його вагу як кількість елементів, які не зміняться після сортування. Наприклад, вага масиву [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} підмасивів.

Приклади

Приклад

Loading
Loading

Примітка

У першому тестовому наборі для кожного підмасиву всі його елементи після сортування залишаться незмінними. Тому відповідь дорівнює 1\cdot 4 + 2\cdot 3 + 3\cdot 2 + 4\cdot 1 = 20, оскільки є підмасиви довжиною , підмасиви довжиною , підмасиви довжиною і підмасив довжиною .