$SOLUTION$SOLUTION

状态:
$F[i,j]表示前i项,递增序列最后一个元素为A_i的方案,递减序列最后一个元素为A_j的方案$F[i,j]表示前i项,递增序列最后一个元素为Ai​的方案,递减序列最后一个元素为Aj​的方案
$G[i,j]表示前i项,递减序列最后一个元素为A_i的方案,递增序列最后一个元素为A_j的方案$G[i,j]表示前i项,递减序列最后一个元素为Ai​的方案,递增序列最后一个元素为Aj​的方案

$Ask:为什么要另外开一个G\left[\right]\left[\right]状态?$Ask:为什么要另外开一个G[][]状态 ?
$Answer:说完转移后,自会提到.$Answer:说完转移后,自会提到.

转移:

注: $1\&lt;=j\&lt;i\&lt;=N$1<=j<i<=N

1. $i$i 与 $i-1$i−1 同属一个序列,

   1. $A_{i-1}\&lt;A_i$Ai−1​<Ai​, $F[i,j]+=F[i-1,j]$F[i,j]  +=  F[i−1,j];
   2. $A_{i-1}\&gt;A_i$Ai−1​>Ai​, $G[i,j]+=G[i-1,j]$G[i,j]  +=  G[i−1,j].

1. $i$i 与 $i-1$i−1 不同属一个序列,

   1. $A_j\&lt;A_i$Aj​<Ai​, $F[i,i-1]+=G[i-1,j]\left(F\right[j,i-1\left]\right)$F[i,i−1]  +=  G[i−1,j]                          (F[j,i−1])
   2. $A_j\&gt;A_i$Aj​>Ai​, $G[i,i-1]+=F[i-1,j]\left(G\right[j,i-1\left]\right)$G[i,i−1]  +=  F[i−1,j]                          (G[j,i−1])

$看到情况2的括号了吗?$看到情况2的括号了吗?
$这些状态在转移时还没有值,所以额外开了G\left[\right]\left[\right]来使得$这些状态在转移时还没有值,所以额外开了G[][]来使得 $转移可行$转移可行

至此已经完成了 $O\left(N^2\right)$O(N2) 的算法, 使用树状数组滚动即可优化为 $O\left(nlogn\right)$O(nlogn)

可能会出现 不存在某种序列 的情况, 所以要进行特殊处理, 代码中已用 $\#$# 注释

$CODE$CODE

#include<bits/stdc++.h>
#define reg register

int read(){
        char c;
        int s = 0, flag = 1;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ flag = -1, c = getchar(); break; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

const int maxn = 1500006;
const int mod = 666623333;

int N;
int M;
int A[maxn];

struct Tree{
        int tap[maxn], v[maxn], tim;
        void Modify(int k, int x){
                while(k <= N){
                        if(tap[k] != tim) tap[k] = tim, v[k] = 0;
                        v[k] += x;
                        if(v[k] >= mod) v[k] -= mod;
                        k += k & -k;
                }
        }
        int Query(int k){
                int s = 0;
                while(k >= 1){
                        if(tap[k] != tim) tap[k] = tim, v[k] = 0;
                        s += v[k];
                        if(s >= mod) s -= mod;
                        k -= k & -k;
                }
                return s;
        }
} Ft, Gt;

int flag_1, flag_2; // 1↑ 2↓

int main(){
        freopen("perm.in", "r", stdin);
        freopen("perm.out", "w", stdout);
        N = read();
        for(reg int i = 1; i <= N; i ++) A[i] = read();
        Ft.Modify(1, 1), Gt.Modify(1, 1);
        flag_1 = flag_2 = 1;			// #
        for(reg int i = 2; i <= N; i ++){
                int tmp_1 = Ft.Query(N-A[i]+1), tmp_2 = Gt.Query(A[i]);
                if(A[i-1] < A[i]) flag_1 = 0, Gt.tim ++;	// #
                else flag_2 = 0, Ft.tim ++;					// #
                Ft.Modify(N-A[i-1]+1, tmp_2), Gt.Modify(A[i-1], tmp_1);
        }
        printf("%d\n", (Ft.Query(N)+Gt.Query(N)-flag_1-flag_2)%mod);
        return 0;
}