Description

小张在暑假时间进行了暑期社会调查。调查的内容是楼房的颜色如何影响人们的心情。于是他找到了一个楼房从左到右排成一排的小区，这个小区一共有

栋楼房，每个楼房有一个颜色

和一个高度

。小张调查的内容为每次他站在第

栋楼和第

栋楼之间向左看，他记录下此时他看到的楼房颜色数作为他的调查结果。

由于小张在暑假时间沉迷游戏来不及做实地调查，只好拜托你将调查结果告诉他。

Input

本题有多组数据。

每组数据第一行一个整数

。表示有

栋楼房从左到右排成一排。

第二行

个数，表示每个楼房的颜色

。

第三行

个数，表示每个楼房的高度

。

数据保证所有组数据的

。

Output

每组数据输出

个数，第

个数表示他站在第

栋楼和第

栋楼之间向左看，能够看到的楼房颜色数。

Notes

在从左向右看楼房的时候，左边较矮的楼房会被右边较高的楼房挡住。

---

C++整体代码

#include <iostream>   
#include <vector>   
#include <stack>   
#include <cstdio>
using namespace std;int main() {int num;cin >> num;stack<int> stack_c, stack_h;while (num--) {int n;cin >> n;stack_c = stack<int>();stack_h = stack<int>();vector<long long> c_class(1000000, 0);vector<long long> c(n,0), h(n,0);long long c_num = 0;//输入楼房颜色   for (int i = 0; i < n; i++) {scanf("%lld", &c[i]);}//输入楼房高度  for (int i = 0; i < n; i++) {scanf("%lld", &h[i]);}//遍历楼房   for (int i = 0; i < n; i++) {if (stack_h.empty() || h[i] < stack_h.top()) {//如果栈顶为空或者新入栈元素小于栈顶   stack_h.push(h[i]);stack_c.push(c[i]);if (++c_class[c[i]] == 1) c_num++;}else if (stack_h.top() <= h[i]) {while (!stack_h.empty() && stack_h.top() <= h[i]) {if (--c_class[stack_c.top()] == 0) c_num--;stack_h.pop();stack_c.pop();}stack_h.push(h[i]);stack_c.push(c[i]);if (++c_class[c[i]] == 1) c_num++;}printf("%lld%c", c_num, i == n - 1 ? '\n' : ' ');}}return 0;
}