Problem:


Score : 600 points

Problem Statement

Takahashi has N cards. The i-th of these cards has an integer A_i written on it.

Takahashi will choose an integer K, and then repeat the following operation some number of times:

Choose exactly K cards such that the integers written on them are all different, and eat those cards. (The eaten cards disappear.)

For each K = 1,2, \ldots, N, find the maximum number of times Takahashi can do the operation.

Constraints

 1 \le N \le 3 \times 10^5 

 1 \le A_i \le N 

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N

Output

Print N integers.
The t-th (1 \le t \le N) of them should be the answer for the case K=t.

Sample Input 1

3
2 1 2

Sample Output 1

3
1
0

For K = 1, we can do the operation as follows:

Choose the first card to eat.

Choose the second card to eat.

Choose the third card to eat.

For K = 2, we can do the operation as follows:

Choose the first and second cards to eat.

For K = 3, we cannot do the operation at all. Note that we cannot choose the first and third cards at the same time.

Sample Input 2

5
1 2 3 4 5

Sample Output 2

5
2
1
1
1

Sample Input 3

4
1 3 3 3

Sample Output 3

4
1
0
0



Sample input:
3
2 1 2


Sample output:
3
1
0

Submission status: Wrong Answer

Solution code:
import subprocess
import gzip, base64, os
import stat

