stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#define LL long long

#define db double

using namespace std;



const int MAXN = 200200;

const int INF = 0x3f3f3f3f;



template <typename T> inline void read(T &x) {

	char c = getchar();

	bool f = false;

	for (x = 0; !isdigit(c); c = getchar()) {

		if (c == '-') {

			f = true;

		}

	}

	for (; isdigit(c); c = getchar()) {

		x = x * 10 + c - '0';

	}

	if (f) {

		x = -x;

	}

}



template <typename T> inline bool CheckMax(T &a, const T &b) {

	return a < b ? a = b, true : false;

}



template <typename T> inline bool CheckMin(T &a, const T &b) {

	return a > b ? a = b, true : false;

}



int n, a[MAXN];

int cnt;

#define ls lower_bound

#define us upper_bound



signed main() {

	read(n);

	for(int i = 1, x; i <= n; i++) read(x), a[x] = i;

	int ans = 0;

	for(int i = 1, len = 0; i <= n; i++) {

		if(a[i] > a[i - 1]) {

			CheckMax(ans, ++len);

		}

		else len = 1;

	}

	printf("%d\n", n - ans);

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

using namespace std;



const int MAXN = 200005;

int p[MAXN], ord[MAXN];



int main()

{

	int n;

	scanf("%d", &n);

	for (register int i = 1; i <= n; i++)

	{

		scanf("%d", &p[i]);

		ord[p[i]] = i;

	}

	int ans = 0, len = 1;

	for (register int i = 2; i <= n; i++)

		if (ord[i] >= ord[i-1]) len++;

		else ans = max(ans, len), len = 1;

	ans = max(ans, len);

	printf("%d", n - ans);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
//#include<bits/stdc++.h> 

#include<iostream> 

#include<cstdio>

#include<cstring>

#include<queue>

#include<vector>  

#define Max int(2e5+10) 

using namespace std;  

int n,p[Max],a[Max],dp[Max];

vector<int> g[Max];

int dfs(int x)

{

	if(dp[x]>0)

	   return dp[x];

	dp[x]=1;

	for(int i=0;i<g[x].size();i++)

	    dp[x]=dfs(g[x][i])+1;

	 return dp[x];	  

}

int  main()  

{   

    while(~scanf("%d",&n))

    {

    	for(int i=1;i<=n;i++)

    	    g[i].clear();

    	for(int i=1;i<=n;i++)

    	   {

    	   	scanf("%d",&p[i]);

    	   	a[p[i]]=i;

		   }

    	for(int i=1;i<n;i++)

		    if(a[i]<a[i+1])

		       g[a[i]].push_back(a[i+1]);

	//	for(int i=1;i<=n;i++)

	//	   cout<<g[i][0]<<endl; 	       

		memset(dp,0,sizeof dp);   

		int ma=-1;      

    	for(int i=1;i<=n;i++)

		   ma=max(ma,dfs(i));

		//cout<<ma<<endl;   

		printf("%d\n",n-ma);   

	}

      

       

     return 0;     

} 

// Optimized solution to the same problem (faster):
#include <cstdio>

#include<cstring>

#include <algorithm>

using  namespace std;

#define mem(v,x) memset(v,x,sizeof(v))

#define low(x) (x & (-x))

int pos[500010],n,m;



int main() {

    scanf("%d",&n);

    for (int i = 1; i <= n; i++){

       scanf("%d",&m);

       pos[m] = i;

    }

    int len = 1,ans = 5000000;

    for (int i = 1; i < n; i++){

        if (pos[i+1] > pos[i]) len++; else{

            ans = min(ans,n-len);

            len = 1;

        }

    }

    ans = min(ans,n-len);

    printf("%d\n",ans);



    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

using namespace std;

int n;

int a[210000],f[210000],ans;

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

	  scanf("%d",&a[i]);

	ans=n;

	for(int i=1;i<=n;i++)

	{

	  f[a[i]]=max(1,f[a[i]-1]+1);

	  ans=min(ans,n-a[i]+a[i]-f[a[i]]);

	}

	printf("%d\n",ans);

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include<cstring>

#include <algorithm>

using  namespace std;

#define mem(v,x) memset(v,x,sizeof(v))

#define low(x) (x & (-x))

int pos[500010],n,m;



int main() {

    scanf("%d",&n);

    for (int i = 1; i <= n; i++){

       scanf("%d",&m);

       pos[m] = i;

    }

    int len = 1,ans = 5000000;

    for (int i = 1; i < n; i++){

        if (pos[i+1] > pos[i]) len++; else{

            ans = min(ans,n-len);

            len = 1;

        }

    }

    ans = min(ans,n-len);

    printf("%d\n",ans);



    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):


#include<iostream>

#include<vector>

#include<map>

#include<algorithm>

using namespace std;

int a[200005];

map<int, int>m;// [200005];//就相当于是int m[200005];

vector<int> g[200005];

int vis[200005]={0};

int maxn = 0;

int dfs(int i, int ans) {

	if(vis[i]!=0)return ans;

	for (int j = 0; j<g[i].size(); j++)

	{

		//if(!vis[i])

		ans = max(dfs(g[i][j], ans) + 1, ans);

	}

	vis[i]=ans;

	return ans;

}

int main() {

	int n; cin >> n;

	int x;

	for (int i = 1; i <= n; i++) {

		cin >> x;

		m[x] = i;

	}

	for (int i = 1; i <= n; i++) {

		if (m[i]<m[i + 1])

			//如果 i+1的下标比i要大, 就是在他后面

			g[i].push_back(i + 1);

	}

	//建图完毕

	int ans = 0;

	for (int i = 1; i <= n; i++) {

		ans = max(ans, dfs(i, 1));

	}

	cout << (n-ans)<<endl;//(最长的)

	return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

#define mp make_pair

#define pb push_back

typedef pair<int,int> ii;

typedef long long ll;

typedef pair<ll,ll>l4 ;

const int maxn=2e5+5;

int n,a[maxn];

int main(){

	scanf("%d",&n);

	for(int i=1;i<=n;++i)

	{

	    int x;

		scanf("%d",&x);

		a[x]=a[x-1]+1; 		

	}

	printf("%d\n",n-*max_element(a+1,a+1+n));

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <vector>

#include <queue>

#include <stack>

using namespace std;

 

//思路：并?集 + ? + ?列 （??取出方式） 



int parent[100016];

int height[100016];



//并?集 

void init(int n)

{

	for(int i = 1; i <= n; i++){

		parent[i] = i;

		height[i] = 0;

	}

}

 

int find(int x)

{

	if(parent[x] == x)  return x;

	else  return parent[x] = find(parent[x]);

}

 

//用来描述原始? 

vector<int> children[100016];

int parent_tree[100016];

bool marked[100016];

int ancestor[100016];

// ?条指令被拆分? 操作 + 目?

stack<char> operation;

stack<int>  target;

 

void bfs(int index, int the_ancestor)

{

	queue<int> q_index;

	queue<int> q_ancestor;

	q_index.push(index);

	q_ancestor.push(the_ancestor);

	while (!q_index.empty())

	{

		the_ancestor = q_ancestor.front(); 

		q_ancestor.pop();

		index = q_index.front(); 

		q_index.pop();

		if(marked[index] == true)  the_ancestor = index;  //如果?点自身被??，?它的染色祖先是自己，它的自己不??的儿子的最近染色祖先是它

		ancestor[index] = the_ancestor;  //??index的最近染色祖先 

		for(vector<int>::iterator it = children[index].begin(); it != children[index].end(); it++){  //将index的儿子加入?列 

			q_index.push(*it);

			q_ancestor.push(the_ancestor);

		}

	}

}

 

int main()

{

 

	int N, Q;

	while(scanf("%d %d", &N, &Q) && (N || Q)){

		for(int i = 1; i <= N; i++){

			children[i].clear();

			marked[i] = false;

		}

		marked[1] = true;

		parent_tree[1] = 1;

		int p;

		for(int i = 2; i <= N; i++){

			scanf("%d", &p);

			parent_tree[i] = p;

			children[p].push_back(i);

		}

		getchar(); 

		for(int i = 0; i < Q; i++){

			char ch;

			int t;

			scanf("%c %d", &ch, &t);

			getchar();

			if(ch == 'M'){

				if(marked[t])  continue;  //不?存重?的 "M v"，防止之后重?反染色 

				else  marked[t] = true;

			}

			operation.push(ch);

			target.push(t);

		}

		bfs(1, 1);

		init(N);

		for(int i = 1; i <= N; i++){

			parent[i] = ancestor[i];

		}

		unsigned long long result = 0;

		while(!operation.empty()){  //从后往前取出操作

			char ch = operation.top(); 

			operation.pop();

			int t = target.top(); 

			target.pop();

			if(ch == 'Q')  result += find(t);  //?目index从1?始

			else{  //??点t反染色（取消染色），t的祖先??其父?点的祖先

				parent[t] = find(parent_tree[t]);

			}

		}

		printf("%lld\n", result);

	}

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>



#define N 100010



int a[N];



long long Find(int x){

	return a[x]==x? a[x]:Find(a[x]);

}



int main(){

	while(true){

		int n,q;

		scanf("%d%d",&n,&q);

		if(!(n||q))

			break;

		a[1]=1;

		for(int i=2;i<=n;i++)

			scanf("%d",a+i);

		long long ans=0ll;

		while(q--){

			char tmp[10]={};

			int x;

			scanf("%s%d",tmp,&x);

			if(*tmp=='Q')

				ans+=Find(x);

			else

				a[x]=x;

		}

		printf("%lld\n",ans);

	}

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstdio>

#include<cstring>

#include<vector>

using namespace std;

#define MAXN 100005

int Set[MAXN];

int Root(int x)

{return Set[x]==x?x:Set[x]=Root(Set[x]);}

int N,Q;

int fa[MAXN];

int Que[MAXN][2];

int marked[MAXN];

int main()

{

	char op[3];

	int id;

	long long ans;

	while(~scanf("%d%d",&N,&Q)&&N&&Q)

	{

		memset(Que,0,sizeof Que);

		memset(fa,0,sizeof fa);

		memset(Set,0,sizeof Set);

		memset(marked,0,sizeof marked);

		ans=0;

		Set[1]=1;fa[1]=1;

		for(int i=2;i<=N;i++)

		{

			scanf("%d",fa+i);

			Set[i]=fa[i];

		}

		for(int i=1;i<=Q;i++)

		{

			scanf("%s%d",op,&id);

			if(op[0]=='Q')Que[i][0]=1;

			else {Que[i][0]=2;Set[id]=id;marked[id]++;}

			Que[i][1]=id;

		}

		for(int i=Q;i>=1;i--)

		{

			if(Que[i][0]==1)

				ans+=1LL*Root(Que[i][1]);

			else

			{

				marked[Que[i][1]]--;

				if(!marked[Que[i][1]])

					Set[Que[i][1]]=fa[Que[i][1]];

			}

		}

		printf("%lld\n",ans);

	}

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>



#define N 100010



int a[N];



long long Find(int x){

	return a[x]==x? a[x]:Find(a[x]);

}



int main(){

	while(true){

		int n,q;

		scanf("%d%d",&n,&q);

		if(!(n||q))

			break;

		a[1]=1;

		for(int i=2;i<=n;i++)

			scanf("%d",a+i);

		long long ans=0ll;

		while(q--){

			char tmp[10]={};

			int x;

			scanf("%s%d",tmp,&x);

			if(*tmp=='Q')

				ans+=Find(x);

			else

				a[x]=x;

		}

		printf("%lld\n",ans);

	}

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<algorithm>

#include<iostream>

#include<string.h>

#include<sstream>

#include<stdio.h>

#include<math.h>

#include<vector>

#include<string>

#include<queue>

#include<set>

#include<map>

//#pragma comment(linker,"/STACK:1024000000,1024000000")

using namespace std;

const int INF=0x3f3f3f3f;

const double eps=1e-8;

const double PI=acos(-1.0);

typedef long long ll;

const int maxn=100010;

int tree[maxn];

int Find(int x)

{

    if(tree[x]==x)

        return x;

    return Find(tree[x]);

}

int main()

{

    int n,m,id,i;

    char com[10];

    ll ans;



    while(scanf("%d%d",&n,&m),n||m)

    {

        tree[1]=1;

        ans=0;

        for(i=2;i<=n;i++)

            scanf("%d",&tree[i]);

        for(i=0;i<m;i++)

        {

            scanf("%s%d",com,&id);

            if(com[0]=='M')

                tree[id]=id;

            else

                ans+=Find(id);

        }

        printf("%lld\n",ans);

    }

    return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>



#define N 100010



int a[N];



long long Find(int x){

	return a[x]==x? a[x]:Find(a[x]);

}



int main(){

	while(true){

		int n,q;

		scanf("%d%d",&n,&q);

		if(!(n||q))

			break;

		a[1]=1;

		for(int i=2;i<=n;i++)

			scanf("%d",a+i);

		long long ans=0ll;

		while(q--){

			char tmp[10]={};

			int x;

			scanf("%s%d",tmp,&x);

			if(*tmp=='Q')

				ans+=Find(x);

			else

				a[x]=x;

		}

		printf("%lld\n",ans);

	}

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
//

//  AOJ 2170 Marked Ancestor

//

//  Created by TaoSama on 2015-03-16

//  Copyright (c) 2015 TaoSama. All rights reserved.

//

#include <algorithm>

#include <cctype>

#include <cmath>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iomanip>

#include <iostream>

#include <map>

#include <queue>

#include <string>

#include <set>

#include <vector>

#define CLR(x,y) memset(x, y, sizeof(x))



using namespace std;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

const int N = 1e5 + 10;



int n, q, par[N];



int find(int x) {

	if(par[x] == x) return x;

	return find(par[x]);

}



int main() {

#ifdef LOCAL

	freopen("in.txt", "r", stdin);

//	freopen("out.txt","w",stdout);

#endif

	ios_base::sync_with_stdio(0);



	while(~scanf("%d%d", &n, &q) && n && q) {

		par[1] = 1;

		for(int i = 2; i <= n; ++i) scanf("%d", &par[i]);



		long long ans = 0;

		for(int i = 1; i <= q; ++i) {

			char op[2]; int x;

			scanf("%s%d", op, &x);

			if(op[0] == 'Q') ans += find(x);

			else par[x] = x;

		}

		printf("%lld\n", ans);

	}

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>



#define N 100010



int a[N];



long long Find(int x){

	return a[x]==x? a[x]:Find(a[x]);

}



int main(){

	while(true){

		int n,q;

		scanf("%d%d",&n,&q);

		if(!(n||q))

			break;

		a[1]=1;

		for(int i=2;i<=n;i++)

			scanf("%d",a+i);

		long long ans=0ll;

		while(q--){

			char tmp[10]={};

			int x;

			scanf("%s%d",tmp,&x);

			if(*tmp=='Q')

				ans+=Find(x);

			else

				a[x]=x;

		}

		printf("%lld\n",ans);

	}

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
//支持分?操作的并?集

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAX_N=1e5+10;

int par[MAX_N];

int find(int x){

  int tmp=x;

  while(par[tmp]!=tmp){

    tmp=par[tmp];

  }

  return tmp;

}

int main(){

  //freopen("in", "r", stdin);

  char op[2];

  int N, Q, x;

  ll ans;

  par[1]=1;

  while(scanf("%d%d", &N, &Q), N){

    ans=0;

    for(int i=2; i<=N; i++){

      scanf("%d", par+i);

    }

    while(Q--){

      scanf("%s%d", op, &x);

      if(*op=='M'){

        par[x]=x;

      }

      else ans+=(ll)find(x);

    }

    printf("%lld\n", ans);

  }

  return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>



#define N 100010



int a[N];



long long Find(int x){

	return a[x]==x? a[x]:Find(a[x]);

}



int main(){

	while(true){

		int n,q;

		scanf("%d%d",&n,&q);

		if(!(n||q))

			break;

		a[1]=1;

		for(int i=2;i<=n;i++)

			scanf("%d",a+i);

		long long ans=0ll;

		while(q--){

			char tmp[10]={};

			int x;

			scanf("%s%d",tmp,&x);

			if(*tmp=='Q')

				ans+=Find(x);

			else

				a[x]=x;

		}

		printf("%lld\n",ans);

	}

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstdio>

#include<iostream>

#include<string>

#include<cstring>

#include<queue>

#include<vector>

#include<stack>

#include<vector>

#include<map>

#include<set>

#include<algorithm>

//#include<bits/stdc++.h>

using namespace std;



const int maxn = 1e5+5;

int pa[maxn];

int Mrk[maxn];



int qt[maxn],qv[maxn];

int Qt;

int fdst(int x)

{

    return Mrk[x] < Qt ? x :pa[x] = fdst(pa[x]);

}



//#define LOCAL

int main()

{

#ifdef LOCAL

    freopen("in.txt","r",stdin);

#endif

    int N, Q;

    while(scanf("%d%d",&N,&Q),N){

        for(int i = 2; i <= N; i++){

            scanf("%d",pa+i);

            Mrk[i] = Q+1;

        }

        int c = 0;

        for(int i = 1; i <= Q; i++){

            char op[2];

            int v;

            scanf("%s%d",op,&v);

            if(*op == 'Q'){

                qt[c] = i;

                qv[c++] = v;

            }else {

                Mrk[v] = min(Mrk[v],i);//取最早生效的??

            }

        }

        long long ans = 0;

        while(c--){

            Qt = qt[c];

            ans += fdst(qv[c]);

        }

        printf("%lld\n",ans);

    }

    return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>



#define N 100010



int a[N];



long long Find(int x){

	return a[x]==x? a[x]:Find(a[x]);

}



int main(){

	while(true){

		int n,q;

		scanf("%d%d",&n,&q);

		if(!(n||q))

			break;

		a[1]=1;

		for(int i=2;i<=n;i++)

			scanf("%d",a+i);

		long long ans=0ll;

		while(q--){

			char tmp[10]={};

			int x;

			scanf("%s%d",tmp,&x);

			if(*tmp=='Q')

				ans+=Find(x);

			else

				a[x]=x;

		}

		printf("%lld\n",ans);

	}

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

using namespace std;

const int MAXN = 100000 + 10;

int par[MAXN];

int Find(int x){

	if (x == par[x])

		return par[x];

	return Find(par[x]);

}

int main(){

	int n, q;

	char ins[10];

	int v;



	while (~scanf("%d%d", &n, &q) && n && q){

		long long sum = 0;

		par[1] = 1;

		for (int i = 2; i <= n; i++){

			scanf("%d", &par[i]);

		}

		for (int i = 0; i < q; i++){

			scanf("%s%d", ins, &v);

			if (strcmp(ins, "M") == 0){

				par[v] = v;

			}

			else{

				sum += Find(v);

			}

		}

		printf("%lld\n", sum);

	}

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>



#define N 100010



int a[N];



long long Find(int x){

	return a[x]==x? a[x]:Find(a[x]);

}



int main(){

	while(true){

		int n,q;

		scanf("%d%d",&n,&q);

		if(!(n||q))

			break;

		a[1]=1;

		for(int i=2;i<=n;i++)

			scanf("%d",a+i);

		long long ans=0ll;

		while(q--){

			char tmp[10]={};

			int x;

			scanf("%s%d",tmp,&x);

			if(*tmp=='Q')

				ans+=Find(x);

			else

				a[x]=x;

		}

		printf("%lld\n",ans);

	}

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cmath>

#include <cstdio>

#include <string>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <set>

#include <map>

#include <queue>

#include <vector>

#define rep(i, a, b) for (int i = a; i < b; ++i)

#define repr(i, a, b) for (int i = a; i <= b; ++i)

#define dep(i, a, b) for (int i = a; i > b; --i)

#define depr(i, a, b) for (int i = a; i >= b; --i)

#define getnum(n) scanf("%d", &n)

#define LL long long

#define INF 0x7f7f7f7f

#define PI acos(-1.0)

using namespace std;



const int MAXN = 1e5 + 5;

int f[MAXN], mark[MAXN], n, q, x, qt[MAXN], qv[MAXN], cnt, t;

LL ans;



inline int Find(int x) {

	return mark[x] < t ? x : f[x] = Find(f[x]);

}



inline void Init() {

	mark[1] = cnt = ans = 0;

	f[1] = 1;

	repr(i, 2, n) {

		getnum(f[i]);

		mark[i] = INF;

	}

}



inline void Solve() {

	char op[2];

	repr(i, 1, q) {

		scanf("%s%d", op, &x);

		if (op[0] == 'Q') {

			qt[cnt] = i;

			qv[cnt++] = x;

		}

		else mark[x] = min(mark[x], i);

	}

	while (cnt) {

		t = qt[--cnt];

		ans += Find(qv[cnt]);

	}

	

	printf("%lld\n", ans);

}



int main()

{

	while (~scanf("%d%d", &n, &q) && (n || q)) {

		Init();

		Solve();

	}

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>



#define N 100010



int a[N];



long long Find(int x){

	return a[x]==x? a[x]:Find(a[x]);

}



int main(){

	while(true){

		int n,q;

		scanf("%d%d",&n,&q);

		if(!(n||q))

			break;

		a[1]=1;

		for(int i=2;i<=n;i++)

			scanf("%d",a+i);

		long long ans=0ll;

		while(q--){

			char tmp[10]={};

			int x;

			scanf("%s%d",tmp,&x);

			if(*tmp=='Q')

				ans+=Find(x);

			else

				a[x]=x;

		}

		printf("%lld\n",ans);

	}

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
/*

 ━━━━━?

 ┓┏┓┏┓┃μ'sic foever!!

 ┛┗┛┗┛┃＼○／

 ┓┏┓┏┓┃ /

 ┛┗┛┗┛┃ノ)

 ┓┏┓┏┓┃

 ┛┗┛┗┛┃

 ┓┏┓┏┓┃

 ┛┗┛┗┛┃

 ┓┏┓┏┓┃

 ┛┗┛┗┛┃

 ┓┏┓┏┓┃

 ┃┃┃┃┃┃

 ┻┻┻┻┻┻

 */

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <map>

#include <stack>

#include <vector>

using namespace std;

const int maxn=1e5+10;

bool vis[maxn];

int pre[maxn];

long long res;

bool flag;

int find(int x){

    int r = x;

    while(pre[r]!=r){

        if(!flag&&vis[pre[r]]){

            res += pre[r];

            flag = true;

            return -1;

        }

        r = pre[r];

    }

    return r;

}

void join(int a,int b){

    pre[b]=a;

}

int main(){

    int n,q,i,j,a,b;

    char op;

    while(~scanf("%d%d",&n,&q)&&n&&q){

        res = 0;

        memset(vis, false, sizeof(vis));

        for(i=1;i<=n;i++){

            pre[i] = i;

        }

        for(i=2;i<=n;i++){

            scanf("%d",&a);

            join(a,i);

        }

        getchar();

        for(i=1;i<=q;i++){

            scanf("%c %d",&op,&a);

            if(op=='Q'){

                if(!vis[a]){

                    flag = false;

                    if(find(a)==-1){

                        

                    }else{

                        res += 1;

                    }

                }else{

                    res += a;

                }

            }else{

                vis[a] = true;

            }

            getchar();

        }

        printf("%lld\n",res);

    }

    return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>



#define N 100010



int a[N];



long long Find(int x){

	return a[x]==x? a[x]:Find(a[x]);

}



int main(){

	while(true){

		int n,q;

		scanf("%d%d",&n,&q);

		if(!(n||q))

			break;

		a[1]=1;

		for(int i=2;i<=n;i++)

			scanf("%d",a+i);

		long long ans=0ll;

		while(q--){

			char tmp[10]={};

			int x;

			scanf("%s%d",tmp,&x);

			if(*tmp=='Q')

				ans+=Find(x);

			else

				a[x]=x;

		}

		printf("%lld\n",ans);

	}

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = 2e5 + 5;

#define bug(x) printf("  %s = %d \n",#x,x);

#define mem(arr,x) memset(arr,x,sizeof arr);

int par[maxn];



int dfs(int pos){

	if(par[pos] != pos)

		return dfs(par[pos]);

	else

	 	return pos;

}



int main() {

#ifdef LOCAL

	freopen("in.txt", "r", stdin);

#endif

	ios_base::sync_with_stdio(0);

	int N,Q;

	while(scanf("%d%d",&N,&Q) == 2){

		if(N == 0 && Q == 0) break;

		par[1] = 1;

		for(int i = 2; i <=  N; i++){

			scanf("%d",par + i);

		}

		char op;

		int  pos;

		long long  Sum = 0;

		getchar();

		for(int i = 1; i <= Q;i++){

			scanf("%c %d",&op,&pos);

//			bug(op);

			if(op == 'Q'){

				Sum += dfs(pos);

			}

			else{

				par[pos] = pos;

			}

			getchar();

		}

		printf("%lld\n",Sum);

	}

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>



#define N 100010



int a[N];



long long Find(int x){

	return a[x]==x? a[x]:Find(a[x]);

}



int main(){

	while(true){

		int n,q;

		scanf("%d%d",&n,&q);

		if(!(n||q))

			break;

		a[1]=1;

		for(int i=2;i<=n;i++)

			scanf("%d",a+i);

		long long ans=0ll;

		while(q--){

			char tmp[10]={};

			int x;

			scanf("%s%d",tmp,&x);

			if(*tmp=='Q')

				ans+=Find(x);

			else

				a[x]=x;

		}

		printf("%lld\n",ans);

	}

	return 0;

}


// Fastest known solution for this problem: