What is the necessary and sufficient condition?

The necessary and sufficient condition for a beautiful sequence is that there exist one $$$i$$$, such that $$$a_{i} \le i$$$. Just check the sequence for the condition.

#include<bits/stdc++.h>
using namespace std;
int a[100005];
void solve()
{
    int n;
    scanf("%d",&n);
    for(int i  =1;i <= n;i++) scanf("%d",&a[i]);
    for(int i = 1;i <= n;i++) {
        if(a[i] <= i) {
            puts("YES");
            return;
        }
    }
    puts("NO");
}
int main()
{
    int t;scanf("%d",&t);
    while(t--) solve();
}

How the binary representation changes after an operation?

First, we notice that after each operation, the number of candies is always a odd number. So even numbers can not be achieved.

Then consider how the binary representation changes for a odd number $$$x$$$, after turn it into $$$2x+1$$$ or $$$2x-1$$$.

• For the $$$2x + 1$$$ operation: $$$\overline{\dots 1}$$$ turns into $$$\overline{\dots 11}$$$.

• For the $$$2x - 1$$$ operation: $$$\overline{\dots 1}$$$ turns into $$$\overline{\dots 01}$$$.

So, the operation is just insert a $$$0/1$$$ before the last digit. And the answer for an odd $$$n$$$ is just the binary representation of $$$n$$$, after removing the last digit.

#include<bits/stdc++.h>
using namespace std;
void solve()
{
    int n;scanf("%d",&n);
    if(n % 2 == 0) {
        puts("-1");return;
    }
    vector<int> v;
    int f = 0;
    for(int i = 29;i >= 1;i--) {
        if((n >> i) & 1) {
            f = 1;
            v.push_back(2);
        }
        else if(f) {
            v.push_back(1);
        }
    }
    printf("%d\n",v.size());
    for(auto x : v) {
        printf("%d ",x);
    }
    printf("\n");
}
int main()
{
    int t;scanf("%d",&t);
    while(t--) solve();
    return 0;
}

Try the enumerate the length $$$n$$$ of permutation.

There're too many lengths to be checked. How to decrease the amount of $$$n$$$?

Firstly, we need to remove numbers such that each number appears at most once, this part of cost is unavoidable. Then, let's sort the array $$$a_{1},a_{2} \dots a_{m}$$$ ($$$1\le a_{i} < a_{2} < \dots < a_{m}$$$).

Secondly, assume we enumerate the length of the permutation $$$n$$$. We need to remove all the $$$a_{i}$$$ greater than $$$n$$$, and insert some numbers $$$x$$$ ($$$x \le n$$$) but does not appear in the array $$$a$$$. We can find some $$$i$$$ such that $$$a_{i} \le n < a_{i+1}$$$, the cost here is simply $$$(m-i)\cdot a + (n - i)\cdot b$$$. Here, $$$m$$$ is the length of array $$$a$$$, after removing the repeated numbers.

However, $$$n$$$ can up to $$$10^9$$$ and can not be enumerated. But for all the $$$n \in [a_{i} , a_{i+1})$$$, the smaller $$$n$$$ has a smaller cost. (see that $$$(m-i)\cdot a$$$ do not change, and $$$(n-i)\cdot b$$$ decreases). Thus, the possible $$$n$$$ can only be some $$$a_{i}$$$, and we can caculate the cost in $$$O(n)$$$ in total.

Don't forget the special case: remove all the numbers and add a $$$1$$$.

#include<bits/stdc++.h>
using namespace std;
int p[100005];
typedef long long ll;
void solve()
{
    int n,a,b;scanf("%d%d%d",&n,&a,&b);
    set<int> st;
    ll sol = 0 , ans = 2e18;
    for(int i = 1;i <= n;i++) {
        int x;scanf("%d",&x);
        if(st.find(x) == st.end()) st.insert(x);
        else sol += a;
    }
    int c = 0;
    for(auto x : st) p[++c] = x;
    for(int i = 1;i <= c;i++) {
        ans = min(ans , 1LL*(p[i] - i)*b + 1LL*(c-i)*a);
    }
    ans = min(ans , 1LL*c*a + b) ;
    printf("%lld\n",ans+sol);
}
int main()
{
    int t;scanf("%d",&t);
    while(t--) solve();
}

The possible $$$L$$$ is always an interval. How to maintain it?

