假设您有两个点 $$$p = (x_p, y_p)$$$ 和 $$$q = (x_q, y_q)$$$。我们将它们之间的曼哈顿距离表示为 $$$d(p, q) = |x_p - x_q| + |y_p - y_q|$$$。
假设三个点 $$$p$$$、$$$q$$$、$$$r$$$ 形成一个坏三元组,如果 $$$d(p, r) = d(p, q) + d(q, r)$$$。
假设数组 $$$b_1, b_2, \dots, b_m$$$ 是好的,如果无法选择三个不同的索引 $$$i$$$, $$$j$$$, $$$k$$$ 使得点 $$$(b_i, i)$$$, $$$(b_j, j)$$$ 和 $$$(b_k, k)$$$ 形成一个糟糕的三元组。
给你一个数组 $$$a_1, a_2, \dots, a_n$$$。计算 $$$a$$$ 的好子数组的数量。数组 $$$a$$$ 的子数组是数组 $$$a_l, a_{l + 1}, \dots, a_r$$$ 对于某些 $$$1 \le l \le r \le n$$$。
请注意,根据定义,长度为 $$$1$$$ 和 $$$2$$$ 的子数组是好的。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5000$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。
保证 $$$n$$$ 的总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印数组 $$$a$$$ 的好子数组的数量。
示例
输入 #1
3 4 2 4 1 3 5 6 9 1 9 6 2 13 37
输出 #1
10 12 3
注意
在第一个测试用例中,可以证明 $$$a$$$ 的任何子数组都是好的。例如,子数组 $$$[a_2, a_3, a_4]$$$ 很好,因为它仅包含三个元素并且:
- $$$d((a_2, 2), (a_4, 4)) = |4 - 3| + |2 - 4| = 3$$$ $$$<$$$ $$$d((a_2, 2), (a_3, 3)) + d((a_3, 3), (a_4, 4)) = 3 + 1 + 2 + 1 = 7$$$;
- $$$d((a_2, 2), (a_3, 3))$$$ $$$<$$$ $$$d((a_2, 2), (a_4, 4)) + d((a_4, 4), (a_3, 3))$$$;
- $$$d((a_3, 3), (a_4, 4))$$$ $$$<$$$ $$$d((a_3, 3), (a_2, 2)) + d((a_2, 2), (a_4, 4))$$$;
在第二个测试用例中,例如,子数组 $$$[a_1, a_2, a_3, a_4]$$$ 不好,因为它包含错误的三元组 $$$(a_1, 1)$$$, $$$(a_2, 2)$$$, $$$(a_4, 4)$$$:
- $$$d((a_1, 1), (a_4, 4)) = |6 - 9| + |1 - 4| = 6$$$;
- $$$d((a_1, 1), (a_2, 2)) = |6 - 9| + |1 - 2| = 4$$$;
- $$$d((a_2, 2), (a_4, 4)) = |9 - 9| + |2 - 4| = 2$$$;
所以,$$$d((a_1, 1), (a_4, 4)) = d((a_1, 1), (a_2, 2)) + d((a_2, 2), (a_4, 4))$$$。