The sequence is generated by the following scheme.
1. First, write down 1, 2 on a paper.
2. The 2nd number is 2, write down 2 2’s (including the one originally on the paper). The paper thus has 1, 2, 2 written on it.
3. The 3rd number is 2, write down 2 3’s. 1, 2, 2, 3, 3 is now shown on the paper.
4. The 4th number is 3, write down 3 4’s. 1, 2, 2, 3, 3, 4, 4, 4 is now shown on the paper.
5. The procedure continues indefinitely as you can imagine. 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, . . . .
所求答案为前n项i*f[i]的和，f[i] 有i个，所以1e9大概需要算到5e5就行（参考别人的思路），
upper_bound查找（好像是二分查找），自己按思路写的最开始用的for查找，发现比别人慢很多，然后才注意到这个函数，以前虽然知道，但并没怎么用过- -。
预处理：sum存到i时数的个数，g保存到i最后一个时的i*f[ i ]值。因为n找到后不一定是i的最后一个，再填上多出部分即可
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<stack>
#include<functional>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int maxn=5e5; int a[maxn];
ll sum[maxn];
int g[maxn]; int su(int a,int b)
{
int ans =(ll)(a+b)*(b-a+1)/2%mod;
return ans;
} int main()
{
a[1] = sum[1] = g[1] = 1;
sum[2] = 3;
g[2] = 11;
a[2] = a[3] = 2;
int cnt = 3;
for(int i = 3; i < maxn; i++)
{
for(int j = 0; j < a[i]; j++)
{
if(cnt == maxn)
break;
a[++cnt] = i;
}
sum[i] = (sum[i-1] + a[i]);
g[i] = (g[i-1]+ (ll)i*su(sum[i-1]+1,sum[i])) % mod;
} int T,n,i;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int tmp = n;
int cur;
for(i = 1; i < maxn; i++)
{
if(sum[i]>n){
cur = i-1;
break;
}
} ll ans = g[cur] + (ll)(cur+1)*su(sum[cur]+1,tmp)%mod;
printf("%d\n",ans%mod);
} return 0;
}