gz = b'H4sIAG0Yq10C/+19fWATVbb4pGlL+GoKAlZAKBiFipQGCrR+tpTADKRQaUFWlGmaprSSNjWZlOKi4LZVY6jyXJ/re79dH7vuuu636/pcVISWjxZQEVAQxQ/8QCcUpaJCFSS/c+69k85MMhV2972/XpTenDPnnnvPueeee+5H7qx1OOckmUyc8knibuQQMo0uIHABw28IxEgAl8f1h79judFcKsApKroCrkCT9jDWSmphdGb4lwz/8pIonJdUoElHMzolNanSFE79KdCkzSs5TcpxmbF8WNfDtRR7uLZck2YkU3xOP22+JJavh+XrYfRKyiVxmlSRL5n9K2P4MiaXks5mdLNV9PgpOSZV4vfGSgo3VhZo0kcZ3aO6fDdDvlTuwj/pLF3EyjPSy0RWfyVV2mGKt6ZiRu4Ub+Vkb01dsHFyY96MyTNyswO+7KmkTumMdu6CxRo9ZrA6D2M2gM/PrL1hVlH7r4PRaRPOnwk8/WRt96kN+Oxalg+bpKUuvTp5XP8kE5fLrQPW+OwG+DcL/j377rSDA+7dIP7C/fLOh2qjux5ocY94s3Rj0/ofFXw5+UtxeVpmQ85Ex0Fn2/Gr2oY9PqjoidH1m1YLK5/vSz+vQAWGJsC/mJQYL6Ukxo8wJcanxyxM+xlrgH/TgH+lAf5ZLjH+EQP6stTE+EEGeLcBvi45Mb7EoNypBnzGGuj55wb4MQZ8phnoc4EBn6ABn7cN6CcZ0C80KPenBu1ywgB/nUG5vzSwq6EG9ZlrQL/MgP49A/u3GPBpNWj3jQb4Xxrwv8dADzUG+rzJoP42A3y5gT4vM6D/dwN5ywzqX2zA5w0DuTIN+Ow00NsyA/xfDer5lUG/SzPQwwsG/P/boJ5zDOTdZlDuAOAzjhvJPeNn4y7Df5tE8d2Bcs34lJZC8ZxE8UsZ/hTjwzE+6xj+96zcfZcVaMrNZvrZOFKLnwp8hgCfo4y/YmOuZIrnguWaca/NRMtd59fSn2b863XlzkyhfDb6tXxsjP9Rhk9nD7KTKf9ySSvXeqb/glFa/hyMwwGp0j1pEo69MzhRXFHrqxMDkssviSInzmsQF3lW1AQkj7/I6woEPAFOFMqKxUqPn6HLiou8vjpPmavC66HPEj8R66Vqv8dVKa70rBbd8E1CpLvRJVb5PR7R0+j21Es1vjpOvHVBaSAXiq2354hYUkDy+1Y7Fs0vdQluBz6eXypNd0ur6z0A26cBzaqaSk+dWFNXIzkagKBUss8URSjOt0qsgBJdXq/P3UBzBuzTqmrqKsWqGn9AEn1VjpL57tpaUqhvepU3GKhWWMxQs3C7AhLhAA+m+YN1Uk0t1Nnv9/ln21UZfFBXj6sWqhLw+CXBDVi7u9rlFyW/q0YKQH0di5BDhStQ41aohTKxLEd0lM4QS+aXThO9TC2kcMI5H5RZW1MHGqNVCBTZUR0BUu+yMmCY38uwpm4FY5ugdKJCB5Ujr8YXANkCnlwBFMfEAPwMUJbL6+lF6ARmhcdqAgpUtQ1B1WowEqsdlJdQI9PdXo/L74AnU0UB6gT/JGIdIPrUHKUVfEFsLtHvqlvhgSKV1pxBWhNMUxLrfNoGxcczVY2te14mQM3UZocInaysKSrAouvABiR3tco8oW6loqe2XloNJl8Pfcbnd63wKBZqn06lpk1SEawybo9pQIPKFlc0Nor1Hn/AV+fy1gDbhhymwFg1Z09lrRIAZRWLoLiVInCsVLAzXPX1nrpKIiRgKr0lDdAUUj7ITrQooZxLLqp2pB1y3aD/+LxgZgZ5MVvdqlqSeSYrXaW7fFAddQKO2lqNscTMkopK9E86MNDqvIRvWn1QcriZlV5cHwArxdYmBrcQVFbrq/QQ+RaA14FCG10VNQ12NL9AjehG1yeix4GeXeVzqH2UHSRh/dPLhI7TOBDP9HvAJTSAuDq79nrqVkjV1NyYXev7ZhHrivPVlpC7qtol6ZuddUxsdvTstdSpw7cVbmgvhOycuLhuFXaKRZ5AsNaDD92UrMoHPDhQnOTzclUeXxVXtcIjBTg3UT8+gLoqLSJ5GmskrtZT666tJ0n9aq7K7fUFPFwtpQdkra8BnTwWwYaUWldNHYcOn5tbVCROy87h5jqFWUXi1Gx7buzr1OzpXNHSpYWzBNGePY2ily4F6tzsfA1kt6tBOk+k/ynfzfAvmfyXRL7Rvxz7nqzKkcylsOdJMNNMIrPNZEaVyuhT2fN+LLWo6OP/SyXjtYk7ltI7Xyu5avVAnJHelarMh4EylT7PwXn5vz2WiqsAP2G44Mia/liP1hh9MokBlPjmjb+sTMGZ8X8w+tDarCRc4fg1g109P0vCmfKzDJayHrGgzO2MX4+Pxgmp+nURFleksHmy8lmnws9Sx+kq/GwV/hkV/loV/qgK71DhlfgN8ddpJsi9+OvV8bgKP0fNX4XXRDzBXnyhCp1RT/H9VDEWic9U+CQVfqIKb1bhc1T4ZBU+T4VX67lAhe+nwvMqvEU9D1bh+6vwS1X4AWr9qPADVfhqFX6QCl+vwg9W4RtV+DS1PajwVhX+ARU+XYXfoMIPUeEfV+HVcf9GFf4SFf5pFb5IbW8q/HAVfpMKP0KFb1PhL1Xhd6nwGSr8PhV+pAp/WIW/UW2HKvwoFV5W4Uer7V+Fv1yF71Hhx6jt+c5e/Fj1PFuFV89701X4cWr7V+HHq+1fhb9Cbf8qvE1t/yr8lWr7V+GvUtu/Cn+T2v5V+Ilq+1fhs9T2r8JfrbZ/FX6S2v5V+GvU9q/CT1bbvwqfrbZ/FX6K2v5V+By1/avwc9X2r8Lb1favwk9V278KP01t/yp8rtr+VfjpavtX4Weo7V+Fn6m2fxU+T23/Kny+uh2bTlj4cMprt2RyfEublCIvI8gdlu30eXT6NngUvXIH/LWOLYBvCFfjo8jRKHyufBFhdMmRfQR+FmF0xZE2Av8eYXTBkWcI/CuE0fVGNhL4PxFGlxvZQOBHEMbhLrKOwA8ijNWO1BP4Jwijy42UE/guhNHVRkoI7EcYXWykgMB3IIyuNZJD4AqE0aVGMgl8K8LoSiPpBF6EMLrQCEfgeQij64x0n0d4FsLpRH4CX4vwECI/gaciPJTIT+CrEb6EyE/g8QgPI/ITeCTCw4n8BB6K8AgiP4EHIHwpkZ/ASQhnEPkJ/N0SgC8j8hP4FMIjifwEPo7wKCI/gT9CeDSRn8DvIHw5kZ/ABxAeQ+Qn8B6ExxL5v0d4G8KZRH4Cv4jwOCI/gZ9FeDyRn8C/R/gKIj+Bf4WwjchP4P9E+EoiP4EfQfgqIj+BH0R4ApGfwD9BeCKRn8B3IZxF5CewH+GrifwEvgPhSUR+AlcgfA2Rn8C3IjyZyE/gRQhnE/kJPA/hKUT+c6T9Ec4h8hP4WoTtRH4CT0V4KpGfwFcjPI3IT+DxCOcS+Qk8EuHpRH4CD0V4BpGfwAMQnknkJ3ASwnlEfoBLtiZDxCQfg69bcW1qC4IvytDbZTtUf+l2++dCaP9yPvQR3/RJd0mZ0Nm2r7yA4zvby0nS2T26gJMPQfavrWMhMNx0BrIu5id3Q8I39aTxoWOrkm7fvon4CnAQX9++FR9Fj1rHkqWrTd0q+vYeM9DzoW18+/GbeNM+fn9PEDK/SDMfgMx8qIPm/4jlX3fDrUvBmIJDFkNO+R4Q8PaOlLmAMn21Hf0N33TDxJuBQBoTq8KwxVu7a6G00LHovtsjP4Ys1rFcJEDTEhm7vr3t1u1VRJ7FhbcULilcXFhWyt97YhM824pdZwuGmTIHUvOh7Q77ab7liDSRb33UhoVs+QQ1E/pAxvbiO4twSRw0VUTCJCH0vorDlrPIYSff8rlUhNnb8MntLsx+Ur6TZHeQbHxns22D4nJDf7RtJDiHBf1k52wb8c1dmRoq+L5RGTRMIaCxf+4MPWd7GhehW05LyUJ0jsUZkmzVqvpkn1VLNJlvXW/bhQ9RghcHkLI/kGvOJhQLmT8DX53hWiDz2pY6HvSotXXgu2hUCHWqMG3fkdLsn2NhUwutz+9o6lkcNAvRnaiLfbQ4Z+gLeUWCEvnQe3z4Nls1H76ODwc5uYiw74eqHMBHiy3W5mdBOULnXJILUpLLGdpMNCQ03cRZmz8Ft9TRbHsc5wRh0FBzGx+GigdtyCA4hg87OL61UX4BJxt8/uvWlsMjOdI0930LFYJKX8FH51uCl/Nhs5au4DKqquVI17rZ9gBWuPU5UrTc/xoEKFJ23oCUs21L+fDPKRmwnULYZsWxvZSx7YdsoX0fYO27NTOmU++3Kp1ew4eRc+v1O0lImk6emTuKLESLTJsZMW06SE1K+NY1tsZYbZdN0tj8oG+ZhXwSs3ke9Lxlrova/OZvExnHuyoOe3oYh2iMw1I1h7sScvgAG7sRNdLUKEPTbUZseCYfXiDbD2C2r3qw/TuEpvNRa/MVJo7YYAZkcJq6UaxqRs13bsNhGbOsO4NZdqrtv6dXe9Zm3oQGc5JvnWt6uQfaQMjvsDZfDshNWDdnVjdv6sTq456R/bQQ+l5+/wytRGtdhtD0vckZOm5t2UvqfxCbovpB7gEHF3mVY7Vj5RxFOFpkibyJX+KMbucIanRDgDkf/iO1XwO7BvO3No8Fx026QMtw/Ba+G9BRCM0KSNudlHedjkYj3xHnBZVQiT8FSsA6tUklfCeHIvOdBawhCliv29mVCzz4MDgOkEr+OfDcdJQpp+XTS5FkUoK+Wgw1uEKILoTeIoT7aQWsG4ECROUcqNfWibHa/BJA+26szTjrLW3WIb2V6CzIYJXKpOzb+dB6G44HYFWFLyNj69hm0jWEcK6NNHvopDP0nTyYNhAq2ZnfKFt/UkHa+Etn1rfYJTHu5ENfIGUATEGlmmGnsce3QdcMr2dkFuyC+DWRol5AZNfADQq5vY0PNdtKMGPratmZfzK4DAtcxxwDPpBzZmDz/5xSQd+4iriBTOYGMI8Pzbb/N7T3l7D1CjT54tZ7TNYWKxh25PckAG/viY13l21Cg++2tpugBs+BFw/TpKtf2NRaEg0NaWmzPuzDPgEVeQYeyJ1QQuR2xDS19bxA+eyWLnuB8bGAsgmf9QofS+vN0VB6y27rw8vUfNYiHwEwxaFPt86D/i1//zVg1p/HRtgR+SSDGKxk6G6bhlHLvxRyFbd8Il0pRJ02oBTCyTYt5f3DsBk/kz//SmNCyyEjcTQ/aEMwMjlDa2zlPCiHNEoYfEeBhXgOPn+7tdkK1BAfYAM8PpN0BCF8i0W47pZ0aRTGJhC5XM03bbMIoVsska3AgcYPxeB1QvvQV0BwA0K/QFyHdfaHgmmH9ZE2nugUPmP50F5n/qfWR9ot7U6r41MQt/Blsi52Fb9JoRHyd6xqnNd6/THiztu/Ie4LSsCaOLNOCaG3hPYoVGQf33S0x2mSsVITsecNdKL5nyb6mN/q/d6CEQCM/mfkzaeiUWcYBC8OTRFCPsv81tnHQBlz0/mm7RY+HwZYa4sFyu4a6gydldOwQTFiilwxAsOIqDSRFO+zCE1rM7jg8BjfSuQLffq2U9j633el8eFrrrSQHnraYf+8OHROMX+5ZjqqG707GbLQ5q+KG/reHEqHvkGn0Phn2xpJI245RzVzk5D/hTPstJVYm5eg62919BCVy8ClxMSH9vPjvpSGCq25HUL+l6suEVqT28FfrRpg3+0MdUfQUwBqLx86xDd9ChVbfo5v70pyQJ+Nbpf6Q7F802cmKaPQmp4K/xakF1qHmOCfkF64KZn0trNJ/lnzW9e058xvva0jx5nVUaX4H2t60T5r+vyj1iFz91mHLDwKcLc1fSCA3dYhVr6pswAUDf86eoJv8vl7rM2PEYd2nM/aBtbUA4GwmY9uozUzo52l8KDiGXzTeZM0Hv4mSaDZHCGUu5uPtkN3tfQJNX2X7M8TWp27M5T68eF0PnSzzIdLwNZv7oYU4R5IM/jQEPAjmZAxk8+XgweLQ69jJ8zETpgRvMwZ+liIDS3Bbjqk1nZrvOb73XQ83R0b6utxqOfZUP/wl4niurf5kNM2kYUujaYtFtI9z8n2U4SZKthZC+xp7x7JhzI6Ciyke7NuzeKaTieO+xDVgaeBKkv10NIwpA/6vAc9VXsE1NuObbyHb/oI2lgIX4rKbj9/Ez/ufd50SIgmnxaaOkF13yb5c6s2CGEr0rZ/B8/f4U174PkhIbzQEo9s6kwX8juDezF2Ac9iUdW78yQLgUiUNgECtM9Jj/adNAzQBBhCwx7oPaDKz8EnFofOWh/4DRn5vTYeZmXYDcDVLQwP21vccuCetdA5naHz99xRRT7ZsfYOfQVlEp8uWBfs4ltzB/Khw+CcbuJbywZGsau0R+C7BHrdfx4MJkr9v9X5Om/6Ughf8yo/roc3HXbmH7x7mBC6ZgeQmLDQtb8pDg2zdSXD3x1CtFOIthfnv21t8aLvsJBKQu3AExSHPiAtyoM7EbvJaKzSzJ++UMb8kc5QTuIWbUf7SOfDJhqthjJU+Wu/IBMq6LkwroDBXf8eUewIgnZwHQ5k6GAMHYyhjIwysReD8TlDPQgW8OEyG29d/1sci8P4OJyBUkDvmT0YZ7bn+c4OEkhaF3Q48yMwTYFvXxZD41h5CDglW07hVhyg9fqHwCmP36SsLvL5Hcg9h7fObsfencxHZ6WD+EzpfLvQujCK8laDViApj7xCePbyM+0neGfYLGTtKyRTZetDT8XGHwG6U8tpPnTqntsIzIfeULX/K3zrsIEY+7d/D22+Btv/W9r+ZUOg/b/jm6Kx9t8FRQnhQdD+O3nTe8789rsvEUKDTgCJae3vikPJtq5+MD7ClxN8FCLgeSb+Oqi2M/TK3aMWhGe/YVkwafbZHiG0x/pwNZlq0/o77Ee0+mk5bW3uxDlqeJgNAFY6WqozDSKLhqgQHvYquj8yOhaS8fSeipi/dYZ28+3fQj9sd5p2F7feCTH4Gb49CohOoXVNvqkYLLg4nHyuOH/nPZcI+QfvmVAcuuZE17BYvJi/755hKEQxBIWh1xa2OvubYMxY81shNOzEgtCwI0J0e3H+Wev6UhBiXrjsbA80m9C5nZgCjEDl1pYaCG+6hrP1iXmdIDVteCdGF2BUkAHbvGReyNnTI03jo/PSg5PJBOxadKZD1t1l4YLQKm/I1hNotu/wobcQGtLFoC7oX8ihAPwLsl1qbfkNCfTRTFvIHNaCfHngK4AzC73Ch/Mo60ZkDbGO/FwXjs9g6p3yC8eRLxj+KbTAyaQ+E0gmdX2AkbyWZDoF9ZGbaSYkg542HiK49OBoZaoxcN3dkCVFXthFJxy3HNdEZbuOo6v6/IKisp18+8dmaqHm3kCIz99pvf+KIWglQQjxi2HM2sViLBiqAiXgKi0k7vtcGogDzWMnyNpDcdbXUhpEJRAKOUMfyUcR237O3DuM/TmC0crd3PzW5M+EkMMitA46KYSAfcsRjFBK1mZ0LdD1ZwiTSAWirwlhB0RMu6TRKFgqHx6IUwQYdZFR11BmDzifDL0vX5lDQt+1bSq1/DVyMfMdp63eST0X9P2JsVhVAM00P4qTGgjC1+EKyOYV1AVVdZVefDg/wUTnJyScfwYqGBlu0vgfIbwYZOqu6h1fwB91QHMIZ05gINou3wTjYhJv2sav3Hb6wZ+bxuPY3zrH9MAYmAj1B+8xdBWY0O7GVPvurrSqDR3cZHiaRLp1B7q3vUL+ab612XYvyBK4dMODaQ+WRB8Y8QBYd3Qvn9/NtxaY/MdVIcdKWVlS28TCZxL6YuzxAAoxKkJW1VjMwVbXUJHNtkYyO1tjq0eJEZCfmIjrWZsJgNHuFDKDzYqbwT55nka7dZ/RqVljbGq20+K8zotB9BtIAs4fAuYbC5vW9uCMt3E8hsoCdAcF2TgYMTMBI4Rv7DIDDdpdPRiTM7wMhtH3+ay9EJyYneFKW7l0N29eK0NoVJx1DrQhWP/ytRPG3OZniUi32ZYKrct6+KxXIJiFKGc7v0mJlsEOkuwH+HGHrc1k0QDCk2onxMRsQH0HQqHzfOus8/x+GTpRtE1ajRptOmYK1jvsByAGISGzSumnP6XD7hEMsmA2kW5tnpWMynzU9jQofYvAljSf+CyR8rsiw5NZLSIlJvbNHo2sJW4znw/XWJwQdmEvDYO85jvlwheSiHc4BQNxUgB01o6etcQZOtRVPA/DW2fWHjr+8eFCCG5rILCFr7Ucb66XefPdgCqEGDdLjyXh7rZzwd0KRz70DW/6ns9/IziYhxEe2mJp5E+kG7/DZ+3RROhvwSTBjAunB6RB4E2C/Qh1lwMHSAWYAACJ2E1YsrkaS7SQR3qUBoKSMXKfSaoAT262kKdQ6XASTQrTY5jCDOUrSAP2EHwVZ1qPD8DmWG/bAKn9gPybY2iNk3A5CZ803Q2mN1yhk//+GV1pIpnC8y1C/mvW5tQksswr4CwdfBREKgU4vWCLl8tlDGWtuDQUekc+fQwNeIEFAgWh1WFx5kODSgPAOQbFyHps4fxd1uYm+FK4BftQBH8FcbHOaW0g5pguheK6Kul8O/QFDhowFE4klTuJjn4Fqc5yC1YxGVfa+PA0Z/geGbv04Hmta67kcMWn8Fjfi7rL2LJh6GPor6bPnKbvhaaOdCyq3nldPXTO7uC9kT9z/4Akt8UkKf4EJClW+9dQpxC+XVfzKhknYgOZdKFPaL3HkHpnxJaLzlhb/KzKhz6C5jYdA3ek1Lca6itDOB58gppfyxHinAyFvzOFzr/Xf6SZ4H3/EZnJYPHZuHRCLCZkRh+IX+nKmHaCt4msjA1QqO1HiMNQl0acm7WlBY0CbBQG8ZHoPMaB3rfiuSLsBqFt8r0Ad0FcnpJ3fSYQFsh86yZ8HH6GC5RzTXtNshU1E07JUJ6Hn94HT8ga6XcwB1l3dx4npTzoKOoi/Pd/iNQOJM3ZQjc7Tkb3Wbd0k0LlR5AZhEvXfkzUjVFWhqG6SpOoum5HnjikyE02HEI+kS6n0+cRQvh6Gw068j/EweMz2f4hrnJFpfEwyEAwJYRvwueDCtetJcFU0kd0jBlAyE7jauoCspqaqi0a+ykOIh8djUb7iM3+9iGNzV46SrcoyGJ/GsQX/L07cJ9rWeFthbcXLi8Ub99+8WGD4zxdBdyINr0aSopMO69dTbQ2H4TmNeAVadP5A2vzrj6o/xZH/VIf1E/FUf+5D+r/iKP+ZR/U6+OoH+2Dem0c9f19UPvjqO/qg9oTR13bB/XSOOryPqjno+PunEN6c3Eo+8GUVXmZXNEDs7MzIlEYOdR28JlqNfjOD9AOtARvfaIiKEGCnZ9oCAYfUxFMQYKzWoLt6iLSkOCv2iJeiqgIPn8fCH4X0RDsUBO8igTPagmau1QEf0ACf5eGYOg5FcGDSIBbwyoCr5qgBglu1RL89mMVAY8E//7xP7L8/qPvVHw45DP3O+q2nrwCG+tTXHf3mpSvqt0Ga/NiNAJwZ9aW+cTzal1a8/g4G8F5rZGNfEyCpLNYBowNo4BvRnA47tUSlzfnXTou3fgudT5kHdg1FvL92oRjHqlYo1KxnmSlYl8kJ6hYvyR9xd7rw3h30QLI8IX+b9l7oKTHkrG2XbS21uY2WmCGteV5UiCr9YYjpNaRnwOyd/AeHNP3BiZV9RHtBk1MwrVj6IaHSDY8fqTf8JBuuujIobfwS96l/rzrHTo8LCfDw1Ld8PBPFfHMERyBzsgPvBONKgv21uabYq0zPb51/qnyCqi+5Yx3VGv+kdfNibU/lFEff1s7B4vgXGErOiv5v47Q3T94ephj0QnUN4yxcscwbCZEy5veplaJwJYumLq8iMev5EIVmux/yn95VxMMdb9NVxlaotaWs2YkouU4YC5zaTIxu8hN5ph9s91+a/Mks6LBceYE9p2VrLfvqNnYvo+b2eYylvYkin6yvICTf30YzHzvF/Bn2PfRqPwbBM+dxvaEWAt3vtLxLMhEpQe0xHzBjxP5guVxviC3jy43VunTVB1aVnh4XstqRpIxq3FJ6t77gfyLt2nsdPAdTMmedG/XXgcPI8f6a3OsBCQBMJZajhSBlF6Nxchm45NLvydbl3EPJ+DDn52jjnXeGG0BA/Dh1WQa2ylPpg+78hDIHEORGSxNH5PYkvnD1JIz31KCxzl47qRpja2ckyZgAF/OR/kMjOnwK13bS5G/PITdEojkz/AbkKdz0lSkSSdrgRPoV0pO5gHpZD0wRf7tWzRnuvwnlnMiJ91BJ1FR3hIU2XzqX+etPKzEifJ1h+jKZQZOKm1YUZhPBEcxpztw3Y9JDVPeoioZfEgVrZYPp5u+h9GYJ36nGVAfMqsWrs5ArsgaszLqxZpKfItE3NbmV/DwUHQhmHs7ftMt7zSnm/U2+mkfNro/qbfr44kklbfRH9sgcyGNUus1Sp1npNS8REpNP0SVJL+pPR4U2XNepRtVhg8OgrCdqVxlARmjZPRkxFEueQu1MBZcQXAyiiITl4czrM3J+D38XDLKgXOsP0ChXVegs0k10TnP6oO0jUim0Ps4VTt0kIYl3Ww0xBMv8i8Pabzns28qU0lryygTVSHS2Y9E8hQHkvL5ZJjKhZQKDT49mc3sQutJvVBqLCMdZ4mQP8/E/ets9q9MrVhAPWm3zbaJUIBczYyyAIFJB+kgWQTp30zEus5jixPr+pqsmOqs6y1Ob11/6iOwepzrVQ2baR/l+phpa8saFee4v+yjrHe5xA7qt2/QqejaA9CvHj6T2Lh+wohuBaLmI/RUwI1v4rITPSdYjDs9f0N/DoGKteV3+O1fGKyY36DtcGQ/bbVnlM5QkJRYqAMHyGJBeJLGwh6d9L9oYQsPGFhY6psqC9t9QLObctd+1ZZnMdk5cMQWV7fiVqv8szfo9iffylt4sp3RJg3iQxm9q0qhYgvuh7J1WbbLIAuhORYSDrzPKeEAPaKmCwf+HmfBrcZW1fVj0pWVLZfr9rHxGEfsvfvJ2oq1+UUcXEmB5BCtvsDn4kL+B/twyEGDFj+6j/rLTa8TN5gDbnDLPjeEe23LC8gSysn99IzcUvWgcTUiIXx7mh3WvIMsAVX+KwPfuaxiY1+n9vC0cqYXit34P1fsvtdpsU/vpcVuVBW7gRU7gRQ7LjYnOsGqKrE8yvFjepw2eAc9xhELIpb+K4OIzNdpELFUPv0aDVuqOWvz8TM0oKjGUq0tR2Lgv7Dkp/bSkqvlNa/RALRsHznTBoNV/+8S+0P/XqqpeZAj8s63uAWuP19u6Yfj3Dd86HpbIS7TWZvfxmlD+O70LftgGmI/QLY9ZB45NfXAyIK3R6iGUN9rsdMThuc323k8PBfC7dGu/lUbhHs7yTF2ZWt1rdCa3I+/AWcYW/AHjoVW5xmy5B9Ox1A0XZ7/GjkIaW3+iXYL6KtXleGbHlubiMemWiVc2X3UJqfieP+awSluqA8EpaEvZPF1umR5NZkf2+IPBL5qogcCU6Ewdr6B1C1PzgWdQK1a8knwlWxzhnNwNAlXy8DwJXaI4L2mxh6ucSB27Tf3YoSTijMfC9/qvDz64GiLSporX1V2EQs3E3EmWbe8QY7B4w5H63pbN0okvhq/nSWEThSHTqpYvfOKTjHK8SdUTA+yeeDVhIohK8ThW2RnOMgVt9bJwnVL5KAVj/Fd+hoR9tHtXUlky03KIAobyg7i7gwuRSV9uIeemuxHTk1Kw5uP4EG8ydr9a/1RStwSmIUG/eQeHLZxbd5ibT4EE6HI+2RDs6P3YGk1PVhaaG1PhQEzuR85WYpJ1y2avlWl7luEjCZdZRqyciOyBYXh1FY+WhhKw5Oq46LY405iv8Jfo8kjQb+RQVFN9H8dO4VKCL4FSSJZWoK/f68iOIwE9AQFKOPeHdgNVcvfuGKAWwbkBwnkWHVHonPazTfFDUrDdYOSSqgIR2ayHV13wx9l/Ota2Qt8ILez9ltGT72WxZ16bT71g8vk6hL/RqLoXv6uPUziMAkEaohnd1/EgKJuI72bJIpdu5u6vFt2sZI62RmdM7INWo0uygzYQ/tHp1mZh2QmK/OQvXto3EMwf8OVGPzhmXz/btp6E5PpdAIv55MX7dFMJ9y7ehdjlrEZGdLhYsyq2IpQ62594Q+kKIXfzAonmDew8EtJfVnhG1LYyh6k8sHdmsI/7ewtfC4rHOmwcHd8NEKUtWgXXcC7GvJGKuNnbIRo8i463KQg0U140AibNFJBmxbC11czafiaSdbiBh/M7A1fCQqGaNSaEr7WJ+vXY/4aF8vdzxnaVFeQlrqElYqqglJFVakEhYFBSm+ph1N0QfNajZH9yKi0uYlUMrKTRh4olhI0l6NB7N9F268RgUeBquvGRPnf6WCRS0pv/l3Ypv/G8h9FoKyTmrKXpVInnV7cRkybmhab7OPXC5rsW5v/Eqfslj6UHVDMiBWEXy+woFfjPMWv+vAUrabEJvqXnWSKVD1GY2N3jrk4G/unXMo1Ow1a++MOVWs/tVMzRbplxw9OkaSOBFMkZygPN2SThehcoykSHyqykEl+ZZIyyb81KcEk/4a4weGSPgaH81BK5F6DVsjaQVrho9GaPtc1+iL73D/TCk9tN+gzt+9U9ZnMHZpW2L/tB1vhix3/ZCsMMimtkGRK0ArH4vrbS8b9LfIUx7yqMld9uF01Vx2/nS0eHjurLB4eOZtg8fD3cWWu66OP1yVS98xtdCnF2o5qN5fjRDUTJqpd1ySi7s+oP2wj1NppLdlP2Z54cNnXTjM+DRkj1rPk97CFS0r5phMZQui8EF6eiXHCJBInXBl35OH37Oehd7ThbHoOPb8ZXp7RV56fsTwzaJ4Mlie9rzzNLE8SzUOD7vAYzDKeZBkdm5wu3Ead9Vtb6TonvZogY1nhcu2ZhsW9reG0JYfhX5egIbhZTTAICAbhuS4VwQI1wTAgGNY1SxVufkLOQ+Ta5FpU7aHzmlj0LHko2SzyQnx6Qvt0SJQ+TZft+DQJQHX8rpo/kmY64wxPwdOvxdd50qVMDB/TwCKFULJN6OxHjyTusBSHPJbI2zgkbFFO1OJBWmfoQ2fWl3z7t+aXSf+yOiK86TXrI+34e5T24zdY/32bZQ9gv6BdeAyf/431/l+SBTD2A4bsdjzKCNMVqIEz9Kkz6zQf+pJv+rCHN7VLg8lvK4awehTnf2ptfoK0SEcP3/6FmY924PkxJDfBNNUZOgWzWOj/kC0N5qus/YTWJRbqHWbDxK3pfJJ/oe78+G5pMB6LC5n4ziS6+zoLqPdCMRbc9bgLgNXgQ2ZZqDngr2I6LEL+Diw6tC24pRimuT3FWWeE9pPmrhJaTutSS+R+/cmuS+LbXOUsp9NGWwMa7spSz7fGxP+0TzHu4H+htWa9HLNWmG5ZivO/Du7GFQzLvNbbetLxVyDYrBYMA89vposbeMYYXNXtUNNkGb6nUzOPTWHkxVvj1htKoE8Xh28kLuxpukKdYW15gtRxLP6ki8/vkhoKN2PduvKMJaf9RSX5BGLpTSBF1+gNzvCkYjyEJOAEdbTAJk3O/M+Cf4JJnHzDZuKjlJPUfP57wdfoxoNkQV1cvpm6pOGb1T3YohJN9/uKxeiw7j2xjgTE58kSQAY6OLxhJPYL9plQNz7/5wQpDYIZH5KDV7h9O996m81Cwn+kWwiNtyWEkX8Wwwx+mSwb0CkT3YCz0I2RNcmWsJQ8EbdEHkfRM5C8bjPdwbOwfZC9AHc021ZBcRMoHqqG0IvY4eS/bFYmRd9spjvVdAHlepssAc+C/zahajHs/M1L+EvdLXj71ot4ZSniCl+mc5lwSuewTI4abnjwG8OUuMCZbMFd9HQaEdBfV11QOLDGRMYnTOLCgUZckf7ZS3SDPp3GAmtsvFz2MpW8XB65mTrhqbR6XbeTOmqnsv9U6ZdB6QXNMEFPitKY/DAgIt+cJ+NXKR86G5vd/dginyO7th8sizz5UsLn79LncvNLjO7/vYAON2Zfevo/MvoyhX5l3/RrGL1Nob8O6WPkG0rkF+GJ3PJiov56Rgid47f2uuxcmxAuQ+Paz/z2S8xvv82bXiF++33wrOC32yy7APsB+8EZOO6zq1bHfhy1+iX2O1LGzpl1ig8dJD+46P0laSr54ZuF/KKC/Zh0CNRRaPV+3vtjUt8m3C+/xiaEvOCSWme/B30Qt5y1PVbe9WLv739AvFC0cIkQOl24WAgdLCxztl5ZPjiTW8y3Tq6GtNSZdcx+hFSm6YRFbv07XSEc0/t7n+NQl9nAIzrsXXAhJvBaweOkxNuVIrer2uOr7ezOInZFEd7PN6XS0zAlIFXW1HENHrfk8197LbvMkbtrdeOqhqAU8N9Z76ur9a68o6Z6RZWn0l3hys+bOWN67rSp9hz71Gm502fMzMt3VbgrPVUrqmvuWOmtrfPV3+kPSMGGVY2r7+IyB3Dq+zivvTYQrICvOiTememrAyjoljLrgl5vZp1PymxweWsquZo6kmZ6aySP3+XNrPL5M72+uhUTszJX1UjVmXiZZKY959oJnDBlYaavHojwFslM+J/c2liZWVXj9XD+SdwcSDPHIUkd4YKX9kLxXJEv6K2smyCxJ0jFcQvsU8W5zoWzCp2iuEC059Wvlqp9dTXu6XhZZsCes8TlDXoceLclveXvB+inlUquukq8z5Rl6Zs+36HchqncIfhD/GeBGtSZ0tk9gRsqCjT3D8buS2PPy9nztoqChM9zGP6owXNOwbu1z/uu70xhoUp3FyDfDEddQ40fTNFTJ+lyautT705cH+V5AcM/o3seuzdM0cdyJjdL9fdmx+4Nc2vp08W+6TN19AU6etMo83WPsjsEd/0tGsU97mro/BkQK4Qgxe3cRnA3meDxHoAUT7DKn0ajGxD+KhrFhdCJ38BziAGXnoHnkOb1wHOch38XjW6CtBrSfZA+DqkM6S5I8bJHC0x9ZOQHaQ7AS8FnN7JLIIcp7xm5axFnakw3jRrUz7LB1C99GLvnb//z0aj6frrE9PROPaQ/+mw0uhF5p6XPScuYZx24yrKOu2nkdVdPs41X5zfr8ivllYAuyH2QhWnp6vehmO8qcZIc/cx4JbhZyZfL7vObCPmWZXNc8qDqAsw7Ky1jVlrmrLSJs9JyCtPy5qZ1D2/qtz61NeWh5IfN9yWRfLeR949Eo78YBPmW3pE4X1uaJh/WZweuSX0ZjeJZaG5WWnphWsbstJwm80NJtD6f4P2E30ajh5kcOp6FaQUaluSD+UYjP2jrSUkJ881OK0mcrwzy9Xwdje6/iPJQZ7dBvo1gU4MBl5yzUpG/MC1zbtpGc1PyQ0CN7fIc2iDY3OWMf1MSbS9chNsA+Ct1+E8A/3QC/DnAtyXAD0Mbfi4aHadqd7yT1Qv4Z8DGPRzV88NJjrSMh8yOtMzWZEfaxPUpfFrOfal8Wl5Tv+K0Ai9KCvJOJLKDBkAWC+GPu+uHgU+Srs9GzTub163jzJuTJ7HbN3+K97LdwYA/IPA9uzfThDekNZjopZ478cmsJErmRLu+hb1eoAyBrxjw3wiMNVOyzzCPiwEmVP+TZnpl6RgATPvZffc8ArjqiGR7UVN4CvWnyhWvuCiFd/HtHANkx1NodV4bw15sgXkOIzCnH2W9lFxnCjPDR/AaWry07lcAVMdeTtCfXtZ6KV4X6BxIGVyFdds2hF6/uh9FeA2AptiFlkPpk+PIbdsltAYHEei+hIogISAOo6yvQ3nuZEAJAjcMp+U8jcLtGEGvMS3CQk+MYLVGsm8BeExpsYcv4zicrx7F6oyA9jio3D3bNY7eA8mjereNp5fJklofGk9vriV5jsCfwcr9tvJVtKIT8Ba9zAn0Is8QAiL8KVeux916NeVWhtZxchLNc002M4ZbkzRvaoqa37iXM+8jwDuKrt5hluTDkvubqBKw2TmJAd8j8DsTvbM1Ccm+MtE8VgTwPjSLUp909qqHApw2jk+h94DOQ2BBiuoy0lZGNguf/Bcja0PgFQD+rnD7SX8q3Uj8YxlIgY3YskPhT9gU6yP7OPMC8sYlpQD8Uo+PEGhX33/7Brvk9wnM/QG7yfVJE6NNM3H/9/m/z//Mp429v+0oe1/IxtHaOM1kkB5J0cLHdHASu3dcuXM6M4PyVe6afrOcwpcp98qy94iNUr33ilPdvSyz50pco9yVDdN7H7lXN6kgdt83kat/Qey+cxoIUVi5M/s19kC5K1u5+3m4Tj+xO7/ZvcyK91qaoo3rFL+q3C29a2iBBt82pEBTbwtTVH9d+eejVJ5MRh9lsFKPbgY/lF7wv2onsffY6T5LWLtWsbSBpfex9DGWPsXS51nawdJDLP2UpadZmsri/xEsvYqlM1g6h6VLWFrF0gaW3sfSx1j6FEufZ2kHSw+x9FOWnmZpKnv/zwiWXsXSGSydw9IlLK1iaQNL72PpYyx9iqXPs7SDpYdY+ilLT7M0lfXHESy9iqUzWDqHpUtYWsXSBpbex9LHWPoUS59naQdLD41KbEdzi4quzZy4uCJYJwUzc7PzsnMnTw0SyH6PPTc7Jzc7N4viOUbk9rrqVmQ2ePwBXG6Ylj09O2dyLs0y9R7JHwxIq6dmTpRcKwJTFjmcjsJShzhtes6UKnyfRlbmRFy3qMRVCqdzSTHNnsVx2YHVtZKrAlLJT9Nq5VtNneTx13PZdT7Jk104S5gMrBm0oi6YXRGs8VZOrqnkCFTtClRz2ZWr64AfTSU/fcIqrAFEeOb3eF1IyL7VeyUssgb+Sp5G+Av1roFnvkqX5OKyPdVild9V6xGrK/29EDB1u9m7TESJvB6J8BBdfr9rNeWhfL/D7ScVc9XWuCGfTyJ/aLm0jIpAgMt2+2pxzv9P9+dRzFcr/qz3vZqcxs/qxwHlc4XuXQm9763kNO+7Uj7JOtiuyy+x/JJqntVXfpznnAZfqORX/P/jDMFeixkbDyy6/AuY70/SjQ+Ko21j40Mqk92i89NLGGmSbrxp668dX4z0t5z5diW/4s8fYgPfBl39da8P5VaysUKBlfEik71sQTmzm8rqqZf/LqbTJN341DZEOz7p9afI36zLr4x3u4Zqx8cUFgPo8z/E9b5rVR0fZGZox32j9g/p8hew/AUs/0azbj1Mlz6qy6/EP0dZAHJqduL8yuc/dfmVeObNcu24blT/jbr+d5TlP8ryP27uu/yndfl73//aK19f5T+vy5/uYet1Hgqf00369fbTpsuPy0c0ZfUx913+AfZ+EbMu/lPeL6uXV1/+++w9JGZdfCjXJqbXw8dZ/WNxFcvffYH5T6r6ljo+Ut7/qygmVZdfkatHV77yfp4eX9/lK+n3uvxKfEpmmGhHpr7z44+01PmPsvc6HL3zwvQ/iE3EY+Wz9/x0s/wWXfvrx4MhrPwcHV7Jf5/B+KOkQzjt+3iUT4Of+Q9T3/5XbbvqT8mP2ftE2EtucFWoOIH/6m9Q/jMPMv8wpO/y+/qYgVoZj7X4pNg4q8WbY+OnFp8cGxe1+JTe8U6DT42NY1p8v4TzDTNoRRl3tPj+sfFEix8QGye0+IEx/6/FD4r5dS1+cMxfa/FpMT+sxVtj/lWLT4/5TS1+SMwfavFDY35Oi78k5r+0+GExv6TFD4/5Gy1+RMJ5lhlmlYp/0OIzevu9Bn9ZrD9r8b3vQdXiR8XhTMRnfxnV4+k7dOL1cCPD43aApj8xPC6Tqz8VpP/1tuM4VVxignqm6N6n+jtGr+wPXalaKiR8lmvxuGiGeGVfSXnH0iyG55ZS/KOsAC/Db/wRxU9izuGvDJ+uK/d9ht+3jOL3M/zUJIovn0/xv2ALIG8x/DO3sXUQxj/JzOpzOcUvYy8dwhsAUA/JOj3kELw1tm+m+KNyhlf26xT8Txme09F3MPwzOvw5ht+nw+M5W8Qf1fFfwvDKvqfyjqX7GF7Zb1XemfQCw+fo8CcYXtmvVN6BhOu1iFf2KZV3RC1geGW/VtlrW8PwJZVa+j8yfLeOzwcMn6mjH5ia2P5HpCJ9fP+9IpW2Y45u/SyP4ct1+PkMr19vc6XSdjfp2r2e4OP9yc8YnzYdnycJfbxfMpJrG6Efwll0/XqfgbycgX94l9DH+6VTJBC6JK7+5n4Ur6/niH7IJ94fju2HsUS8f7u6X+L3SAsG+KABfiPBQ79m44USIzzD8Cadnv/eL/H7pU8b8B9lSfx+8qsN8DdaEvNZZMH3tw3m1jG/dJjhHzSg/60B/jDBx4+b7xvQm/snxl9qgL/aAC8Y4IMG+McM8M8Y4N82wCcPAL0lDebqmd6U9d9RAxK/r3v5gMR87hyQ+D3ejw1I3I7PDsCYtTcOUeZD7Qb8jxrgTxngxw5MjJ82MHF9igdijB/fj2414HPfwMTvS/+DAf2bAxO/z/y7gYnf6345jJNDki7junX1yRpkYD+DEr8XvdyA/m7GX9bxf9CA/olBtL+Xs/Zi02Luzwb0AwcnxmcOTvy++hsN6MsHI83IOD14DejvH5z4vfebDejfNcCb0hLjxxvgi9IS29VSRr9xpNZO7jHg84gB/ikD/EkDvMmaGH+ZlerTEtTqc4wBvdsAv8pK9ay8h1bx8381oH/LyuxT0vqT1PTE9LZ02h/17T6J0Rfo5jtOAz6/MsD/twF+vwE+YoDvN4TKxenik3FDEtNfa4C/3QBfb4B/eAjtj92jtft4jxJ8gvnjFL/PJ02pX+2S3L5Kj39Kvd9X4fXUBqa4Ktz23GlT5kzBV1Rnu+vryRuq1Yv09jjM1DhMHhc7nhcIVoiCGOMm3mp0ds9uF0XclpBq6kTRmbvAV0dfIn/BRytn59D3gF/M2cd/KM/UC8iTiydDL4zSWxOQhAWldnFaQPI7HPn1wUC1WOFyrxRKp4kOR8PCMvEHmShHJH9InqBU4wWlBapdfk+l6PdUCaXSDHqcF6qQI1JupCKlLqF0OpTvUKSYfyENR+SeWRWsQ5Z5eGjWW1PncXuFeYt6+RMiB7Iuc3sD/j44OWIsAvVICjWrdMys8vlXufyVQpnoqKonVaxfWJov9lXJXsHcDV5FnlxRxOd+Vx0x0On4Z6qbPi6VnHmiWOMju1rirWXCxZzxvQB6/RncC8miOxZ8AVkSnIT94Vy9521/mDZfK0LpRWqp9OK1VHrxWir9h7RUehFaKr0oLS25SC0tuXgtLbnQyrv9UkAKVlVluzlRnFe0SHQKpWWiyMGo4FkBnsnjF6Va0e0FdxzgEqBEsdInrvD6KlxesRL6fEB0BRs5t6+23uuRPJXZM/LzpiYmEns3eEVQvH81RzeJK4O1tashiwoSe/eFGakozllUWOwQHQtmQ2Vpzdl3JvXCOXNKHWViWeEspwMpNCwqtYiA5PJDL5/9owWFxUIRhzvKCu7WBaWBGa76esjjKJnvri0omOsUZhUtXSpOy84lbqQUDAhEqRS9roAk1vkk0VdFSONoS6WpOaIIDse3SvR66lZI1aIHWwGIdaSit6bCLboDQaIkLlaZsiWlkn26+vcQFcEqwQ1Iuxt8uij5XTVSQHCj93Y7HPEVsM9QKlDhqhTdUOMGfdEran11tEDU5rwGcRFr9SIQMIBNfmult6QhThG9I4kXSvc6HPZ8sVj0gCG43B4yoGGrw0AwH545GsBn04GtNDCT/ZDEkUi70nQ3miyIY58G/FbVVHrqSNs5tFXItts5pi2sS16NLyDisYlcAWiL7Dpqrtbl9foUtYtTs6dmT+eq8DcdWhRrCaoOHB90j7H6uaCh+nz8WQoMVhJIUbtoPtG/Xpq6VfhEygcbIU0g6VXvbnSJwKGxRoovRrJP8wfrpBroE8RoQCRgFujLxnxBtEURxrcVngQ2Rs6kgA14vSK0bm1NHRSNNlYGZeVTG/NRI4O/HlfthdpZ1QqPFEgggLZJZsc1iSiUFYu9fqesuAhdTBk5GSIKC0Xy4yMxGPBUUr2DBmrdCVVd5fd44iqAHXUm6ahVNf4+eyqI640zBKxc4qqJen9BDMKeI6I0wMu32mFgEGje+R7FceeuqnZJjoaEHmaaquJG7iVWsh1skbWoN67MMiHOlPSGAeIpzpTpGcozEKFUynWDncWj82M2FedhKgM+sRoGaVAenlfyeRP2OfR+LPqifstHzRCQ4C2kRNboWISy9ZouGi0MATmio3SGWDIf4mmv1mfkc7We2lpfQ5y1oJZ6W0YvHfq/vntyRSCgsgjf9CovRPXxbYvjdA72+0ZXRU2DHbtuoAY7JmRHrweyVvlA55CjcJYg2rOn6boSBucJvQh6N9C9qJJBz6RXPiMu2I+MOIj1IDoE5+JKz2rm+RL6qfh+Dip319ZrNe5O4I5pJWlrgrwJG3y62+txwWRFgnBHAJ3APwlqonMHHl+V3sRQPNJ2WqlIaED65UUMs2S+pBOyivyeMM6stOM32KcB40RD90z10E301WDkAsCQSnHolVaDz6qHonx+1wqPI1EbV4BPq4NRQHJX61RBDtZBPNDYKNZ7/AEfeJMaYNiQE29KFzlegEdBOyEtthDG3FpfpSfBYJlAOjbqxTm/xXWr0EEu8gSCtciqqAjwOSwswa4As/H4AQe0OpN14fiyfNPqg5LDnaASYGvFEMC5VoIXg3lGAvOuX93b8vZcbRQZP2pjXMFRX/f/AfXmFvJKnAAA'
bin = gzip.decompress(base64.b64decode(gz))
p = os.path.dirname(__file__)
pymain = os.path.join(p, "a.out")
with open(pymain, "wb") as f:
    f.write(bin)
