Description
N clients are waiting in line to collect their packages at the post office. Packages arrive at the post office one by one. For simplicity, we will number the packages from 1 to N in the order in which they arrive. Each client wants to collect a single package; the K-th client in the line (for K from 0 to N−1) wants to collect package number client[K].
After a package arrives, one of the following events happens:
-
if the first client in the line wants to collect the package, they pick it up and leave the line;
-
otherwise, the package is put on the shelf.
If the first client wants to collect a package from the shelf, they leave the line and collect the package. Please note that only the first client from the line can collect their package. How many packages will be stored on the shelf at the same time?
Write a Python program which, given an array client, returns the maximum number of packages that will be stored on the shelf at the same time.
Examples:
- For client = [3, 2, 4, 5, 1], the function should return 2. The following events happen:
-
the first client waits for package number 3, so packages with numbers 1 and 2 are put on the shelf;
-
package number 3 arrives and the first client collects it;
-
the second client collects package number 2 from the shelf;
-
the third and fourth clients wait for packages number 4 and 5, and collect them as they arrive;
-
the last client collects package 1 from the shelf.
- For client = [1, 2, 3, 4, 5], the function should return 0. Every client collects their package just as it arrives.
- For client = [3, 2, 7, 5, 4, 1, 6], the function should return 4.
Input
The first line contains the number of test cases (t). (1 <= t <= 10)
The next line contains the parcel numbers to be received in order. When the number of customers is N, the parcel numbers range from 0 to N-1 and are non-repeating (1 <= N <= 1,000). This line is repeated as many times as the number of test cases.
Output
For each test case, output the maximum number of packages stored on the shelf at the same time, one per line.
3
3 2 4 5 1
3 2 7 5 4 1 6
1 2 3 4 5