Problem C
Nuclear Malware
Norway is facing imminent danger as one of its top secret nuclear power plants has just been taken over by malware. In snarky messages output by the malware, criminals are threatening to blow up the plant unless the government pays a hefty ransom that, if paid, would probably leave the country bankrupt.
Despite their best efforts, the government cyber defence unit have not been able to circumvent the malware’s real-time protection mechanisms; however, they have been able to dump an image of the system under attack. They have now hired you to dismantle the malware.
You started out with applying a bullet-proof machine learning technique, which quickly identified two suspicious memory locations that could contain the encryption key for the malware. The catch is that the other of these locations contains the priority queue of processes used by the power plant operating system - if touched carelessly, you risk initiating a nuclear meltdown!
Knowing that the priority queue of the operating system is implemented as a 1-based min heap, all that remains is to determine which of the two memory locations contains the heap, and which contains the malware encryption key!
Input
The first line of input consists of one integer $n$, the number of words (32-bit signed integers) in the memory location to check. The second line contains $n$ space-separated integers, the $i$’th of which, $w_ i$, corresponds to the content of the $i$’th memory location. Note that since we’re looking for a 1-based min heap, the first word of such a heap will always be $0$ and serve as padding.
Constraints
-
$1 \leq n \leq 100\, 000$
-
$-2^{31} \leq w_ i < 2^{31}$
Output
Output a single line containing “true” if the memory location could contain a 1-based min heap, and “false” otherwise.
| Sample Input 1 | Sample Output 1 |
|---|---|
10 0 1 2 3 4 5 6 7 8 9 |
true |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 1 2 3 4 |
false |
| Sample Input 3 | Sample Output 3 |
|---|---|
10 0 9 8 7 6 5 4 3 2 1 |
false |