The main idea is to that for each $$$a,b,n$$$, the possible $$$L$$$ is a interval $$$[l,r]$$$. We will show how to calculate that.

In the first $$$n-1$$$ days, the snail will climb $$$(n-1)\cdot (a-b)$$$ meters. And in the daytime of the $$$n$$$-th day, the snail will climb $$$a$$$ meters. So after $$$n$$$ days, the snail climbs at most $$$(n-1)\cdot (a-b) + a$$$ meters, which means $$$L \le (n-1)\cdot (a-b) + a$$$. Also, the snail can not reach $$$L$$$ before $$$n$$$ days, which means $$$L > (n-2)\cdot (a-b) + a$$$. So $$$L \in [(n-2)\cdot (a-b) + a + 1 , (n-1)\cdot (a-b) + a]$$$. $$$n=1$$$ is a special case, where $$$L \in [1,a]$$$ .

Now after each operation $$$1$$$, we can maintain a possible interval $$$[L_{min} , L_{max}]$$$. When a snail comes, we let the new $$$[L_{min}',L_{max}']$$$ be $$$[L_{min},L_{max}] \cap [l,r]$$$, where $$$[l,r]$$$ is the possible interval for the new snail. If the new interval is empty, we ignore this information, otherwise adopt it.

Now let's focus on another problem: for a fixed $$$L,a,b$$$, how to calculate the number of days the snail needs to climb? We can solve the equation $$$(n-2)(a-b) + a < L \le (n-1)(a-b) + a$$$, and get $$$n - 2 < \frac{L - a}{a - b} \le n - 1$$$, which means $$$n$$$ equals to $$$\lceil \frac{L-a}{a-b} \rceil + 1$$$. Still, special judge for $$$L \le a$$$, where $$$n=1$$$ in this case.

Then, for each query of type $$$2$$$, we just calculate the number of days we need for $$$L_{min}$$$ and $$$L_{max}$$$. If they are the same, output that number. Otherwise output $$$-1$$$.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
    int q;scanf("%d",&q);
    ll L = 1 , R = 1e18;
    while(q--) {
        int op;scanf("%d",&op) ;
        if(op == 1) {
            int a,b,n;scanf("%d%d%d",&a,&b,&n);
            ll ql = 1LL*(n - 2)*(a - b) + a + 1, qr = 1LL*(n - 1)*(a - b) + a;
            if(n == 1) ql = 1 , qr = a;
            if(ql > R || qr < L) {
                puts("0");
            }
            else L = max(L , ql) , R = min(R , qr) , puts("1");
        }
        else {
            int a,b;scanf("%d%d",&a,&b);
            ll ans1 = max(1LL,(L - b - 1) / (a - b) + 1) , ans2 = max(1LL,(R - b - 1) / (a - b) + 1);
            if(ans1 == ans2) printf("%lld\n",ans1);
            else puts("-1");
        }
    }
    return;
}
int main()
{
    int t;scanf("%d",&t);
    while(t--) solve();
}

How to check whether it is possible to defeat all the monsters, starting from a fixed vertex $$$u$$$?

Let $$$S(u)$$$ be the vertices set that can be reached, starting from vertex $$$u$$$. What's the relationship between $$$S(u)$$$ and $$$S(v)$$$, where $$$v\in S(u)$$$?

For some vertex set $$$T$$$, let's define $$$E(T)$$$ as the ''neighbours'' of vertex set $$$T$$$. Formally, $$$v \in E(T)$$$ if and only if $$$v \notin T$$$, but there exist some vertex $$$u$$$, such that there's an edge $$$(u,v)$$$ in the graph, and $$$u \in T$$$.

Now let's consider how to solve the problem for some fixed starting vertex $$$u$$$? Let's maintain the set $$$S(u)$$$ and $$$E(S(u))$$$. Initially, $$$S(u) = {u }$$$. We keep doing the procedure: choose a vertex $$$v \in E(S(u))$$$ with minimal value $$$a_{v}$$$. If $$$a_{v} \le |S(u)|$$$, we add $$$v$$$ into set $$$S(u)$$$, and update set $$$E(S(u))$$$ simultaneously. Since $$$S(u)$$$ is always connected during the procedure, we are actually doing such a thing: find a vertex $$$v$$$ that is ''reachable'' now with minimal value $$$a_{v}$$$, and try to defeat the monster on it. Our goal is to find some $$$u$$$ such that $$$|S(u)| = n$$$.

