Problem ID:
goodarr
Points:
3.2 (partial)
Time limit:
1.0s
Memory limit:
256M
Input:
stdin
Output:
stdout
Author:
Problem type
Allowed languages
C, C++, Golang, Java, Pascal, Perl, Python, Rust
Một dãy số nguyên ~b_1, b_2, b_3, ..., b_k~ được gọi là đẹp, khi thoả mãn tính chất sau: ~b_{i+1} - b_i \ge b_i - b_1~ ~(\forall 2 \le i < k)~.
Cho một dãy số nguyên ~n~ phần tử ~a_1 \le a_2 \le a_3 \le ...\le a_n~. Hãy tìm cách loại bỏ một số ít nhất các phần tử của dãy ~a~ để được một dãy số đẹp.
Dữ liệu vào
- Dòng đầu tiên chứa một số nguyên ~t~ ~(1 \le t \le 10^4)~ - số bộ dữ liệu.
- Trong mỗi bộ dữ liệu:
- Dòng đầu tiên chứa số nguyên ~n~ ~(2 \le n \le 2.10^5)~ - kích thước của dãy ~a~.
- Dòng tiếp theo chứa ~n~ số nguyên ~a_1 \le a_2 \le a_3 \le ... \le a_n~ ~(1 \le a_i \le 10^9)~ - các phần tử của dãy ~a~.
- Dữ liệu vào đảm bảo tổng các giá trị ~n~ trong tất cả các bộ dữ liệu không vượt quá ~2.10^5~.
Dữ liệu ra
- Với mối bộ dữ liệu, in ra trên một dòng số lượng ít nhất các phần tử của dãy ~a~ cần loại bỏ để được một dãy số đẹp.
Subtask
- ~10\%~ số điểm có ~t = 1, n \le 20~;
- ~20\%~ số điểm khác có ~t = 1, n \le 1000~;
- ~70\%~ số điểm còn lại không có ràng buộc gì thêm.
Sample Input
3
4
1 2 3 4
5
1 2 5 5 7
6
7 8 1234560 2348768 7890000 12378459
Sample Output
1
2
2
Giải thích
Ở bộ dữ liệu đầu tiên, ta có thể bỏ số ~4~ để được một dãy đẹp là ~[1, 2, 3]~.
Comments