int ops[1000005], prev[1000005], size[1000005], sz; void Init(){ } void TypeLetter(char L){ ops[sz] = L; size[sz] = size[prev[sz]]+1; sz++; prev[sz] = sz-1; } void UndoCommands(int U){ prev[sz] = sz-U-1; size[sz] = size[prev[sz]]; sz++; prev[sz] = sz-1; } char str[1000005]; char GetLetter(int P){ int i = prev[sz]; int piv = size[i] - P - 1; while (piv) { if(!ops[i]) piv++; i = prev[i]; } while(!ops[i]) i = prev[i]; return ops[i]; }