Giá xấu

Điểm: 2,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho dãy giá $a_{1}, a_{2}, \dots, a_{n}$ của một sản phẩm trong $n$ ngày liên tiếp. Giá ngày thứ $i$ được gọi là giá xấu nếu tồn tại một ngày $j$ với $j > i$ sao cho $a_{j} < a_{i}$ (tức là về sau có ngày bán rẻ hơn).

Hãy đếm số ngày có giá xấu.

Có $t$ bộ dữ liệu độc lập trong cùng một file vào.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $t$ — số bộ dữ liệu.
Với mỗi bộ dữ liệu:
- Dòng thứ nhất chứa số nguyên $n$ — số ngày.
- Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ .

Dữ liệu ra

In ra $t$ dòng, mỗi dòng là số lượng ngày có giá xấu trong bộ dữ liệu tương ứng.

Ràng buộc

$1 \leq t \leq 10000$
$1 \leq n \leq 150000$
$1 \leq a_{i} \leq 10^{6}$
Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá $150000$ .

Ví dụ

Input	Output	Giải thích
5 6 3 9 4 6 7 5 1 1000000 2 2 1 10 31 41 59 26 53 58 97 93 23 84 7 3 2 1 2 3 4 5	3 0 1 8 2	Bộ 1: các ngày xấu là 2 ( $a_{2} = 9$ ), 4 ( $a_{4} = 6$ ), 5 ( $a_{5} = 7$ ) vì sau chúng đều có $a_{j} = 5$ nhỏ hơn. Bộ 4: chỉ ngày cuối ( $a_{10} = 84$ ) không xấu vì không có ngày nào sau nó; tám ngày còn lại đều có ngày sau nhỏ hơn (giá 23 ở ngày 9).
1 5 5 4 3 2 1	4	Dãy giảm chặt: bốn ngày đầu đều có ngày sau rẻ hơn, ngày cuối không xấu.
1 5 1 2 3 4 5	0	Dãy tăng chặt: không ngày nào có ngày sau rẻ hơn.

Bình luận

Không có bình luận tại thời điểm này.