class RLE{

public:

vector<vector<int>> encode(vector<int>& input){
int sizeInput = input.size();
int prev = -1;
int count = 0;
vector<vector<int>> ans(3);
for(int index = 0;index<sizeInput;index++){
  if(input[index]==prev){
    count++;
  }
  else{
    if(prev!=-1){
      ans[0].push_back(prev);
      ans[1].push_back(count);
      ans[2].push_back(index);
     }
     prev = input[index];
     count = 1;
    }
  }
}
ans[2].push_back(sizeInput);
ans.push_back({prev,count});
return ans;
}

int getValueAt(vector<vector<int>>& encodedInput, int index){
// binary search on encodedInput[2]
index += 1;
int indexInEncoded = lower_bound(encodedInput[2].begin(),encodedInput[2].end(),index) - encodedInput[2].begin();
return encodedInput[0][indexInEncoded];

}

};