Superheroes

Interview

Time limit2sMemory limit1024 MB

Summary

Given skyscraper heights and hero positions, count the skyscrapers no hero can jump to, and find how many heroes can be removed without changing that count.

Level: Medium6 of 10
Topics: Stack, Intervals, Greedy
Solved: No attempts yet

Problem

Along a long street in Manhattan, $N$ skyscrapers of various heights stand in a row. Some of them have a superhero on the roof, and each superhero has secret powers.

A superhero on a skyscraper of height $A$ meters can jump to another skyscraper only if every skyscraper between the two, including the target, has height at most $A$ meters. A skyscraper is called unreachable if no superhero can jump to it.

Given the heights and the superhero positions, find:

the number of unreachable skyscrapers,
the maximum number of superheroes that can be removed so that the number of unreachable skyscrapers stays the same.

Input

The first line contains a natural number $N$ ( $1 \le N \le 300\,000$ ).

The second line contains $N$ natural numbers less than 1,000,000. The $i$ -th number is the height of the $i$ -th skyscraper.

The third line contains $N$ numbers, each 0 or 1. If the $i$ -th number is 1, a superhero is on top of the $i$ -th skyscraper. Otherwise, there is none.

Output

Print the answer to the first question on the first line, and the answer to the second question on the second line.

Hints

Explanation of the first test: the only superhero is on top of the second skyscraper, which has height 3. He can jump to his own skyscraper and to the skyscraper of height 1. He cannot jump to the skyscraper of height 2, because a skyscraper of height 4 stands between them.

Explanation of the second test: the only unreachable skyscraper is the one of height 5. If we remove the superhero from the second skyscraper, the first and second skyscrapers become unreachable. If we remove the superhero from the fifth skyscraper, the fourth and fifth become unreachable. So we cannot remove any superhero without changing the count.

Explanation of the third test: if we remove the superheroes from the 5th and 7th skyscrapers, the number of unreachable skyscrapers stays at 2. Note that a superhero on the skyscraper of height 4 can jump to the skyscraper of height 2 even though a skyscraper of height 3 stands between them.

Examples3

Example 1
Input
```
4
1 3 4 2
0 1 0 0
```
Expected output
```
2
0
```
Example 2
Input
```
5
1 3 5 2 3
0 1 0 0 1
```
Expected output
```
1
0
```
Example 3
Input
```
7
1 3 5 2 3 4 2
1 0 0 0 1 1 1
```
Expected output
```
2
2
```