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