The above sentences are records that journalists would like to include in newspapers and magazines. These records share a common pattern: a time period, and the minimum value happened in that period. We would use (length, value) to represent a record, where length is the length of the time period, and value is the minimum value in that period.
However, not all records are interesting to the journalists, such as the following one:
Given that there is a (5,2) record, no journalist would like to report the (3,1) one.
Formally, a record (l1, v1) is not interesting if there is another record (l2, v2) satisfying one of the following criteria:
Given a time series (the value in each time unit),
please help the journalists to identify the number of interesting records.
The first line of the input contains an integer T, which is the number of test cases.
Each test case consists of two lines.
The first line has an integer n, indicating the number of time units in the series.
The second line has n integers a1,...,an, where ai denotes the value in the i-th time unit.
(1 <= n <= 200000, |ai| < 231)
Please output one integer for each test case, indicating the number of interesting records.
A record may occur more than once in the series, but it should be counted only once.
2 8 1 3 7 5 8 2 4 6 4 8 6 9 3
5 3
The interesting records in the first sample are: (8,1), (7,2), (4,3), (3,5) and (1,8).
The interesting records in the second sample are: (4,3), (3,6) and (1,9).
Migrated from old NTUJ.
Ferng
| No. | Testdata Range | Score |
|---|