Security Vault System#5657
A digital security vault system uses nested encryption containers where lower-level encryptions are placed inside higher-level ones. Each security vault can be decrypted to reveal a container with a lower encryption level inside, which has, in turn, another container inside, and so on.
A corporate data center recently completed a system migration where multiple vault sets with similar encryption protocols were transferred. Each set differed only in the number of nested encryption levels. Unfortunately, during the migration process, an automated script malfunctioned and separated all the vault sets, placing all individual encryption containers in a sequence. There are containers in the sequence, each with an integer encryption level. You need to reassemble the vault sets, knowing neither the number of sets nor the number of containers in each set. You know only that every complete set consists of containers with consecutive encryption levels from to some number , which may vary between the different sets.
When reassembling the sets, you must follow these rules:
You can nest a container or a nested group of containers only inside a container with a higher encryption level.
You can combine two groups of containers only if they are adjacent in the sequence.
Once a container becomes a member of a group, it cannot be transferred to another group or permanently separated from the group. It can be temporarily separated only when combining two groups.
Your processing time is valuable, and you want to complete this reassembly as quickly as possible. The only time-consuming part of this task is decrypting and subsequently re-encrypting a container, so you want to minimize how often you do this. For example, the minimum number of decryptions (and subsequent re-encryptions) when combining group [1, 2, 6] with the group is two, since you have to decrypt the containers with encryption levels and . When combining group [1, 2, 5] with the group , you need to perform three decryptions.
Write a program to calculate the minimum number of decryptions required to combine all separated vault sets.
The input consists of a single test case. A test case consists of two lines. The first line contains one integer (1 \le n \le 500) representing the number of individual containers in the sequence. The second line contains positive integers specifying the encryption levels of the containers in the order they appear in the sequence. Each encryption level is between and inclusive.
Display the minimum number of decryptions required when reassembling the vault sets. If reassembling cannot be done (some containers might have been lost during migration), display the word impossible.
Example 1