1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const ll N=1e6+11,St=1e6,mod=998244353;
 5 ll T,n,A,B,dp[N];
 6 
 7 inline ll re_ad() {
 8     char ch=getchar(); ll x=0,f=1;
 9     while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
10     while('0'<=ch && ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
11     return x*f;
12 }
13 
14 inline void Init() {
15     dp[0]=dp[1]=dp[2]=1;
16     for(ll i=3;i<=St;++i) dp[i]=(dp[i-1]+dp[i-3])%mod;
17 }
18 
19 int main()
20 {
21     freopen("achen.in","r",stdin);
22     freopen("achen.out","w",stdout);
23     T=re_ad();
24     Init();
25     while(T--) {
26         n=re_ad(),A=re_ad(),B=re_ad();
27         if(A>B) A^=B^=A^=B;
28         ll lj=B-A;
29         if(A!=1) --lj;
30         if(B!=n) --lj;
31         if(lj<0) printf("0\n");
32         else printf("%lld\n",dp[lj]);
33     }
34 //    system("pause");
35     return 0;
36 }

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int N=1e6+11,M=2e6+11,L=23;
  4 int n,m,a[N],ans;
  5 int to[M],nxt[M],edge,head[N];
  6 int fa[N],g[N],gr[N][L],dep[N],mxdep[N];
  7 int tot,dfn[N],rev[N];
  8 int Mi[N],dp[3][N];
  9 int lst[3][N],t[N],tag[N];
 10 
 11 inline int re_ad() {
 12     char ch=getchar(); int x=0,f=1;
 13     while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
 14     while('0'<=ch && ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
 15     return x*f;
 16 }
 17 
 18 inline void addedge(int x,int y) {
 19     ++edge,to[edge]=y,nxt[edge]=head[x],head[x]=edge;
 20     ++edge,to[edge]=x,nxt[edge]=head[y],head[y]=edge;
 21 }
 22 
 23 int dfs1(int d,int f,int x) {
 24     fa[d]=gr[d][0]=f,g[d]=x;
 25     for(int i=1;i<=20;++i) gr[d][i]=gr[gr[d][i-1]][i-1];
 26     mxdep[d]=dep[d]=dep[f]+1;
 27     dfn[d]=++tot,rev[tot]=d;
 28     for(int i=head[d],u;i;i=nxt[i]) {
 29         u=to[i];
 30         if(u==f) continue;
 31         mxdep[d]=max(mxdep[d],dfs1(u,d,x));
 32     }
 33     return mxdep[d];
 34 }
 35 
 36 void dfs2(int d) {
 37     dp[1][d]=max(dp[1][d],dp[1][fa[d]]+1);
 38     int maxx=0;
 39     for(int i=head[d],u;i;i=nxt[i]) {
 40         u=to[i];
 41         if(u==fa[d]) continue;
 42         maxx=max(maxx,mxdep[u]);
 43     }
 44     for(int i=head[d],u;i;i=nxt[i]) {
 45         u=to[i];
 46         if(u==fa[d]) continue;
 47         if(mxdep[u]!=maxx) dp[1][u]=max(dp[1][u],maxx-dep[d]+2);
 48         else {
 49             for(int j=head[d],v;j;j=nxt[j]) {
 50                 v=to[j];
 51                 if(v==u || v==fa[d]) continue;
 52                 dp[1][u]=max(dp[1][u],mxdep[v]-dep[d]+2);
 53             }
 54         }
 55     }
 56     for(int i=head[d],u;i;i=nxt[i]) {
 57         u=to[i];
 58         if(u==fa[d]) continue;
 59         dfs2(u);
 60     }
 61 }
 62 
 63 inline int LCA(int x,int y) {
 64     if(dep[x]<dep[y]) x^=y^=x^=y;
 65     int fx,fy;
 66     if(x==y) return x;
 67     for(int i=20;i>=0;--i) {
 68         fx=gr[x][i];
 69         if(dep[fx]>=dep[y]) x=fx;
 70     }
 71     if(x==y) return x;
 72     for(int i=20;i>=0;--i) {
 73         fx=gr[x][i],fy=gr[y][i];
 74         if(fx!=fy) x=fx,y=fy;
 75     }
 76     return fa[x];
 77 }
 78 
 79 void search1(int d) {
 80     for(int i=head[d],u;i;i=nxt[i]) {
 81         u=to[i];
 82         if(u==fa[d]) continue;
 83         search1(u);
 84         t[d]+=t[u];
 85     }
 86 }
 87 void search2(int d) {
 88     for(int i=head[d],u;i;i=nxt[i]) {
 89         u=to[i];
 90         if(u==fa[d]) continue;
 91         search2(u);
 92         tag[d]=max(tag[d],tag[u]);
 93     }
 94 }
 95 
 96 inline void print_test() {
 97     for(int i=1;i<=n;++i) printf("%d ",fa[i]); puts("");
 98     for(int i=1;i<=n;++i) printf("%d ",g[i]); puts("");
 99     for(int i=1;i<=n;++i) printf("%d ",dep[i]); puts("");
100     for(int i=1;i<=n;++i) printf("%d ",mxdep[i]); puts("");
101     for(int i=1;i<=n;++i) printf("%d ",dfn[i]); puts("");
102     for(int i=1;i<=n;++i) printf("%d ",rev[i]); puts("");
103     for(int i=1;i<=n;++i) printf("%d ",Mi[i]); puts("");
104     for(int i=1;i<=n;++i) printf("%d ",dp[1][i]); puts("");
105     for(int i=1;i<=n;++i) printf("%d ",dp[2][i]); puts("");
106     for(int i=1;i<=n;++i) printf("%d ",t[i]); puts("");
107     for(int i=1;i<=n;++i) printf("%d ",tag[i]); puts("");
108 }
109 
110 int main()
111 {
112     freopen("tree.in","r",stdin);
113     freopen("tree.out","w",stdout);
114     n=re_ad(),m=re_ad();
115     for(int i=1;i<=n;++i) a[i]=re_ad();
116     for(int i=1,x,y;i<n;++i) x=re_ad(),y=re_ad(),addedge(x,y);
117     fa[1]=g[1]=0;
118     for(int i=1;i<=20;++i) gr[1][i]=0;
119     dep[1]=dfn[1]=rev[1]=tot=1;
120     int maxx=0;
121     for(int i=head[1],u;i;i=nxt[i]) {
122         u=to[i];
123         maxx=max(maxx,dfs1(u,1,u));
124     }
125     mxdep[1]=maxx;
126 /*    for(int i=head[1],u;i;i=nxt[i]) {
127         u=to[i];
128         if(mxdep[u]!=maxx) Mi[u]=maxx;
129         else for(int j=head[1],v;j;j=nxt[j]) {
130             v=to[j];
131             if(v==u) continue;
132             Mi[u]=max(Mi[u],mxdep[v]);
133         }
134     }
135     for(int i=1;i<=n;++i) dp[1][i]=Mi[g[i]]+dep[i]-1;
136 */
137     dfs2(1);
138     for(int i=1;i<=n;++i) dp[2][i]=mxdep[i]-dep[i]+1;
139 
140 //    printf("awa\n");
141     for(int i=1,x,l,lca;i<=n;++i) {
142         x=rev[i];
143         l=lst[1][a[x]];
144         lst[1][a[x]]=x;
145         if(!l) ++t[x];
146         else lca=LCA(l,x),++t[x],--t[lca];
147     }
148 //    for(int i=1;i<=n;++i) printf("%d ",t[i]); puts("");
149     search1(1);
150 //    for(int i=1;i<=n;++i) printf("%d ",t[i]); puts("");
151     for(int i=1;i<=n;++i) if(t[i]==m) ans=max(ans,dp[1][i]);
152 //    printf("%d\n",ans);
153 
154 //    printf("qwq\n");
155     for(int i=1,x,l,lca;i<=n;++i) {
156         x=rev[i];
157         l=lst[2][a[x]];
158         if(!l) lst[2][a[x]]=x;
159         else lst[2][a[x]]=LCA(l,x);
160 //        printf("col: %d %d\n",lst[2][1],lst[2][2]);
161     }
162     for(int i=1;i<=m;++i) tag[lst[2][i]]=1;
163     search2(1);
164     for(int i=1;i<=n;++i) if(!tag[i]) ans=max(ans,dp[2][i]+1);
165     printf("%d\n",ans);
166 //    print_test();
167     return 0;
168 }

  1 //std
  2 #include<bits/stdc++.h>
  3 using namespace std;
  4 typedef long long ll;
  5 const int maxn = 2e5 + 7, maxm = 1e6 + 7, INF = 0x3f3f3f3f;
  6 int Td, n, m, a[maxn], p[maxn], now[maxn], lst[maxn];
  7 ll ans;
  8 
  9 struct Node{
 10     int pos, x;
 11     Node(int pos = 0, int x = 0) : pos(pos), x(x) {}
 12 }mx[maxn], mn[maxn];
 13 int tx, tn;
 14 
 15 #define lc (pos << 1)
 16 #define rc (pos << 1 | 1)
 17 
 18 int num[maxm], laz[maxm], hs[maxm];
 19 void ud(int pos) {
 20     num[pos] = min(num[lc], num[rc]);
 21     hs[pos] = 0;
 22     if(num[lc] == num[pos]) hs[pos] += hs[lc];
 23     if(num[rc] == num[pos]) hs[pos] += hs[rc];
 24 }
 25 
 26 void bld(int pos, int l, int r) {
 27     laz[pos] = 0;
 28     if(l == r) {
 29         num[pos] = 0;
 30         hs[pos] = 1;
 31         return;
 32     }
 33     int mid = (l + r) >> 1;
 34     bld(pos << 1, l, mid);
 35     bld(pos << 1 | 1, mid + 1, r);
 36     ud(pos);
 37 }
 38 
 39 void add_laz(int pos, int x) {
 40     laz[pos] += x;
 41     num[pos] += x;
 42 }
 43 
 44 void pd(int pos) {
 45     add_laz(lc, laz[pos]);
 46     add_laz(rc, laz[pos]);
 47     laz[pos] = 0;
 48 }
 49 
 50 int ql, qr, qx;
 51 void chge(int pos, int l, int r) {
 52     if(l >= ql && r <= qr) {
 53         add_laz(pos, qx);
 54         return;
 55     }
 56     int mid = (l + r) >> 1; pd(pos);
 57     if(ql <= mid) chge(lc, l, mid);
 58     if(qr > mid) chge(rc, mid + 1, r);
 59     ud(pos);
 60 }
 61 
 62 int q(int pos, int l, int r) {
 63     if(l >= ql && r <= qr) {
 64         if(num[pos] != -1) return 0;
 65         return hs[pos];
 66     }
 67     int mid = (l + r) >> 1, rs = 0; pd(pos);
 68     if(ql <= mid) rs += q(lc, l, mid);
 69     if(qr > mid) rs += q(rc, mid + 1, r);
 70     return rs;
 71 }
 72 
 73 int main() {
 74 //    freopen("easy.in", "r", stdin);
 75 //    freopen("easy.out", "w", stdout);
 76     int x;
 77     scanf("%d", &n);
 78     for (int i = 1; i <= n; ++i) {
 79         scanf("%d", &a[i]);
 80         p[i] = a[i];
 81     }
 82     sort(p + 1, p + n + 1);
 83     m = unique(p + 1, p + n + 1) - p - 1;
 84     for (int i = 1; i <= m; ++i) now[i] = 0;
 85     for (int i = 1; i <= n; ++i) {
 86         x = lower_bound(p + 1, p + m + 1, a[i]) - p;
 87         lst[i] = now[x];
 88         now[x] = i;
 89     }
 90 
 91     bld(1, 1, n);
 92 
 93     ans = 0;
 94     mx[tx = 1] = Node(0, INF);
 95     mn[tn = 1] = Node(0, 0);
 96     for (int i = 1; i <= n; ++i) {
 97         //R:
 98         while(tx > 1 && mx[tx].x <= a[i]) {
 99             ql = mx[tx - 1].pos + 1;
100             qr = mx[tx].pos;
101             qx = a[i] - mx[tx].x;
102             chge(1, 1, n);
103             --tx;
104         }
105         mx[++tx] = Node(i, a[i]);
106         //L:
107         while(tn > 1 && mn[tn].x >= a[i]) {
108             ql = mn[tn - 1].pos + 1;
109             qr = mn[tn].pos;
110             qx = mn[tn].x - a[i];
111             chge(1, 1, n);
112             --tn;
113         }
114         mn[++tn] = Node(i, a[i]);
115         //cnt:
116         ql = lst[i] + 1; qr = i; qx = -1;
117         chge(1, 1, n);
118 
119         ql = 1; qr = i;
120         ans = ans + (ll)q(1, 1, n);
121     }
122     printf("%lld\n", ans);
123     cerr<<ans<<endl;
124     return 0;
125 }