U468527 （模版题）用二分法求算术平方根

**xxs**有 _N_ 个整数，他希望求得 _N_ 个整数的**算术平方根**（可是他没上过初中数学），以便更好地了解他们（无整数根**向上取整**）。此外，他喜欢用 **O(NlogN)** 的复杂度解题。请你帮助他用 **O（NlogN）** 的复杂度解得答案。

给定 _N_ 个整数，求出每个整数的**算术平方根**并输出。

**第一行**输入一个正整数 _N_ ; **第二行**输入 _N_ 个正整数。

输出每个整数的算术平方根，中间用**两个空格**隔开，**只用输出整数（即向上取整），不用输出浮点数**。

输入的整数（**除N以外**）都**小于1000000000**。 **（底下附CODE了！！！！！）**