Then let's move to a lemma: if $$$v \in S(u)$$$, then $$$S(v) \subseteq S(u)$$$.

Then we can tell, if $$$|S(u)| < n$$$, then for $$$v \in S(u)$$$, $$$|S(v)| < n$$$. So it's unnecessary to search starting from $$$v$$$. And we can construct such an algorithm: Search from $$$1,2,3,\dots n$$$ in order, if some $$$i$$$ has been included in some $$$S(j)$$$ before, do not search from it.

Surprisingly, this algorithm is correct. We can prove it's time complexity. For each vertex $$$v$$$, if $$$v \in S(u)$$$ now, and when searching from vertex $$$u'$$$, $$$v$$$ is add into $$$S(u')$$$ again, then $$$|S(u')| > 2|S(u)|$$$. Thus, one vertex can not be visited more than $$$log(n)$$$ times, which means the time complexity is $$$O(nlog^2(n))$$$.

This problem has many other methods to solve. This one I think is the easiest to implement.

#include<bits/stdc++.h>
using namespace std;
int vis[200005];
int n , m;
vector<int> E[200005];
int a[200005];
int T = 1;
bool span(int u)
{
    set<pair<int,int> > st;
    st.insert(pair<int,int>{a[u] , u});
    int amt = 0 , df = 0;
    while(st.size()) {
        auto pa = (*st.begin()) ; vis[pa.second] = u;
        if(pa.first > df) {return (amt == n);}
        st.erase(st.begin());
        amt++ ; df++ ;
        for(auto v : E[pa.second]) {
            if(vis[v] < u) {
                st.insert(pair<int,int>{a[v] , v});
            }
        }
    }
    return (amt == n);
}
void solve()
{
    scanf("%d%d",&n,&m);
    for(int i= 1;i <= n;i++) scanf("%d",&a[i]) , vis[i] = 0, E[i].clear();
    for(int i = 1;i <= m;i++) {
        int u,v;scanf("%d%d",&u,&v);E[u].push_back(v) ; E[v].push_back(u);
    }
    for(int i = 1;i <= n;i++) {
        if(a[i] == 0 && !vis[i]) {
            if(span(i)){puts("YES");return;}
        }
    }
    puts("NO");
}
int main()
{
    int t;scanf("%d",&t);
    while(t--) solve();
}

Can you solve a single query using binary search? How to check the answer?

Try to find a closed formula for this problem.

Let $$$num_{i}$$$ be the number of occurances of integer $$$i$$$ in the array $$$a$$$. To check whether the answer can be $$$\le x$$$ or not, we can do the following greedy: Starting with a single vertex written $$$x$$$, which is the root. For each $$$i$$$(from large ones to small ones), if the number of current leaves is smaller than $$$num_{i}$$$, then we can not make the answer $$$\le x$$$. Otherwise, let $$$num_{i}$$$ leaves stop, and other leaves ''grow'' $$$m$$$ children each(these vertices are no longer leaves, but their children are). We can discover that each round, the ''stopped'' vertices have $$$dep = x - i$$$, which represents their value is $$$x$$$.

We can use the following code to calculate it.

bool check(int x)
{
    int d = 1;
    for(int i = x;i >= 1;i--){
        if(d < num[i]) return 0;
        d = (d - num[i]) * m;
    }
    return 1;
}

Since a negtive number multiplies $$$m$$$ is still a negtive number, the code can be as following:

bool check(int x)
{
    int d = 1;
    for(int i = x;i >= 1;i--){
        d = (d - num[i]) * m;
    }
    return d >= 0;
}

Find out something? The final $$$d$$$ is just $$$m^x - \sum_{i=1}^{x}{num_{i} \cdot m^i}$$$, which represents it's equivalent to checking $$$m^x \ge \sum_{i=1}^{n}{m^{a_{i}}}$$$! So now the answer is just $$$\lceil log_{m}{\sum_{i=1}^{n}{m^{a_{i}}}} \rceil$$$. This is the highest bit plus one of $$$\sum{m^{a_{i}}}$$$ in $$$m$$$-base representation(except for that it's just some $$$m^x$$$. In this case the answer is $$$x$$$ but not $$$x+1$$$). We can use a segment tree, supporting interval min/max query and interval covering to solve the question.

#include<bits/stdc++.h>
using namespace std;
int n , m , q;
const int N = 2e5 + 40;
int num[N];
int a[N];
int cov[N*4 + 5] , mx[N*4 + 5] , mn[N*4 + 5];
void rec(int u)
{
    mx[u] = max(mx[u<<1|1] , mx[u<<1]) ; mn[u] = min(mn[u<<1|1] , mn[u<<1]);
}
void pd(int u)
{
    if(cov[u] != -1) {
        cov[u<<1] = mn[u<<1] = mx[u<<1] = cov[u];
        cov[u<<1|1] = mn[u<<1|1] = mx[u<<1|1] = cov[u];
        cov[u] = -1;
    }
    return;
}
void build(int u,int l,int r)
{
    cov[u] = -1;
    if(l == r) {mn[u] = mx[u] = num[l] ; return;}
    build(u<<1 , l , (l + r >> 1)) ; build(u<<1|1 , (l + r >> 1) + 1 , r);
    rec(u) ; return;
}
void modify(int u,int l,int r,int ql,int qr,int v)
{
    if(ql <= l && qr >= r) {
        cov[u] = mn[u] = mx[u] = v; return;
    }
    pd(u);
    int md = (l + r>> 1);
    if(ql <= md) modify(u<<1 , l , md , ql , qr ,v);
    if(qr > md) modify(u<<1|1 , md +1 , r , ql , qr , v);
    rec(u);
    return;
}
 
int qumax(int u,int l,int r,int ql)
{
    if(mn[u] == m &mdash; 1) return -1;
    if(l == r) return l;
    pd(u);
    int md = (l + r>> 1);
    if(ql > md) return qumax(u<<1|1 , md + 1 , r , ql);
    if(ql == l) {
        if(mn[u<<1] < m &mdash; 1) return qumax(u<<1 , l , md , ql);
        return qumax(u<<1|1 , md + 1 , r , md + 1);
    }
    int w = qumax(u<<1 , l , md , ql) ;
    if(w == -1) return qumax(u<<1|1 , md + 1 , r , md + 1);
    return w;
}
int qumin(int u,int l,int r,int ql)
{
    if(mx[u] == 0) return -1;
    if(l == r) return l;
    pd(u);
    int md = (l + r>> 1) ;
    if(ql > md) return qumin(u<<1|1 , md + 1 , r , ql);
    if(ql == l) {
        if(mx[u<<1] > 0) return qumin(u<<1 , l , md , ql);
        return qumin(u<<1|1 , md + 1 , r , md + 1);
    }
    int w = qumin(u<<1 , l , md , ql);
    if(w == -1) return qumin(u<<1|1 , md + 1 , r , md + 1);
    return w;
}
 
int qmax(int u,int l,int r,int ql,int qr)
{
    if(ql <= l && qr >= r) {
        return mx[u];
    }
    pd(u);
    int md = (l + r>> 1) , ans = 0;
    if(ql <= md) ans = max(ans , qmax(u<<1 , l , md , ql , qr ));
    if(qr > md) ans = max(ans , qmax(u<<1|1 , md +1 , r , ql , qr));
    return ans;
}
int qmin(int u,int l,int r,int ql,int qr)
{
    if(ql <= l && qr >= r) {
        return mn[u];
    }
    pd(u);
    int md = (l + r>> 1) , ans = 1e9;
    if(ql <= md) ans = min(ans , qmin(u<<1 , l , md , ql , qr ));
    if(qr > md) ans = min(ans , qmin(u<<1|1 , md +1 , r , ql , qr));
    return ans;
}
int ask(int u,int l,int r)
{
    if(l == r) return l;
    int md = (l + r >> 1);
    pd(u);
    if(mx[u<<1|1] == 0) return ask(u<<1 , l , md);
    return ask(u<<1|1 , md + 1 , r) ;
}
int get()
{
    int highbit = ask(1 , 1 , n+35);
    if(highbit == 1 || qmax(1 , 1 , n+35 , 1 , highbit &mdash; 1) == 0) return highbit;
    return highbit + 1;
}
void add(int u)
{
    int l = qumax(1 , 1 , n + 35 , u);
    if(l > u) modify(1 , 1 , n+35 , u , l &mdash; 1 , 0) ;
    modify(1 , 1 , n+35 , l , l , qmax(1 , 1 , n + 35 , l , l ) + 1);
    return;
}
void sub(int u)
{
    int l = qumin(1 , 1 , n + 35 , u);
    if(l > u) modify(1 , 1 , n+35 , u , l &mdash; 1 , m &mdash; 1) ;
    modify(1 , 1 , n+35 , l , l , qmax(1 , 1 , n + 35 , l , l ) &mdash; 1);
    return;
}
void solve()
{
    scanf("%d%d%d",&n,&m,&q);
    for(int i = 1;i <= n + 35;i++) num[i] = 0;
    for(int i = 1;i <= n;i++) {
        scanf("%d",&a[i]);num[a[i]]++;
    }
    for(int i = 1;i <= n + 35;i++) {
        num[i + 1] += num[i] / m;num[i] %= m;
    }
    build(1 , 1 , n + 35);
    while(q--) {
        int u , v;scanf("%d%d",&u,&v);
        sub(a[u]) ; a[u] = v; add(a[u]) ;
        printf("%d%c",get(), " \n"[q == 0]);
    }
    return;
}
int main()
{
    int t;scanf("%d",&t);
    while(t--) solve();
}

