#include "infection.h"
#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
using namespace std;
const int maxn =1500010;
vector<int> starts[maxn];
vector<int> endss[maxn];
int n,q;
int bord[maxn];
std::vector<int> solve(
    std::vector<std::pair<int, int>> R,///rebra
    std::vector<long long> D,///nachalni dni
    std::vector<int> S,///nachalna poziciq
    std::vector<int> T,///krajna poziciq
    std::vector<bool> I///bolen/nebolen
)
{

    q=D.size();
    vector<int> mom(q,0);
    n=R.size()+1;
    for(int i=0;i<=q;i++) mom[i]=-1;
    for(int i=0;i<n-1;i++)
    {
        R[i].f++;
        R[i].s++;
    }
    for(int i=0;i<q;i++)
    {
        S[i]++;
        T[i]++;
        if(S[i]<T[i])
        {
            starts[S[i]].push_back(i);
            if((T[i]-S[i])&1) T[i]--;
        }
        else
        {
            endss[S[i]].push_back(i);
            if((S[i]-T[i])&1) T[i]++;
            bord[i]=T[i]-S[i]/2;
        }
    }
    for(int i=1;i<=n;i++)
    {
        bool fl=0;
        for(auto e:starts[i]) fl=(fl|I[e]);
        for(auto e:endss[i]) fl=(fl|I[e]);
        if(fl)
        {
            for(auto e:starts[i]) {I[e]=1;mom[e]=0;}
            for(auto e:endss[i])  {I[e]=1;mom[e]=0;}
        }
    }
    ///for even
    stack<int> ill;
    priority_queue<pair<int,int>> pq;
    //printf("before even\n");
    for(int i=2*(n/2);i>0;i-=2)
    {///make bord array
        for(auto e:endss[i])
        {
            if(!I[e]) {pq.push({-bord[e],e});continue;}
            while(!ill.empty() && bord[ill.top()]>=bord[e]) ill.pop();
            ill.push(e);
        }
        int mx=0;
        for(auto e:starts[i]) mx=max(mx,T[e]);
        if(starts[i].size()!=0 && !I[starts[i].back()])
        {
            while(!ill.empty() && bord[ill.top()]>i/2) ill.pop();
            if(!ill.empty())
            {
                ///zarazqwame lewite
                for(auto e:starts[i])
                {
                    if(T[e]>=(S[ill.top()]+i)/2) mom[e]=(S[ill.top()]+i)/2-i;
                }
            }
        }
        ///da zarazim desnite
        while(!pq.empty() && T[pq.top().s]<=mx)
        {
            mom[pq.top().s]=S[pq.top().s]-(S[pq.top().s]+i)/2;
            pq.pop();
        }
    }
    //printf("did even\n");
    ///for the uneven
    while(!ill.empty()) ill.pop();
    while(!pq.empty()) pq.pop();
    int lim=n;
    if(n&1) lim--;
    for(int i=lim;i>0;i-=2)
    {
        for(auto e:endss[i])
        {
            if(!I[e]) {pq.push({-bord[e],e});continue;}
            while(!ill.empty() && bord[ill.top()]>=bord[e]) ill.pop();
            ill.push(e);
        }
        int mx=0;
        for(auto e:starts[i]) mx=max(mx,T[e]);
        if(starts[i].size()!=0 && !I[starts[i].back()])
        {
            while(!ill.empty() && bord[ill.top()]>i/2) ill.pop();
            if(!ill.empty())
            {
                ///zarazqwame lewite
                for(auto e:starts[i])
                {
                    if(T[e]>=(S[ill.top()]+i)/2) mom[e]=(S[ill.top()]+i)/2-i;
                }
            }
        }
        ///da zarazim desnite
        while(!pq.empty() && T[pq.top().s]<=mx)
        {
            mom[pq.top().s]=S[pq.top().s]-(S[pq.top().s]+i)/2;
            pq.pop();
        }
    }
    return mom;
}