os.chmod(pymain, stat.S_IRUSR | stat.S_IWUSR | stat.S_IXUSR)
if p == "":
    pymain = "./" + pymain
subprocess.call(pymain)


# compiled by pythran
'''
#pythran export main2()
import numpy as np
i8 = np.int64
i4 = np.int32

def push(val, que, sz):
    i = sz
    while i > 0:
        parent = (i - 1) // 2
        if que[parent] < val:
            que[i] = que[parent]
            i = parent
        else:
            que[i] = val
            break
    else:
        que[0] = val

def pop(que, sz):
    if sz == 0:
        return 0
    ret = que[0]
    sz -= 1
    val = que[sz]
    i = 0
    while True:
        child = 2 * i + 1
        if child >= sz:
            que[i] = val
            break
        if que[child] > que[child + 1]:
            if que[child] > val:
                que[i] = que[child]
                i = child
            else:
                que[i] = val
                break
        else:
            if que[child + 1] > val:
                que[i] = que[child + 1]
                i = child + 1
            else:
                que[i] = val
                break
    return ret


def solve(A, N):
    count = np.zeros(N + 1, i8)
    for c in A:
        count[c] += 1
    que0 = np.empty(N, i8)
    sz = 0
    for i in range(N + 1):
        if count[i] > 0:
            push(count[i], que0, sz)
            sz += 1
    num = sz
    ans = np.zeros(N, i8)
    ans[0] = A.shape[0]
    work = np.empty(N, i8)
    for m in range(2, N + 1):
        que = que0[:num]
        sz = num
        x = 0
        while True:
            for i in range(m):
                if sz == 0:
                    work[m - 1] = 0
                    break
                work[i] = pop(que, sz)
                sz -= 1
            if work[m - 1] == 0:
                break
            x += work[m - 1]
            for i in range(m - 1):
                if work[i] - work[m - 1] > 0:
                    push(work[i] - work[m - 1], que, sz)
                    sz += 1
                else:
                    break
        ans[m - 1] = x
    return ans


def main2():
    stdin = open('/dev/stdin')
    N = int(stdin.readline())
    A = np.empty(N, i8)
    for i, c in enumerate(map(int, stdin.readline().split())):
        A[i] = c
    ans = solve(A, N)
    s = '\n'.join(map(str, ans.tolist()))
    print(s)

'''

