Anbarın avtomatlaşdırılması
Компания anbarın avtomatlaşdırılması ilə məşğuldur. Anbarda n növ mal saxlanılır, 1-dən n-ə qədər nömrələnmişdir, hər növ mal öz otağında saxlanılır. i növ mal i nömrəli otaqda saxlanılır.
Xüsusi robot anbardan malların alınması üçün sorğuları yerinə yetirir. Robot anbar otaqlarına giriş üçün xüsusi elektron kartlardan istifadə edir. Kartlar robotda xüsusi bölmədə saxlanılır, oradan o, yuxarıdakı kartı çıxara bilər. Çıxarılan kartı robot bölməyə istənilən yerə qaytara bilər: yuxarı mövqeyə, iki kartın arasına və ya ən aşağı mövqeyə.
Otağı açmaq üçün robot aşağıdakı kimi hərəkət edir. O, kartları saxlama bölməsindən çıxarır və lazım olan otağın kartı yuxarı mövqedə olana qədər onları geri qaytarır. Bundan sonra, bu kartı çıxarıb otağı açmaq üçün istifadə edir və sonra kartı saxlama bölməsinə geri qaytarır. Əgər robotun ümumilikdə x kart çıxarması lazım gəlibsə, o cümlədən otağı açmaq üçün istifadə etdiyi kartı, deyəcəyik ki, robot otağı açmaq üçün x hərəkət edib.
İş gününün əvvəlində robota m malın verilməsi sifariş olunub: a[1], a[2], ..., a[m]. Robot malları məhz bu ardıcıllıqla verməlidir. Bunun üçün o, ardıcıl olaraq aşağıdakı hərəkətləri yerinə yetirir: növbəti malın olduğu otağı açır, malı götürür, otağı bağlayır və malı müştəriyə verir. Bundan sonra robot növbəti malın verilməsinə keçir.
Başlanğıcda elektron kartlar bölmədə aşağıdakı ardıcıllıqla yerləşir, yuxarıdan aşağıya: b[1], b[2], ..., b[n]. Hər bir otaq üçün bölmədə dəqiq bir kart var.
Anbardan malların verilmə vaxtı, robotun növbəti otağın kartını tapmaq üçün saxlama bölməsindən yuxarı kartı neçə dəfə çıxarmasından asılıdır. Robotun otaqları açmaq üçün ümumi hərəkət sayını minimallaşdırmaq üçün çıxarılan kartları hara qaytarmalı olduğunu seçmək lazımdır.
Verilmiş tam ədədlər n və m, veriləcək malların ardıcıllığı a[1], a[2], ..., a[m] və kartların saxlama bölməsindəki başlanğıc mövqeyi b[1], b[2], ..., b[n] əsasında proqram yazın ki, robotun bütün otaqları lazım olan ardıcıllıqla açması üçün minimum neçə hərəkət etməli olduğunu müəyyən etsin. Hər çıxarılan kart üçün onu optimal hərəkət sayına nail olmaq üçün hansı mövqeyə qaytarmaq lazım olduğunu da göstərin.
Giriş məlumatları
Birinci sətir iki tam ədəd n və m (1 ≤ n, m ≤ 3 * 10^5) - mal növlərinin sayı və anbardan verilməsi lazım olan malların sayı.
İkinci sətir m tam ədəd a[1], a[2], ..., a[m] (1 ≤ a[i] ≤ n) - anbardan verilməsi lazım olan malların növləri, verilməli olduğu ardıcıllıqla sadalanmışdır.
Üçüncü sətir n müxtəlif tam ədəd b[1], b[2], ..., b[n] (1 ≤ b[i] ≤ n) - kartların saxlama bölməsində başlanğıcda yerləşdiyi ardıcıllıq, yuxarıdan aşağıya sadalanmışdır.
Çıxış məlumatları
Birinci sətir k ədədini - robotun malları verilmiş ardıcıllıqla verməsi üçün lazım olan minimum hərəkət sayını göstərməlidir.
Sonra k ədəd yazın. Robotun hər bir hərəkəti üçün çıxarılan kartı saxlama bölməsinə qaytarmalı olduğu mövqeni yazın. Əgər kart ən yuxarı mövqeyə qaytarılırsa, 1 yazılmalıdır, bir kartdan sonra 2, və s., son mövqe üçün n yazılmalıdır.
Əgər ümumi hərəkət sayını minimallaşdırmaq üçün bir neçə yol varsa, onlardan istənilən birini yazın.
İzah
İkinci nümunədə robotun bölməsində kartlar aşağıdakı kimi hərəkət edir:
