Problem
新しいゲーム (ボウリングとビリヤードのハイブリッド) をプレイする場合、1 から N までの番号が付けられた N 個のボールが使用されます。ゲームの開始時に、これらのボールは番号順に一列に並べる必要があります。ゲーム中に順番が変わる場合があります。
次の試合開始までにボールを揃えるために、次のような工夫をしています。このデバイスは、ボールの上を移動して「吸う」ことができるヘッドで構成されていますそして「吐き出す」風船。この装置をよりよく理解するために、ボールを吸い込んで正しい場所に移動し、反対方向に吹き飛ばしてボールを「吐き出す」ことができる掃除機を想像してみてください。
風船が吸い込まれると、吸い込まれた風船の右側にあった風船がすべて左に移動します。 "吐き出す"ボールは任意の 2 つのボールの間 (および最初のボールの前または最後のボールの後) にある可能性があり、これらのボールの間にスピッティング ボールが挿入され、挿入されたボールの右側にあるすべてのボールが右にシフトされます。 .
同時に複数のボールをデバイスに吸い込むことができ、ボールを吐き出すときは、最後に吸い込まれたボールが最初に吐き出され、次に最後から 2 番目のボールが吐き出されます。 (つまり、デバイスはスタックの原理で動作します)。ボールは一度に 1 つずつ吐き出されます。 1 つのボールだけを吐き出し、残りはデバイス内に残します (この場合、同じ場所または別の場所でボールを「吐き出す」か、新しいボールを吸い込むことができます)。
説明されている操作の中で最もエネルギーを消費するのは、ボールを吸う操作であるため、そのような操作の数を最小限に抑えたいと考えています。
ボールの初期配置が与えられたときに、ボールを番号順に並べるのに必要な最小吸引回数を決定するプログラムを作成してください。
入力
入力ファイルでは、数値 N が最初に与えられます —ボールの数 (1≤N≤1000)。次に、現在の位置でボールの番号を左から右に順番に示す N 個の番号があります (各番号 - 1 から N までで、各番号はシーケンス内で 1 回だけ発生します)。
出力
単一の数値を出力する —ボールを番号順に並べるのに必要なボール吸引操作の最小回数。
サンプル テストに関するコメント
1.たとえば、2 番目のバルーンを吸って、1 番目と 3 番目のバルーンの間で吐き出すことができます。
2.>こんなことができます。最初に
番号 1 の風船を吸い、次に – を吸います。次に、先頭に移動し、4 番目のボール (これがボール番号 2 になります) の前にボールを吐き出します。次に3番の風船を吸い込んで2番と4番の風船の間に吐き出します.次に先頭に移動して1番の風船を吐き出します.しかし,この例の風船の順序はこれだけではありません.
<本体>
| 入力 |
出力 |
|
3
2 1 3
|
1 |
|
4
4 3 2 1
|
3 |
チーム オリンピアード、モスクワ チーム オリンピアード、9 年生から 11 年生、2007 年、リーグ A、プロブレム F