Ếch trò chuyện
Xem PDFCho \(n\) cây tre được sắp xếp theo vòng tròn (theo chiều kim đồng hồ) và có độ cao lần lượt là: \(a_1,a_2,...,a_n\) (độ cao có đơn vị mét). Ở trên đỉnh mỗi cây tre có một chú ếch rất là dễ thương.
Hai chú ếch \(i\) và \(j\) có thể trò chuyện với nhau nếu không tồn tại cây tre \(k\) nào nằm giữa cây tre thứ \(i\) và \(j\) và thoả mãn: \(a_k>a_i\) hoặc \(a_k>a_j\). (Ở đây, \(i,j,k\) khác nhau từng đôi một).
Yêu cầu: Hỏi có bao nhiêu cặp ếch có thể nói chuyện được với nhau ?
Chú ý: Hai chú ếch \(i,j\) chia đường tròn thành hai cung, nên chỉ cần tồn tại một trong hai cung mà hai chú ếch này có thể nói chuyện với nhau thì xem như quá tuyệt vời rồi !
Input:
-
Dòng thứ nhất chứa số \(t(1\le t\le 20)\) - Thể hiện số lượng testcase của bài toán.
-
\(t\) block tiếp theo, mỗi block có dạng như sau:
-
Dòng thứ nhất chứa số \(n(1\le n\le 5*10^5)\)
-
Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n(1\le a_i\le 10^9)\)
Output:
- Ứng với mỗi testcase, hãy đếm xem có bao nhiêu cặp ếch có thể nói chuyện được với nhau.
Ví dụ:
Input 1:
4
5
6 4 3 4 5
8
7 7 5 6 6 7 7 5
6
7 5 4 7 6 4
5
7 6 5 4 3
Output 1:
8
15
14
12
Input 2:
2
8
5 4 3 7 3 3 4 4
7
7 6 5 4 3 3 4
Output 2:
15
14
Giải thích:
Testcase 1:
5
6 4 3 4 5
Ở đây ta có \(8\) cặp ếch có thể nói chuyện được với nhau đó là: \((1,2),(2,3),(3,4),(4,5),(5,1),(2,4),(1,4),(2,5)\)
Bình luận
ý là test ví dụ 1 trong bài ấy
test sai bạn ơi
vẽ con ếch dễ thương vậy
viết edtorial đi anh jumptozero