魔法の訓練 (Magical Training)

いもすは、14歳の時に魔法に目覚めた魔法少女である。

いもすは、161日後に来たるべき強敵「ウォーターリークス」を倒すために、魔力を高める訓練をしている。その訓練とは次のようなものである。

N 個の、それぞれ魔力の値が定められている石があり、1列に並んでいる。

連続したいくつかの石を選んで、それらを魔力の昇順になるように、すなわちより番号の小さい位置にはより魔力の小さい石が置かれるように並べ替えることができると、いもすの魔力を上げることができる。どの石もとても重いので、並べ替えるときは、魔法を使って隣り合う石同士を入れ替えることしかできない。

しかし、石は非常にたくさんあるため、並べ替えるのはとても大変である。魔力を上げることができる石の選び方はいくつかあるため、最も楽なものを選びたい。さらに、石の魔力の強さは時とともに変化することがある。魔力の強さの変化の仕方は、すでにいもすの魔法によりすべて予測されている。

いもすの魔法の訓練を助けるために、次に示すようなプログラムを書いてほしい。

N 個の整数からなる配列 A が与えられる。石の列の左端から i+1 個目の石を石 i と番号づけ、A[i] は石 i の魔力を表すとする。

次のプロシージャを実装せよ:

• 次のパラメータを持つプロシージャ init(N, A):
  • N -- 石の数。石には左から順に 0 から N-1 までの異なる整数の番号がつけられている。
  • A -- 石の魔力を表す整数の配列。0 ≦ i ＜ N に対し 1 ≦ A[i] ≦ N を仮定してよい。
  このプロシージャは最初に update(i, x) または train(p, q) が呼び出される前に1度だけ呼び出される。このプロシージャは戻り値を持たない。
• 次のパラメータを持つプロシージャ update(i, x):
  • i -- 魔力が変化する石の番号。
  • x -- 魔力が変化した後の石 i の魔力。1 ≦ x ≦ N を仮定してよい。
  このプロシージャは複数回呼び出される。1回の呼び出しは1回の魔力の変化に対応する。このプロシージャは戻り値を持たない。
• 次のパラメータを持つプロシージャ train(p, q):
  • p -- 並べ替える石の左端の番号。0 ≦ p ＜ N を仮定してよい。
  • q -- 並べ替える石の右端の番号。p ≦ q ＜ N を仮定してよい。
  このプロシージャは複数回呼び出される。1回の呼び出しは石 p から石 q (両端も含む)までの石を、隣り合う石を入れ替えることによって p の位置から q の位置に向かって魔力の昇順に並べ替える訓練に対応している。それぞれの呼び出しは対応する訓練のために必要な最小の石の入れ替え回数を戻り値として返す必要がある。ただし、実際には石の並べ替えは行わず、入れ替えの回数だけを求めるものとする。

N = 6, はじめの石の魔力の状態が

の場合を考える。

最初、プロシージャ init は上記のパラメータで呼び出される。その後、複数回の update または train の呼び出しが任意の順番で行われる。以下に呼び出しと正しい戻り値の例を示す: