長さ $N$ の数列 $A = (A_1, A_2, \ldots , A_N)$ があります。

この数列に対して、 $Q$ 個のクエリを与えられた順番に処理し、各クエリ操作後の数列 $A$ の転倒数を出力してください。

クエリは以下の $4$ 種類のいずれかです。

• 1 x: $A$ の末尾に $x$ を追加する。

  • より形式的には、 $K = |A|$ とし、 $A = (A_1, A_2, \ldots, A_K)$ を $A = (A_1, A_2, \ldots, A_K, x)$ で置き換える。

• 2: $A$ の末尾の数を取り除く。

  • より形式的には、 $K = |A|$ とし、 $A = (A_1, A_2, \ldots, A_K)$ を $A = (A_1, A_2, \ldots, A_{K - 1})$ で置き換える。

• 3 x: $A$ の先頭に $x$ を追加する。

  • より形式的には、 $K = |A|$ とし、 $A = (A_1, A_2, \ldots, A_K)$ を $A = (x, A_1, A_2, \ldots , A_K)$ で置き換える。

• 4: $A$ の先頭の数を取り除く。

  • より形式的には、 $K = |A|$ とし、 $A = (A_1, A_2, \ldots, A_K)$ を $A = (A_2, A_3, \ldots , A_K)$ で置き換える。

• $2 \leq N \leq 10^5$
• $-10^5 \leq A_i \leq 10^5$
• $1 \leq Q \leq 10^5$
• $-10^5 \leq x \leq 10^5$
• 入力はすべて整数
• $A$ の長さが $2$ より小さくなるようなクエリは与えられない

部分点

以下の条件を満たすテストケースにすべて正解したとき、記載された点数が与えられる。

1. (10点) $N \leq 100, ~~ Q \leq 100, ~$ クエリは 1 x か 2 のどちらか
2. (10点) $N \leq 100, ~~ Q \leq 100$
3. (20点) $N \leq 2 \times 10^4, ~~ Q \leq 100$
4. (60点) 追加の制約はない

入力は以下の形式で標準入力から与えられる。

各クエリ $\mathrm{query}_i$ は以下に示す $4$ つの形式のいずれかである。

$Q$ 行出力せよ。
$i$ 行目には、 $i$ 番目までのクエリに対して操作を行った数列 $A$ の、転倒数を出力せよ。