How to calculate the maximal prefix sum? One possible way is let $$$f_{n+1} = 0$$$ and $$$f_{i}=max(f_{i+1},0)+a_{i}$$$.

Consider this method to find maximal prefix sum: let $$$f_{n+1} = 0$$$ and $$$f_{i}=max(f_{i+1},0)+a_{i}$$$. We can discover that the only influence $$$[a_{i+1},a_{i+2} \dots a_{n}]$$$ has(to the whole array's maximal prefix sum) is its maximal prefix sum. Then we let $$$dp_{i,j}$$$ be : the expect score we can get, if we assume that the maximal prefix sum of $$$[a_{i+1},a_{i+2} \dots a_{n}]$$$ is $$$j$$$ (Read the definition carefully). The answer for each $$$k$$$ is $$$dp_{k,0}$$$, since if the maximal prefix sum for $$$[a_{k+1},a_{k+2} \dots a_{n}]$$$ is $$$0$$$, that is equivalent to removing them from the array. And also $$$dp_{0,j} = h_{j}$$$.

And we have $$$dp_{i,j} = p_{i}\cdot dp_{i-1,j+1} + (1 - p_{i})\cdot dp_{i-1,max(j-1,0)}$$$. The first section represents chosing $$$a_{i} = 1$$$ and the second one represents chosing $$$a_{i} = -1$$$.

We also have other solutions, using inclusion-exclusion or generate function. Actually all the testers' solutions differs from each other.

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int N = 5005;
int p[N] , q[N];
int n;
int f[N][N];
int h[N];
int fpow(int a,int b)
{
    int ans = 1;
    while(b){
        if(b & 1) ans = 1LL*ans*a%mod;
        a = 1LL*a*a%mod;b >>= 1;
    }
    return ans;
}
void solve()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i++) {
        int a,b;scanf("%d%d",&a,&b);
        p[i] = 1LL*a*fpow(b , mod - 2) % mod;
        q[i] = (1 - p[i] + mod) % mod;
    }
    for(int i = 0;i <= n;i++) scanf("%d",&h[i]);
    for(int i = 0;i <= n;i++) f[0][i] = h[i];
    for(int i = 1;i <= n;i++) {
        for(int j = 0;j <= n;j++) {
            f[i][j] = (1LL*p[i]*f[i - 1][j + 1] + 1LL*q[i]*f[i - 1][max(0 , j - 1)] ) % mod;
        }
        printf("%d ",f[i][0]);
    }
    printf("\n");
    return;
}
int main()
{
    int t;scanf("%d",&t);
    while(t--) solve();
    return 0;
}

Actually I don't know how to hint. Try to find some rules related to $$$\frac{\sqrt{5}+1}{2}$$$, fibnacci or similar

Assume that the moment before the $$$x$$$-th operation(but after $$$x-1$$$-th), the first time we have $$$S_{max} \le 2S_{min}$$$. Let's divide the operation into two part: before $$$x$$$ and equal or after $$$x$$$.

Still, at the moment just before the $$$x$$$-th operation, let us sort the elements in the multiset in non-decreasing order, $$$S_{0},S_{1} \dots S_{k}$$$. We will show that the answer is $$$S_{0}\cdot (-1)^{k} + \sum_{i=1}^{k}{S_{i}\cdot (-1)^{i+1}}$$$.

Let $$$d_{i}$$$ be the $$$S_{max}$$$ value in the $$$i$$$-th operation. Let's prove that before the $$$x$$$-th operation, $$$d_{i} = n-\lceil \frac{i}{\phi} \rceil + 1$$$, where $$$\phi = \frac{\sqrt{5} + 1}{2}$$$.

