AIOC Banner

Problem: Bookshelf

Want to try solving this problem? You can submit your code online if you log in or register.


Input File: standard input
Output File: standard output
Time Limit: 1 second
Memory Limit: 32 MB

In the town of Harigato, there is a library that holds a collection of books on the ancient order of the Harigatan monks. These books are stored side-by-side in a long line, and not all books are of the same height. Some of these books are irreplaceable as they are thousands of years old.

Unfortunately, an outbreak of mildew has begun in the collection, destroying the books that are infected with mildew. Mildew infections begin with one or more infected books. If a shorter book is next to an infected book, it will be safe from the mold. However, books at the same height or taller than an adjacent infected book will also become infected.

The library would like to find out how such outbreaks would affect their collection and they have turned to you for help. Given the order and heights of books along the shelf, which books are irreplaceable, and which books start off with a mildew infection, your task is to find out how many irreplaceable books would be lost.


The first line of the input will contain three positive integers, N M I, representing the total number of books on the shelf, the number of books affected by mildew and the number of books that are irreplaceable, respectively. There will be at most 100,000 books on the shelf.

The second line of the input will contain N positive integers, specifying the height of the N books. The heights are all less than 1,000,000. The books sit on the shelf in the order given and are numbered from 1 ...N.

The third line of the input will contain M integers, specifying which books have been infected with mildew. Each of these integers will be between 1 and N. No book will appear more than once in this list.

The fourth and final line of input will contain I integers, specifying which books are irreplaceable. Each of these integers will be between 1 and N. No book will appear more than once in this list.


Your output should consist of a single integer - the number of irreplaceable books which would be infected with mildew in the given scenario.

Sample Input

10 2 6
12 9 10 10 18 13 19 14 12 16
2 8
1 3 5 7 9 10

Sample Output



The sample data corresponds to the bookshelf below. The books infected with mildew are shaded. The irreplaceable books are marked with a star. The mildew from book 2 can spread to irreplaceable books 1, 3 and 5. The mildew from book 8 can spread only to irreplaceable book 7. Thus there are a total of 4 irreplaceable books infected with mildew after the infection has spread.



The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.


Privacy statement
© Australian Mathematics Trust 2001-2023

Page generated: 27 March 2023,  3:46pm AEDT