数列全体を愚直にノートから読み書きする方法では、かかる計算量が大きくなり実行制限時間やメモリ制限を満たすことは難しいでしょう。 その対策として、数列 \(A\) の現在および過去の状態を木として保持することで、各クエリを高速に処理する方法を述べます。

まず、\(-1\) と書かれた頂点 \(r\) のみからなる根付き木（唯一の頂点 \(r\) を根とする）を用意し、頂点 \(r\) にコマを置きます。 そして、以後、

• ADD \(x\) のクエリでは、現在コマがある頂点の子として新たな頂点 \(v\) を追加し、頂点 \(v\) に整数 \(x\) を書き込んで、コマを頂点 \(v\) に移動します。

• DELETE のクエリでは、コマを、コマが現在ある頂点の親頂点に移動します。ただし、コマが根 \(r\) にあるときは何もしません。

上記のように ADD 、 DELETE のクエリを処理することで、つねに、現在の数列 \(A\) は「根から現在コマがある頂点までの単純パス上の頂点に書かれた整数を順に並べ、先頭の \(-1\) を取り除いて得られる数列」になっていることに注意してください。 よって、現在の数列 \(A\) をノートに記録する際は、数列そのものではなく、現在コマがある頂点がどこかという情報だけを記録すれば十分です。 つまり、

• SAVE \(y\) のクエリでは、現在コマがある頂点（その ID やメモリ上のアドレスなど実装方法に応じたもの）をノートの \(y\) ページ目に記録します。ノートの各ページにどの頂点が書かれているかは連想配列で管理することができます。

そして、

• LOAD \(z\) のクエリでは、ノートの \(z\) ページ目を参照し、そこに書かれた頂点にコマを移動すれば良いです。

\(A\) の末尾要素は、つねに、コマがある頂点に書かれた整数と一致し、また、\(A\) が空の場合（つまりコマが根 \(r\) にある場合）についても、根には \(-1\) が書かれているので、 結局、本問題を解くには、各クエリを実行するたびにその直後にコマがある頂点に書かれた整数を出力すれば良いです。

以下に、C++ 言語による本問題の正解例を記載します。

#include <iostream>
#include <vector>
#include <map>
using namespace std;

struct Node{
  int val, par;
  vector<int> vec;
  Node(int v, int p){val = v, par = p;};
};

int Q;
map<int, int> mp;
vector<Node> vec;

int main(void)
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> Q;
  
  int v = 0;
  vec.push_back(Node(-1, 0));

  string s; int x;
  for(int i = 1; i <= Q; i++){
    cin >> s;
    if(s == "ADD"){
      cin >> x;
      vec.push_back(Node(x, v));
      vec[v].vec.push_back((int)vec.size()-1);
      v = (int)vec.size()-1;
    }
    if(s == "DELETE") v = vec[v].par;
    if(s == "SAVE"){
      cin >> x;
      mp[x] = v;
    }
    if(s == "LOAD"){
      cin >> x;
      v = mp[x];
    }
    cout << vec[v].val << " ";
  }
  cout << endl;
  
  return 0;
}