Mao-Kong Gondola is a famous attraction in Taipei. The gondola system consists of a circular rail, a single station, and gondolas numbered consecutively from to running around the rail in a fixed direction. After gondola passes the station, the next gondola to pass the station will be gondola if , or gondola 1 if .

Gondolas may break down. Luckily we have an infinite supply of spare gondolas, which are numbered , , and so on. When a gondola breaks down we replace it (in the same position on the track) with the first available spare gondola, that is, the one with the lowest number. For example, if there are five gondolas and gondola 1 breaks down, then we will replace it with gondola 6.

You like to stand at the station and watch the gondolas as they pass by. A *gondola sequence* is a sequence of numbers of gondolas that pass the station. It is possible that one or more gondolas broke down (and were replaced) before you arrived, but none of the gondolas break down while you are watching.

Note that the same configuration of gondolas on the rail can give multiple gondola sequences, depending on which gondola passes first when you arrive at the station. For example, if none of the gondolas have broken down then both and are possible gondola sequences, but is not (because the gondolas appear in the wrong order).

If gondola 1 breaks down, then we might now observe the gondola sequence . If gondola 4 breaks down next, we replace it with gondola 7 and we might observe the gondola sequence . If gondola 7 breaks down after this, we replace it with gondola 8 and we may now observe the gondola sequence .

broken gondola | new gondola | possible gondola sequence |
---|---|---|

1 | 6 | |

4 | 7 | |

7 | 8 |

A *replacement sequence* is a sequence consisting of the numbers of the gondolas that have broken down, in the order in which they break down. In the previous example the replacement sequence is . A replacement sequence *produces* a gondola sequence if, after gondolas break down according to the replacement sequence , the gondola sequence may be observed.

#### Gondola Sequence Checking

In the first three subtasks you must check whether an input sequence is a gondola sequence. See the table below for examples of sequences that are and are not gondola sequences. You need to implement a function `valid`

.

`valid(n, inputSeq)`

`n`

: the length of the input sequence.`inputSeq`

: array of length ;`inputSeq[i]`

is element of the input sequence, for .- The function should return 1 if the input sequence is a gondola sequence, or 0 otherwise.

##### Subtasks 1, 2, 3

subtask | points | `inputSeq` | |
---|---|---|---|

1 | 5 | has each number from to exactly once | |

2 | 5 | ||

3 | 10 |

##### Examples

subtask | `inputSeq` |
return value | note |
---|---|---|---|

1 | `{1, 2, 3, 4, 5, 6, 7}` |
1 | |

1 | `{3, 4, 5, 6, 1, 2}` |
1 | |

1 | `{1, 5, 3, 4, 2, 7, 6}` |
0 | 1 cannot appear just before 5 |

1 | `{4, 3, 2, 1}` |
0 | 4 cannot appear just before 3 |

2 | `{1, 2, 3, 4, 5, 6, 5}` |
0 | two gondolas numbered 5 |

3 | `{2, 3, 4, 9, 6, 7, 1}` |
1 | replacement sequence `{5, 8}` |

3 | `{10, 4, 3, 11, 12}` |
0 | 4 cannot appear just before 3 |

#### Replacement Sequence

In the next three subtasks you must construct a possible replacement sequence that produces a given gondola sequence. Any such replacement sequence will be accepted. You need to implement a function `replacement`

.

`replacement(n, gondolaSeq, replacementSeq)`

`n`

is the length of the gondola sequence.`gondolaSeq`

: array of length ;`gondolaSeq`

is guaranteed to be a gondola sequence, and`gondolaSeq[i]`

is element of the sequence, for .- The function should return , the length of the replacement sequence.
`replacementSeq`

: array that is sufficiently large to store the replacement sequence; you should return your sequence by placing element of your replacement sequence into`replacementSeq[i]`

, for .

##### Subtasks 4, 5, 6

subtask | points | `gondolaSeq` | |
---|---|---|---|

4 | 5 | ||

5 | 10 | ||

6 | 20 |

##### Examples

subtask | `inputSeq` |
return value | `replacementSeq` |
---|---|---|---|

4 | `{3, 1, 4}` |
1 | `{2}` |

4 | `{5, 1, 2, 3, 4}` |
0 | `{}` |

5 | `{2, 3, 4, 9, 6, 7, 1}` |
2 | `{5,8}` |

#### Count Replacement Sequences

In the next four subtasks you must count the number of possible replacement sequences that produce a given sequence (which may or may not be a gondola sequence), modulo . You need
to implement a function `countReplacement`

.

`countReplacement(n, inputSeq)`

`n`

: the length of the input sequence.`inputSeq`

: array of length ;`inputSeq[i]`

is element of the input sequence, for .- If the input sequence is a gondola sequence, then count the number of replacement sequences that produce this gondola sequence (which could be extremely large), and
*return this number modulo*. If the input sequence is not a gondola sequence, the function should return 0. If the input sequence is a gondola sequence but no gondolas broke down, the function should return 1.

##### Subtasks 7, 8, 9, 10

subtask | points | `inputSeq` | |
---|---|---|---|

7 | 5 | ||

8 | 15 | , and at least of the initial gondolas did not break down. | |

9 | 15 | ||

10 | 10 |

##### Examples

subtask | `inputSeq` |
return value | replacement sequence |
---|---|---|---|

7 | `{1, 2, 7, 6}` |
2 | `{3, 4, 5}` or `{4, 5, 3}` |

8 | `{2, 3, 4, 12, 6, 7, 1}` |
1 | `{5, 8, 9, 10, 11}` |

9 | `{4, 7, 4, 7}` |
0 | `inputSeq` is not a gondola sequence |

10 | `{3, 4}` |
2 | `{1, 2}` or `{2, 1}` |

#### Implementation details

Your submission should implement all three subprograms described above (even if you only plan to solve some of the subtasks), using the following signatures.

##### C/C++ programs

```
int valid(int n, int inputSeq[]);
int replacement(int n, int gondolaSeq[], int replacementSeq[]);
int countReplacement(int n, int inputSeq[]);
```

##### Pascal programs

```
function valid(n: longint; inputSeq: array of longint): integer;
function replacement(n: longint; gondolaSeq: array of longint; var replacementSeq: array of longint): longint;
function countReplacement(n: longint; inputSeq: array of longint): longint;
```

## Comments

The points for this problem don't correspond to the subtasks—it's possible to have correct

`valid`

and`replacement`

functions but get 0/15. Perhaps simply add 1.5 points per correctly solved subtask? It seems like the batches correspond to subtasks as well.