Submission status: Wrong Answer

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions
from operator import itemgetter

import sys
def input():
	return sys.stdin.readline().strip()

N = int(input())
A = list(map(int, input().split()))

num_dict = defaultdict(int)
for i in range(N):
	num_dict[A[i]] += 1

G = []
for num in num_dict:
	heapq.heappush(G, num_dict[num])

ans = [0]*N
ans[0] = N
n = len(G)

x1 = heapq.heappop(G)
ans[len(G)] = x1
for i in range(n - 1):
	x2 = heapq.heappop(G)
	heapq.heappush(G, x1 + x2)
	x1 = heapq.heappop(G)
	ans[len(G)] = x1

for i in range(N):
	print(ans[i])

Submission status: Wrong Answer

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions
from operator import itemgetter

import sys
def input():
	return sys.stdin.readline().strip()

N = int(input())
A = list(map(int, input().split()))

num_dict = defaultdict(int)
for i in range(N):
	num_dict[A[i]] += 1

G = []
for num in num_dict:
	heapq.heappush(G, num_dict[num])

ans = [0]*N
ans[0] = N
n = len(G)
print(G)

x1 = heapq.heappop(G)
ans[len(G)] = x1
for i in range(n - 1):
	x2 = heapq.heappop(G)
	heapq.heappush(G, x1 + x2)
	x1 = heapq.heappop(G)
	ans[len(G)] = x1

