中文题面：给定一个长度为n的序列，求出最长的交替上升下降的序列，可以不连续。

交替上升下降的定义：

$e.g.$

1 7 4 9 2 5是一个交替上升下降的序列

蒟蒻想用dp解

dp[i][0/1]：在[1,i]中i这一点比上一点大、小的最长交替上升下降序列的长度
状态转移方程
dp[i][0]=max(dp[j][1])+1

其中1<=j<i且a[i]>a[j]
  
dp[i][1]=max(dp[j][0])+1

其中1<=j<i且a[i]<a[j]

请问怎么向最长上升子序列一样用单调队列从$O(n^2)$优化到$O(nlogn)$