Maximum score after the i-th game using prefix maximum

Far away in Lonely lands of Punjab’s village there lived mathematically advanced guy. Let’s call him the lost guy because he remains lost in his Mathematical courses.One of the games he is playing is “Laura the Lasan”.

This game is so addictive that he isn’t doing anything else and played this game N times in a single day, getting a score of Ai in the i-th game. After every game, the Maximum Score among all games played till now, is displayed.Next day, he was bored at work, and was thinking about the gaming session the previous day.

In particular, he had Q thoughts, where each thought involves wondering what Maximum Score was displayed after the i-th game. He wants you to help him resolve these thoughts. That is, he has Q questions, where each question consists of a single integer qi. For this, you should tell him what the Maximum Score was, after the qi game.

Examples :

Input : N=5, q=3
A = {5, 4, 8, 6, 9}
qi = { 2, 3, 5}
Output : 5
8
9
Explanation :
For first thought, maximum score is max(5,4) = 5
For second thought, maximum score is max(5,4,8) = 8
For third thought, maximum score is max(5,4,8,6,9) = 9

// In the approach below we are using a hash map to store the max element
// encountered till now so that we can output the queries directly in O(1) time.
#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(0);  // fast I/O
  long long N = 5, q = 3;

  vector<long long> A = {5, 4, 8, 6, 9};
  vector<long long> qi = {2, 3, 5};

  unordered_map<long long, long long> M;
  M[0] = 0;

  for (long long i = 0; i < N; i++) {
    M[i + 1] = max(A[i], M[i]);
  }

  for (long long i = 0; i < q; i++) {
    cout << M[qi[i]] << endl;
  }

  return 0;
}