定义一个对于数组 AAA 的函数 f(A)f(A)f(A) 为:
对于 AAA 的每一个下标 iii 建立一个顶点,对于 1≤i<j≤n1 \le i < j \le n1≤i<j≤n ,如果 Ai≤AjA_i \le A_jAi≤Aj 则在顶点 iii 和顶点 jjj 之间连一条双向边 (i,j)(i,j)(i,j) 。函数 f(A)f(A)f(A) 的值为这张图的联通块个数。
现给定数组 BBB ,整数 n,mn,mn,m ,BBB 中有一些 Bi=−1B_i=-1Bi=−1 的位置可以填入 [1,m][1,m][1,m] 中的任意整数,记一个合法的填充方案为 B′B'B′ 。求出 ∑f(B′)\sum f(B')∑f(B′) 。