시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 | 512 MB | 4 | 3 | 3 | 75.000% |
Recently, you have been hired by an investment fund. You quickly developed a feeling, though, that something here was amiss, especially when a client's money
has been invested in two companies carefully selected by their best astrologist.
Unfortunately, for the last $n$ days the stock prices were (mostly) falling. The boss called an urgent meeting.
The boss looked at you. It wasn't exactly a look of earnest approval...
Now you have some bruises, a lot of stairs to climb, and much work to do. Given the stock prices of the two companies for $n$ consecutive days, find the maximum subset of days so that both price subsequences are (strictly) increasing. It is enough to output the maximum number of days.
The first line of input contains the number of test cases $z$. The descriptions of the test cases follow.
The first line of every test case contains the number of days $n$ ($1 \leq n \leq 200\,000$). Then two lines follow. The first one contains $n$ positive integers not exceeding $10^9$ -- the stock prices of the first company for all $n$ days. The second line contains the second company's prices, in the same format.
The total number of days in all test cases does not exceed $2\,000\,000$.
For each test case output in a separate line a single integer -- the maximum possible number of days.
1 6 1 2 6 3 4 6 4 1 3 5 7 7
3