Then, by solve $$$n - \lceil \frac{x}{\phi} \rceil + 1 \le 2x$$$, we can get $$$x = \lceil (n+1)\frac{\phi - 1}{\phi} \rceil$$$. Now let's prove for $$$k \ge x$$$, $$$d_{k} = n - \lceil \frac{k}{\phi} \rceil + 1$$$ also holds !

Till now, the lemmas told us the solving the problem is actually solving something like $$$\sum_{(-1)^{i} \cdot (n- \lceil \frac{i}{\phi} \rceil + 1)}$$$. We can divide them into positive part and negtive part, and then solving $$$\sum_{\lfloor C\cdot i \rfloor}$$$, where $$$i$$$ range from some $$$l$$$ to $$$r$$$, and $$$C$$$ is a irrational constant. Since $$$n$$$ is not very large, we can approximate $$$C$$$ by $$$\frac{a}{b}$$$, where $$$a,b$$$ are integers, and turn it into a traditional task. (Maybe it is called floor sum or something like, I'm not sure about the algorithm's english name).

The marvelous jiangly told me $$$a,b$$$ in long long range is enough. But the tester used int128.

We can dig more about the $$$\phi$$$. Let $$$b_{i} = S_{i+1} - S_{i}$$$ (sorted, before the $$$x$$$-th operation), and what we care is $$$b_{1} + b_{3} + b_{5}\dots$$$. We can find that array $$$b$$$ is actually a consecutive substring of fibonacci string. More over, let $$$F_{n}$$$ be the starting point of array $$$b$$$ in the fibonacci string when the initial size is $$$n$$$, we have the conclusion for $$$n \ge 5$$$:

$$$F[5 \dots inf] = [3,0],[4,1],[8,0],[12,1] \dots [f_{i+3} + (-1)^{i+1} , 1 + (-1)^{i}]$$$, where $$$f_{i} = f_{i-1} + f_{i-2} , f_{1} = f_{2} = 1$$$ . $$$[r,l]$$$ represents a list of numbers $$$[r,r-1,r-2 \dots l+1,l]$$$.

Now the only left problem is to find the prefix sum of fibonacci string(of even positions, or of odd positions). This is quite a simple task by using any $$$log(n)$$$ or $$$log^2(n)$$$ solution.

#include <bits/stdc++.h>
 
void solve(__int128 n, __int128 a, __int128 b, __int128 c, __int128 &f) {
    if (n < 0) { f = 0; return; }
    if (a >= c || b >= c) {
        solve(n, a % c, b % c, c, f);
        f += (a / c) * (n * (n + 1) / 2) + (b / c) * (n + 1);
    } else if (a) {
        __int128 m = (a * n + b) / c;
        solve(m - 1, c, c - b - 1, a, f);
        f = n * m - f;
    }
}
 
const long double k = (1 + sqrt((long double) 5)) / 2;
 
int n;
long long ans;
__int128 a, b, c, d;
 
