#P15596. [2025年山东第一轮集训] 火山

[2025年山东第一轮集训] 火山

题目描述

给定一个长为 nn 的字符串

a=a1a2⋯an,a=a_1a_2\cdots a_n,

保证 aa 只包含 1,2,31,2,3 三种字符。

你会做若干次操作。每次操作是选择 aa 的三个位置

1≤i<j<k≤n,1\le i<j<k\le n,

使得 (ai,aj,ak)(a_i,a_j,a_k) 严格单调增或严格单调减,然后删去这三个位置。

设删去的三元子序列中有 xx 个单调增,yy 个单调减,请求出有多少种可能的二元组 (x,y)(x,y)。

输入格式

第一行,一个正整数 tt,表示数据组数。

接下来,对于每组数据:

  • 第一行,一个正整数 nn;
  • 第二行,一个长为 nn 的字符串 aa。

输出格式

对于每组数据,输出一行一个正整数,表示可能的二元组 (x,y)(x,y) 的个数。

样例输入 #1

3
5
12321
14
12311311132133
12
121111321212

样例输出 #1

3
5
3

子任务

对于所有数据:

1≤t≤20,1\le t\le 20, 1≤n≤106,1\le n\le 10^6, ai∈{1,2,3}.a_i\in\{1,2,3\}.
测试点 n≤n\le
1 1515
2, 3 200200
4, 5 10001000
6 30003000
7, 8 10510^5
9, 10 10610^6