Kirill and Mushrooms
Contest: Codeforces Round 935 (Div. 3)
Difficulty rating: 1900
Tags: data structures, sortings

As soon as everyone in the camp fell asleep, Kirill sneaked out of the tent and went to the Wise Oak to gather mushrooms.

It is known that there are $$$n$$$ mushrooms growing under the Oak, each of which has magic power $$$v_i$$$. Kirill really wants to make a magical elixir of maximum strength from the mushrooms.

The strength of the elixir is equal to the product of the number of mushrooms in it and the minimum magic power among these mushrooms. To prepare the elixir, Kirill will sequentially pick one mushroom growing under the Oak. Kirill can gather mushrooms in any order.

However, it's not that simple. The Wise Oak informed Kirill of a permutation of numbers $$$p$$$ from $$$1$$$ to $$$n$$$. If Kirill picks only $$$k$$$ mushrooms, then the magic power of all mushrooms with indices $$$p_1, p_2, \dots, p_{k - 1}$$$ will become $$$0$$$. Kirill will not use mushrooms with zero magic power to prepare the elixir.

Your task is to help Kirill gather mushrooms in such a way that he can brew the elixir of maximum possible strength. However, Kirill is a little scared to stay near the oak for too long, so out of all the suitable options for gathering mushrooms, he asks you to find the one with the minimum number of mushrooms.

A permutation of length $$$n$$$ is an array consisting of $$$n$$$ different integers from $$$1$$$ to $$$n$$$ in any order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears in the array twice) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$, but $$$4$$$ appears in the array).

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 200\,000$$$) — the number of mushrooms.

The second line contains an array $$$v$$$ of size $$$n$$$ ($$$1\le v_i \le 10^9$$$) — the magic powers of the mushrooms.

The third line contains a permutation $$$p$$$ of numbers from $$$1$$$ to $$$n$$$.

It is guaranteed that the sum of the values of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output format:
For each test case, output two integers separated by a space — the maximum strength of the elixir that can be brewed and the minimum number of mushrooms that Kirill needs to use for this.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, you need to take the mushrooms with indices $$$1$$$ and $$$2$$$, so the strength of the elixir is equal to $$$2 \cdot \min(a_1, a_2) = 2 \cdot \min(9, 8) = 2 \cdot 8 = 16$$$. Note that the magic power of the mushroom with index $$$3$$$ after picking two mushrooms will become $$$0$$$.

Example input:
6
3
9 8 14
3 2 1
5
1 2 3 4 5
1 2 3 4 5
6
1 2 3 4 5 6
6 5 4 3 2 1
5
1 4 6 10 10
2 1 4 5 3
4
2 2 5 5
4 2 3 1
5
1 2 9 10 10
1 4 2 3 5

Example output:
16 2
9 3
8 2
20 2
5 1
20 2

Editorial:
Consider a fixed number $$$k$$$ — the amount of mushrooms in the elixir. In this case, we need to maximize the minimum of the taken numbers. We will iterate through the numbers in descending order: until we collect $$$k$$$ numbers, we iterate over the next number. If its index is greater than or equal to $$$k$$$, we take this number as the answer, otherwise we skip it.
If we iterate through $$$k$$$, we get a solution in $$$\mathcal{O}(n^2)$$$ time. How can we speed it up? Notice that at incrementing $$$k$$$, only a few numbers change: $$$v_{p_k}$$$ becomes zero, if we have already taken it, then we need to take the next one in descending order. Also, we need to take the next number in descending order, because we are incrementing $$$k$$$. After sorting, we can traverse the array in linear time. We keep a pointer $$$j$$$ to the last taken element, as well as an array $$$\text{used}$$$ — whether the $$$i$$$-th number is taken, and an array $$$\text{zero}$$$ — whether the $$$i$$$-th number is turned into zero. Every time we move $$$j$$$, we check that $$$\text{zero}_j = \text{false}$$$, and if so, we take the number and set $$$\text{used}_j = \text{true}$$$.
Complexity: $$$\mathcal{O}(n \log n)$$$.