int main() {
    int T;
    scanf("%d", &T);
    __int128 x = (__int128) 2000000000000000000ll * 1000000000;
    __int128 y = (__int128) 1000000000000000000ll * 1000000000;
    __int128 z = (__int128) 1618033988749894848ll * 1000000000 + 204586834;
    for (; T; T--) {
        scanf("%d", &n);
        int i = 0;
        for (int l = 0, r = n - 1, mid; l <= r; ) {
            mid = l + r >> 1;
            if (n - floor(mid / k) <= mid + mid) {
                i = mid; r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        solve((n - 1) / 2, x, 0, z, a);
        solve((i - 1) / 2, x, 0, z, b);
        solve((n - 2) / 2, x, y, z, c);
        solve((i - 2) / 2, x, y, z, d);
        ans = i + (i % 2 ? -1 : 1) * ((a - b) - (c - d));
        if ((n - i) % 2) { ans = n - ans; }
        printf("%lld\n", ans);
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int l[500];
int fib[500];
int evenfib[500];
int getsum(int i,int n) ///1-index
{
    if(n == 0) return 0;
    if(i <= 1) return fib[i];
    if(n <= l[i - 2]) return getsum(i - 2,  n);
    return fib[i - 2] + getsum(i - 1 , n - l[i - 2]);
}
int getsum2(int i,int n,int p) ///n = 2*k+p, 0-index
{
    if(i <= 0) return 0;
    if(i <= 1) return 1^p;
 
    if(n <= l[i - 2] - 1) return getsum2(i - 2 , n , p);
    int L;
    if(p) L = (l[i - 2] - !(l[i-2]&1));
    else L = (l[i- 2] - (l[i - 2] & 1));
    int ans ;
    if(p) ans = fib[i - 2] - evenfib[i - 2];
    else ans = evenfib[i - 2];
    ans += getsum2(i - 1 , n - l[i - 2] , p ^ ((l[i - 2] & 1)));
    return ans;
}
int getfib(int n) ///0-index
{
    if(n <= 0) return 0;
    n++;
    int ans = 0;
    int i;
    for(i = 0;l[i] <= n;i++) {
        ans += fib[i] ; n -= l[i];
    }
    return ans + getsum(i , n);
}
int get_even(int n) ///n = 2*k
{
    n++;
    int ans = 0;
    int i , lbefore = 0;
    for(i = 0;l[i] <= n;i++) {
        if(lbefore) ans += fib[i] - evenfib[i];
        else ans += evenfib[i];
        lbefore ^= (l[i]&1);
        n -= l[i];
    }
    if(n) ans += getsum2(i , n - 1, lbefore);
    return ans;
}
const double phi = (3 - sqrt(5)) / 2;
const double eps = 1e-6;
int getstart(int n)
{
    if(n == 3) return 0;
    if(n == 4) return 1;
    n -= 4;
    int i;
    for(i = 1;1;i++) {
        int lft ;
        if(i & 1) lft = fib[i + 3] + 1;
        else lft = fib[i + 3] - 1;
        if(n <= lft) break;
        n -= lft;
    }
    int start ;
    if(i & 1) start = fib[i + 3] - n + 1;
    else start = fib[i + 3] - n;
    return start;
}
typedef long long ll;
const int L = 95;
int a[120] = {8,0,6,0,1,8,5,9,7,2,9,7,2,9,2,0,5,5,7,9,0,1,8,1,7,3,5,9,3,7,4,9,2,7,7,3,1,5,5,4,6,8,7,3,1,7,3,2,4,9,1,0,2,8,0,9,6,9,7,2,2,8,8,1,6,3,4,3,6,5,6,1,3,1,4,5,9,7,1,5,1,5,0,1,0,5,2,1,1,0,6,6,9,1,8,3};
ll b[120];
double cal(int n)
{
    memset(b,0,sizeof(b));
    for(int i = 0;i <= L;i++) b[i] = 1LL*n*a[i];
    for(int i = 0;i <= L + 15;i++) {
        b[i + 1] += (b[i] / 10) ; b[i] %= 10;
    }
    int ans = 0;
    for(int i = L + 11;i >= L + 1;i--) ans = (ans * 10 + b[i]) ;
    return ans;
}
void solve(int n)
{
    if(n <= 2) {puts("1");return;}
    int v = cal(n);
    int len = n - v;v++;
    int start = getstart(n);
    int ans = 0;
    if(len & 1) {
        ans = v; ///[start + 1 , start + 3...start + len - 2]
        if(start & 1) ans -= (get_even(start + len - 2) - get_even(start - 1));
        else ans -= (getfib(start + len - 1) - get_even(start + len - 1) - getfib(start) + get_even(start));
    }
    else {
        ans = getfib(start + len - 2) - getfib(start - 1);
        ///[start + 1 , start + len - 3]
        if(start & 1) ans -= (get_even(start + len - 3) - get_even(start - 1));
        else ans -= (getfib(start + len - 2) - get_even(start + len - 2) - getfib(start) + get_even(start));
    }
    printf("%d\n",ans);return;
}
int main()
{
    l[0] = l[1] = 1;
    fib[0] = 0 , fib[1] = 1;
    evenfib[1] = 1;
    for(int i = 2;l[i-1] <= 1000000000;i++) {
        l[i] = l[i - 1] + l[i - 2];
        fib[i] = fib[i - 1] + fib[i - 2];
        if(l[i - 2] & 1) evenfib[i] = evenfib[i - 2] + fib[i - 1] - evenfib[i - 1];
        else evenfib[i] = evenfib[i - 2] + evenfib[i - 1];
    }
 
    int t;scanf("%d",&t);
    while(t--) {
        int n;scanf("%d",&n);solve(n);
    }
    return 0;
}