Gondol

Mao-Kong gondolu Taybeyin məşhur turistik məkanıdır. Bu, bir stansiyası və n gondolası olan dairəvi bir asma yoldur, burada gondolalar 1-dən n-ə qədər nömrələnmişdir. Gondolalar bu yolda bir istiqamətdə hərəkət edir. Əvvəlcə, i nömrəli gondoladan sonra stansiyadan i < n üçün (i + 1) nömrəli gondola keçir. Əgər i = n-dirsə, növbəti keçən gondola 1 nömrəli olur.

Bəzən gondolalar xarab ola bilər. Xoşbəxtlikdən, istifadə olunmamış ehtiyat gondolalarımız var, bunlar (n + 1), (n + 2) və s. nömrələnmişdir. Gondola xarab olduqda, onu istifadə olunmamış ən kiçik nömrəli ehtiyat gondola ilə əvəz edirlər. Yeni gondola xarab olanın yerinə qoyulur. Məsələn, beş gondola varsa və biri xarab olarsa, onu 6 nömrəli gondola ilə əvəz edəcəklər.

Siz stansiyada dayanıb keçən gondolalara baxmağı sevirsiniz. Gondola ardıcıllığı, stansiyadan keçən gondolaların n nömrəli ardıcıllığıdır. Ola bilər ki, siz stansiyaya gəlməmişdən əvvəl bir və ya bir neçə gondola xarab olub, amma siz gondolaların hərəkətinə baxarkən heç biri xarab olmur.

Qeyd edək ki, eyni gondola ardıcıllığına bir neçə ardıcıllıq uyğun gələ bilər, hansı gondolanın stansiyaya birinci gəldiyindən asılı olaraq. Məsələn, heç bir gondola xarab olmayıbsa, mümkün gondola ardıcıllıqları (2, 3, 4, 5, 1) və (4, 5, 1, 2, 3) ola bilər, amma (4, 3, 2, 5, 1) gondola ardıcıllığı deyil, çünki gondolalar səhv ardıcıllıqla gəlib.

Əgər 1 nömrəli gondola xarab olarsa, siz gondola ardıcıllığını (4, 5, 6, 2, 3) görə bilərsiniz. Bundan sonra 4 nömrəli gondola xarab olarsa, onu 7 nömrəli gondola ilə əvəz edəcəklər və siz ardıcıllığı (6, 2, 3, 7, 5) görə bilərsiniz. Bundan sonra 7 nömrəli gondola xarab olarsa, onu 8 nömrəli gondola ilə əvəz edəcəklər və siz ardıcıllığı (3, 8, 5, 6, 2) görə bilərsiniz.

Əvəzləmə ardıcıllığı, gondolaların xarab olduğu ardıcıllıqdır. Əvvəlki nümunədə əvəzləmə ardıcıllığı - (1, 4, 7). Əvəzləmə ardıcıllığı r gondola ardıcıllığını g yaradır, əgər gondolalar r əvəzləmə ardıcıllığına uyğun olaraq xarab olub əvəz edildikdən sonra siz gondola ardıcıllığını g görə bilirsinizsə.

Gondola ardıcıllığının yoxlanması

İlk üç alt məsələdə siz gondola ardıcıllığının düzgün olub-olmadığını yoxlamalısınız. Siz valid(n, inputSeq) funksiyasını həyata keçirməlisiniz, burada

• n - ardıcıllığın uzunluğu;

• inputSeq - uzunluğu n olan massiv, inputSeq[i] - i yerindəki ardıcıllığın elementi, 0 ≤ i ≤ n - 1 üçün;

• funksiya verilmiş ardıcıllıq gondola ardıcıllığıdırsa 1, əks halda 0 qaytarmalıdır.

Alt məsələlər 1, 2, 3

Nümunələr

Aşağıdakı cədvəldə gondola ardıcıllığı olan və olmayan ardıcıllıqların nümunələri verilmişdir.

Əvəzləmə ardıcıllığı

Növbəti üç alt məsələdə siz gondola ardıcıllığını yaradan əvəzləmə ardıcıllığını qurmalısınız. Siz bu cür ardıcıllıqlardan istənilən birini qura bilərsiniz.

Siz replacement(n, gondolaSeq, replacementSeq) funksiyasını həyata keçirməlisiniz, burada

• n - ardıcıllığın uzunluğu;

• gondolaSeq - uzunluğu n olan massiv. gondolaSeq-in gondola ardıcıllığı olduğu təmin edilir, gondolaSeq[i] - ardıcıllığın i-ci elementi, 0 ≤ i ≤ n - 1 üçün;

• funksiya l - əvəzləmə ardıcıllığının uzunluğunu qaytarmalıdır;

• replacementSeq - əvəzləmə ardıcıllığını saxlamaq üçün kifayət qədər böyük massiv; siz əvəzləmə ardıcıllığını qaytarmalı və onun i-ci elementini replacementSeq[i]-ə yazmalısınız, bütün 0 ≤ i ≤ l - 1 üçün.

Alt məsələlər 4, 5, 6

Nümunələr

Əvəzləmə ardıcıllıqlarının sayılması

Növbəti dörd alt məsələdə siz verilmiş ardıcıllığı (bu gondola ardıcıllığı ola bilər və ya olmaya bilər) yaradan əvəzləmə ardıcıllıqlarının sayını 10^9 + 9 moduluna görə müəyyən etməlisiniz. Siz countReplacement(n, inputSeq) funksiyasını həyata keçirməlisiniz.

• n - verilmiş ardıcıllığın uzunluğu;

• inputSeq - uzunluğu n olan massiv, inputSeq[i] - verilmiş ardıcıllığın i-ci elementi, bütün 0 ≤ i ≤ n - 1 üçün.

• əgər verilmiş ardıcıllıq gondola ardıcıllığıdırsa, siz gondola ardıcıllığını yaradan əvəzləmə ardıcıllıqlarının sayını müəyyən etməli və bu sayın 10^9 + 9-a bölünməsindən qalanı qaytarmalısınız. Əgər verilmiş ardıcıllıq gondola ardıcıllığı deyilsə, funksiya 0 qaytarmalıdır. Əgər verilmiş ardıcıllıq gondola ardıcıllığıdırsa, amma heç bir gondola xarab olmayıbsa, funksiya 1 qaytarmalıdır.

Alt məsələlər 7, 8, 9, 10

Nümunələr

Giriş məlumatları

Birinci sətir sizin proqramınızın həll etməli olduğu alt məsələnin nömrəsini t ehtiva edir (1 ≤ t ≤ 10);

İkinci sətir verilmiş ardıcıllığın uzunluğunu n ehtiva edir;

Əgər t 4, 5 və ya 6-ya bərabərdirsə, üçüncü sətir gondolaSeq[0], ..., gondolaSeq[n-1] ehtiva edir. Əks halda, o, inputSeq[0], ..., inputSeq[n-1] ehtiva edir.

Çıxış məlumatları

Hər bir sual üçün müvafiq cavab çıxarılacaq.