АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Удахгүй зохион байгуулах програмчлалын олимпиадад зориулж Рое өөрийн их сургуулийн оюутнуудаасаа баг бүрдүүлж байгаа. Нэг багт хэдэн ч оюутан байж болно.

Рое оюутан бүрийн чадварыг мэддэг. Сайн баг бүрдүүлэхийн тулд Рое дараах дүрмийг баримталж багаа бүрдүүлдэг. Багийн бүх гишүүд ялгаатай чадварын түвшинтэй байх ёстой. Хэрвээ багийн i дэх гишүүний чадварын түвшин x[i] (i> 0 багт заавал x[i]-1 чадварын түвшинтэй гишүүн байх ёстой. Оюутнууд хасах чадварын түвшинтэй буюу програмчлалдаа муу байж болно.

Багт илүү олон гишүүд байх тусмаа нэг дор олон бодлого бодох боломжтой болно. Тиймээс Рое өөрийн бүх оюутнуудыг оролцуулсан багуудыг бүрдүүлэхдээ хамгийн цөөн гишүүнтэй багийн гишүүдийн тоог аль болох их байлгахыг хүсч байгаа.

Жишээ нь: 7  оюутан байгаа бөгөөд тэдгээрийн чадварын түвшин нь skills = [-1, 0,1,2,2,3] гэж өгөгдсөн бол маш олон янзаар багуудыг бүрдүүлэх боломжтой. Жишээ нь [-1], [0], …, [3] Нөгөөтэйгүүр багийг мөн team1=[-1,0,1,2,3] ба team2=[2] гэж бүрдүүлж болно. Гэхдээ бид хамгийн цөөн гишүүнтэй багийн гишүүдийн тоо хамгийн их байлгахыг зорьж байгаа тул зөв хариулт нь team1=[-1,0,1,2] ба team2=[2,3]. Хамгийн цөөн гишүүнтэй багийн тоо энэ үед 2 байна.

Тэмдэглэл: Захын нөхцөл нь 0 оюутан тэмцээнд бүртгүүлсэн тохиолдолд нэг ч баг бүрдүүлж чадахгүй тул хариу нь 0 байна.

Оролтын бүтэц

Эхний мөрөнд бүхэл тоо , t , тестийн тоо

Дараагийн t  мөрөнд бүхэл тоо , N , тоо ба N оюутнуудын чадваруудын жагсаалт болох бүхэл тоо x[i] өгөгдөнө

Хязгаарлалт

1 <= t <= 100

1 <= n <= 10⁶

-10⁵ <= x[i] <= 10⁵

Гаралтын бүтэц

Тест тус бүрт хамгийн цөөн гишүүнтэй багийн гишүүдийн тоо хамгийн их байлгах үеийн хамгийн цөөн гишүүнтэй багийн гишүүдийн тоог хэвлэ.

Жишээ оролт

4 

7 4 5 2 3 -4 -3 -5 

1 -4 

4 3 2 3 1 

7 1 -2 -3 -4 2 0 -1

Жишээ гаралт

3

1

1

7

Тайлбар

Эхний тестэнд Рое хоёр баг бүрдүүлж болно. Эхний багт {-4, -3, -5} ба {4, 5, 2, 3}. Хариу нь 3

Хоёр дахь тестэнд боломжит нэг баг нь {-4}

Гурав дахь тестэнд багууд нь {3}, {1, 2, 3}. Хариу нь 1

Дөрөв дэх тестэнд бүх гишүүдийг нэг багт бүрдүүлж болно. Хариу нь 7

Цагийн хязгаарлалт

Цагийн хязгаарлалтыг энэ линкээс харна уу.  https://hr-assets.s3.amazonaws.com/7bb46cae_challenge_assets/checker_limits/3765/limits.json

Тэмдэглэл

Хэрвээ n=0 үед 0-ийг хэвлэ.

Орчуулсан : Б.Мөнхбаяр АНУ