Глеб сходил на семинар по алгоритмам и узнал, что последовательность из $$$n$$$ чисел называется перестановкой, если она содержит в себе все числа от $$$1$$$ до $$$n$$$ ровно по одному разу.

Назовем отрезок $$$[l, r]$$$ массива чисел $$$a$$$ $$$\textbf{величайшей}$$$ перестановкой, если мультимножество количеств вхождений чисел в отрезок является перестановкой. Например, массив из чисел $$$[1, 2, 2, 4, 4, 2]$$$ является величайшей перестановкой размера $$$3$$$. Так как $$$1$$$ встречается $$$1$$$ раз, $$$2$$$ встречается $$$3$$$ раза, а $$$4$$$ встречается $$$2$$$ раза, то соответствующее мультимножество будет $$$[1, 3, 2]$$$, что является перестановкой. Но массив чисел $$$[1, 2, 2, 3]$$$ не является величайшей перестановкой, так как мультимножество количеств вхождений: $$$[1, 2, 1]$$$.

Помогите Глебу для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ найти, сколько отрезков заданного массива образуют величайшую перестановку размера $$$i$$$.