English
Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/
Zadanie Logo (mat)
Matching
Memory limit: 64 MB
As a part of a new advertising campaign, a big company in Gdynia wants to put its logo somewhere in the city. The company is going to spend the whole advertising budget for this year on the logo, so it has to be really huge. One of the managers decided to use whole buildings as parts of the logo.
The logo consists of 
vertical stripes of different heights.
The stripes are numbered from 1 to 
from left to right.
The logo is described by a permutation 
of numbers
.
The stripe number 
is the shortest one, the stripe number 
is
the second shortest etc., finally the stripe 
is the tallest one.
The actual heights of the stripes do not really matter.
There are 
buildings along the main street in Gdynia.
To your surprise, the heights of the buildings are distinct.
The problem is to find all positions where the logo matches the buildings.
Help the company and find all contiguous parts of the sequence of
buildings which match the logo.
A contiguous sequence of buildings matches the logo if
the building number 
within this sequence is the shortest one, the
building number 
is the second shortest, etc.
For example a sequence of buildings of heights 
matches a logo
described by a permutation 
, since the building number 
(of
height 
) is the shortest one, the building number 
is the second
shortest and the building number 
is the tallest.
Input
The first line of the standard input contains two integers 
and 
(
).
The second line contains 
integers 
, forming a permutation of the
numbers 
.
That is, 
and 
for 
.
The third line contains 
integers 
- the heights of the buildings
(
for 
).
All the numbers 
are different.
In each line the integers are separated by single spaces.
Additionally, in test cases worth at least 35 points, 
and
, whereas in test cases worth at least 60 points,
and 
.
Output
The first line of the standard output should contain an integer 
, the
number of matches.
The second line should contain 
integers - 1-based indices of
buildings which correspond to the stripe number 1 from the logo in
a proper match.
The numbers should be listed in an increasing order and separated by
single spaces.
If 
, your program should print an empty second line.
Example
For the input data:
5 10 2 1 5 3 4 5 6 3 8 12 7 1 10 11 9
the correct result is:
2 2 6
Explanation: Both the sequences 
and
match the logo described by the permutation
. In particular, in the first sequence the
building number 
(of height 
) is the shortest one,
the building number 
(of height 
) is the second shortest,
the building number 
(of height 
) is the third shortest,
and so on.
Task authors: Tomasz Kulczynski, Tomasz Walen.