for i in range(N):
	print(ans[i])

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
types = {}
for i in A: types[i] = types.get(i, 0) + 1
A = sorted([types[k] for k in types], reverse=True)
for i in range(N):
    if i == 0:
        print(sum(A))
    elif i >= len(A):
        print(0)
    else:
        print(sum(A[i::i+1]))

Submission status: Wrong Answer

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	A = getlist()
	D = defaultdict(int)
	for i in A:
		D[i] += 1
	a = []
	for i in D:
		a.append(D[i])
	a = sorted(a)
	n = len(a)
	S = sum(a)
	for i in range(n - 1):
		a[i + 1] += a[i]

	print(S)

	for i in range(2, N + 1):
		if i > n:
			print(0)
		else:
			print(min((S // i), a[-i], a[-i + 1]))



if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
c = []
hoge = 1
for i in range(1,N):
    if A[i] == A[i-1]:
        hoge += 1
    else:
        c.append(hoge)
        hoge = 1
c.append(hoge)
c.sort(reverse = True)
M = N
for i in range(N):
    print(min(M,N//(i+1)))
    if M > 0:
        M -= c[i]

Submission status: Wrong Answer

Solution code:
import collections
from heapq import *
from bisect import *

N=int(input())
A=list(map(int,input().split()))
c=collections.Counter(A)
l=list(c.values())
h=[]
for i in range(len(l)):
    heappush(h,l[i])
h2=[]
for i in range(len(l)):
    heappush(h2,heappop(h))
s=sum(h2)
m=[0]*(N+1)
for i in range(N):
    br=bisect_right(h2,-(-s)//(i+1))
    if m[br] != 0:
        sbr = m[br]
    else:
        sbr=sum(h2[:br])
        m[br]=sbr
    print(sbr//(i+1-(len(l)-br)))

Submission status: Wrong Answer

Solution code:
import math
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


def get_primes(max=None, count=None):
    """
    素数列挙
    昇順にソートされています
    https://qiita.com/Ishotihadus/items/73e107271275611f05f2
    :param int max:
    :param int count:
    :return:
    """
    assert max or count
    if count:
        raise NotImplementedError()
    if max <= 1:
        return []

    primes = [2]
    sieve = [False for _ in range(max + 1)]
    p = 3
    while p <= max:
        primes.append(p)
        sieve[p] = True
        if p <= math.sqrt(max):
            for i in range(p * (p | 1), max + 1, p * 2):
                sieve[i] = True
        while p <= max and sieve[p]:
            p += 2

    return primes


N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

primes = get_primes(max=N)


def count(k):
    if memo[k]:
        bc, ret = memo[k]
    else:
        bc = np.bincount(A)
        bc.sort()
        bc = bc[np.searchsorted(bc, 1):]
        bc = bc[::-1]
        ret = 0

    while len(bc) >= k:
        bc[:k] -= 1
        bc.sort()
        bc = bc[np.searchsorted(bc, 1):]
        bc = bc[::-1]
        ret += 1
    for p in primes:
        if p >= k:
            break
        if k % p == 0:
            memo[k // p] = bc, ret * (k // p)
            break
    return ret


ans = [0] * N
memo = [None for _ in range(N + 1)]
for k in reversed(range(1, N + 1)):
    ans[k - 1] = count(k)
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))

B = [0] *(3*10**5+1)
for i in range(n):
    B[A[i]] += 1
C = []
for i in range(len(B)):
    if B[i] > 0:
        C.append(B[i])
C.sort(reverse=True)
C = [0] + C
# print(C)

ANS = [0] * (n+1)
for i in range(1, n+1):
    t = i
    while t < len(C):
        ANS[i] += C[t]
        t += i

for i in range(1,n+1):
    print(ANS[i])

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[int(j) for j in input().split()]
from collections import Counter
c=Counter(a)
l=c.most_common()
ll=[]
for i,j in l:
    ll.append(-j)

import heapq

for k in range(1,1+n):
    if k==1:
        print(n)
    else:
        ans=0
        q=ll
        heapq.heapify(q)
        while True:
            if len(q)<k:
                break
            t=[]
            for i in range(k):
                t.append(-heapq.heappop(q))
            m=min(t)
            ans+=m
            for i in t:
                if i-m!=0:
                    heapq.heappush(q,-(i-m))
        print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a_set = set(a)
b = len(a_set)
c = n - b
print(n)
for i in range(2,n+1):
    if (b//i > 0)*(b%i != 0)*(c > 0):
        print(b//i + 1)
    else:
        print(max(b//i,0))

Submission status: Wrong Answer

Solution code:
from collections import deque
import heapq
import copy

def ans(q,K):
    if len(q)<K:
        return 0
    res=0
    qc=q.copy()
    heapq.heapify(qc)
    dq=deque()
    while qc[K-1]<0:
        for i in range(K):
            dq.append(heapq.heappop(qc)+1)
        for i in range(K):
            heapq.heappush(qc,dq.pop())
        res+=1
    return res

N=int(input())
A=list(map(int,input().split()))

d={}
for Ai in A:
    if Ai not in d:
        d[Ai]=-1
    else:
        d[Ai]-=1

q=list(d.values())

heapq.heapify(q)

for K in range(1,N+1):
    print(ans(q,K))

Submission status: Wrong Answer

Solution code:
from collections import Counter as C
from itertools import accumulate as ac
from bisect import bisect_left as bl
n=int(input())
a=C(list(map(int,input().split())))
t=sorted(a.values())
s=list(ac(t))
s=[0]+s+[s[-1]]
d={}
for i in range(1,n+1):
    if i==1:
        print(n)
    elif i<=len(t):
        if n//i+1 not in d:
            d[n//i+1]=bl(t,n//i+1)
        c=s[-1]-s[d[n//i+1]]-(n//i)*(max(0,len(t)-d[n//i+1]))
        print((n-c)//i)
    else:
        print(0)