{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eBaoBao is a good student who loves reading, but compared with his huge bookshelf containing lots and lots of books, his reading desk, which can only hold at most $k$ books, is surprisingly small.\u003c/p\u003e\n\n\u003cp\u003eToday BaoBao decides to read some books for $n$ minutes by the desk. According to his reading plan, during the $i$-th minute, he is scheduled to read book $a_i$. The reading desk is initially empty and all the books are initially on the shelf. If the book BaoBao decides to read is not on the desk, BaoBao will have to fetch it from the shelf. Also, if the desk is full and BaoBao has to fetch another book from the shelf, he will have to put one book back from the desk to the shelf before fetching the new book.\u003c/p\u003e\n\n\u003cp\u003eTired of deciding which book to put back, BaoBao searches the Internet and discovers an algorithm called the \u003ci\u003eLeast Recently Used\u003c/i\u003e (LRU) algorithm. According to the algorithm, when BaoBao has to put a book back from the desk to the shelf, he should put back the least recently read book.\u003c/p\u003e\n\n\u003cp\u003eFor example, let\u0027s consider the reading plan {4, 3, 4, 2, 3, 1, 4} and assume that the capacity of the desk is 3. The following table explains what BaoBao should do according to the LRU algorithm. Note that in the following table, we use a pair of integer $(a, b)$ to represent a book, where $a$ is the index of the book, and $b$ is the last time when this book is read.\u003c/p\u003e\n\n\u003ctable id\u003d\"problem-table\" style\u003d\"border-collapse: collapse; text-align: center;\" align\u003d\"center\"\u003e\n \u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eMinute\u003c/th\u003e\n \u003cth\u003eBooks on the Desk\u003cbr\u003eBefore This Minute\u003c/th\u003e\n \u003cth\u003eBaoBao\u0027s Action\u003c/th\u003e\n \u003c/tr\u003e\n \u003c/thead\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e1\u003c/td\u003e\n \u003ctd\u003e{}\u003c/td\u003e\n \u003ctd\u003eFetch book 4 from the shelf\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd\u003e2\u003c/td\u003e\n \u003ctd\u003e{(4, 1)}\u003c/td\u003e\n \u003ctd\u003eFetch book 3 from the shelf\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd\u003e3\u003c/td\u003e\n \u003ctd\u003e{(4, 1), (3, 2)}\u003c/td\u003e\n \u003ctd\u003eDo nothing as book 4 is already on the desk\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd\u003e4\u003c/td\u003e\n \u003ctd\u003e{(4, 3), (3, 2)}\u003c/td\u003e\n \u003ctd\u003eFetch book 2 from the shelf\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd\u003e5\u003c/td\u003e\n \u003ctd\u003e{(4, 3), (3, 2), (2, 4)}\u003c/td\u003e\n \u003ctd\u003eDo nothing as book 3 is already on the desk\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd\u003e6\u003c/td\u003e\n \u003ctd\u003e{(4, 3), (3, 5), (2, 4)}\u003c/td\u003e\n \u003ctd\u003ePut book 4 back to the shelf as its the least recently read book,\u003cbr\u003eand fetch book 1 from the shelf\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd\u003e7\u003c/td\u003e\n \u003ctd\u003e{(3, 5), (2, 4), (1, 6)}\u003c/td\u003e\n \u003ctd\u003ePut book 2 back to the shelf as its the least recently read book,\u003cbr\u003eand fetch book 4 from the shelf\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n\u003c/table\u003e\n\n\u003cp\u003eGiven the reading plan, what\u0027s the number of times BaoBao fetches a book from the shelf if the value of $k$ (the capacity of the desk) ranges from 1 to $n$ (both inclusive)?\u003c/p\u003e\n\n\u003ch4\u003eInput\u003c/h4\u003e\n\u003cp\u003eThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:\u003c/p\u003e\n\n\u003cp\u003eThe first line contains an integer $n$ ($1 \\le n \\le 10^5$), indicating the length of the reading plan.\u003c/p\u003e\n\n\u003cp\u003eThe second line contains $n$ integers $a_1, a_2, \\dots, a_n$ ($1 \\le a_i \\le n$), indicating the indices of the books to read.\u003c/p\u003e\n\n\u003cp\u003eIt\u0027s guaranteed that the sum of $n$ of all test cases will not exceed $10^6$.\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\u003cp\u003eFor each test case output one line containing $n$ integers $f_1, f_2, \\dots, f_n$ separated by a space, where $f_i$ indicates the number of times BaoBao fetches a book from the shelf when the capacity of the desk is $i$.\u003c/p\u003e\n\n\u003cp\u003ePlease, DO NOT output extra spaces at the end of each line, or your solution may be considered incorrect!\u003c/p\u003e\n\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\n7\n4 3 4 2 3 1 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e7 6 5 4 4 4 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003cstyle type\u003d\"text/css\"\u003e\n#problem-table \u003e thead \u003e tr \u003e th, #problem-table \u003e tbody \u003e tr \u003e td\n{\n padding: 3px 5px;\n border: 1px solid black;\n font-size: 14px;\n}\n\u003c/style\u003e\n"}}]}