dequeのランダムアクセスがO(1)とは知らなかった 

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll Q;cin>>Q;
    deque<ll> q;
    while(Q--){
      ll t,x;cin>>t>>x;
      if(t==1){
        q.push_front(x);
      }
      else if(t==2){
        q.push_back(x);
      }
      else{
        ll v = q[x-1]; // O(1) !!
        p(v);
      }
    }
    
    return 0;
}