Công suất tối đa

Trong một buổi điều tra, FullHouse Dev được viện kiểm sát giao cho một bài toán phức tạp. Họ cần phải tính toán công suất tối đa có thể đạt được từ một mảng số nguyên sau khi thực hiện một phép hoán đổi. Với tinh thần kiên trì và tỉ mỉ, FullHouse Dev bắt đầu phân tích và giải quyết vấn đề này.

Bài toán

Cho một mảng \(A\) gồm \(N\) số nguyên khác nhau.

Công suất của mảng được định nghĩa như sau:

• Với mỗi \(i\), \(j\) là chỉ số lớn nhất nhỏ hơn \(i\) sao cho \(A[j] < A[i]\).
• Công suất của mảng là tổng của tất cả các \(j\).

Ví dụ: Nếu mảng là \({1,2,5}\), thì công suất của mảng là \(0 + 1 + 2 = 3\).

Phép toán cho phép: Bạn được phép chọn hai chỉ số bất kỳ \(x\) và \(y\) và hoán đổi \(A[x]\) và \(A[y]\). Hãy tìm công suất tối đa có thể đạt được.

Lưu ý: Bạn chỉ được phép thực hiện phép toán trên tối đa một lần.

INPUT FORMAT:

• Dòng đầu tiên chứa một số nguyên \(T\), là số lượng bộ test.
• Dòng đầu tiên của mỗi bộ test chứa một số nguyên \(N\).
• Dòng thứ hai của mỗi bộ test chứa \(N\) số nguyên cách nhau bởi dấu cách, biểu diễn mảng \(A\).

OUTPUT FORMAT:

• Với mỗi bộ test, in ra công suất tối đa có thể đạt được trên một dòng mới.

Ràng buộc:

• \(1 \leq T \leq 10\)
• \(2 \leq N \leq 10^5\)
• \(1 \leq A[i] \leq 10^9\)

Ví dụ

INPUT

2
2
9 10
4
2 3 4 1

OUTPUT

1
3

Giải thích

• Ở bộ test đầu tiên, không cần thực hiện hoán đổi nào, công suất tối đa đạt được là 1.
• Ở bộ test thứ hai, ta có thể hoán đổi \(A[3]\) và \(A[4]\) để mảng trở thành 2 3 1 4, và công suất sẽ là 3.