↵
Since `std::map` is sorted by keys, not values, you can use `std::max_element` to find the pair with the largest value:↵
↵
```cpp↵
auto it = max_element(↵
m.begin(), m.end(),↵
[](const auto &a, const auto &b) {↵
return a.second < b.second;↵
}↵
);↵
↵
cout << "Max value: " << it->second << " (Key: " << it->first << ")" << endl;↵
```↵
↵
**Explanation:**↵
↵
* `std::max_element` iterates through all pairs.↵
* The lambda compares elements based on their `second` value.↵
* The iterator `it` points to the pair with the maximum value.↵
↵
---↵
↵
### Bonus↵
↵
If you want the maximum key instead, you can write:↵
↵
```cpp↵
auto last = m.rbegin();↵
cout << last->first << " " << last->second;↵
```↵
↵
---↵
↵
Tip: Counting Distinct Elements in All Prefixes↵
↵
When a problem asks you to count distinct numbers before (or up to) each index, think in terms of prefix processing + frequency tracking.↵
↵
Idea:↵
Stand at each index i and maintain a frequency array (or map).↵
↵
If the current element appears for the first time, then the number of distinct elements increases by one.↵
↵
Store this count as the number of distinct elements in the prefix ending at i.↵
↵
Implementation Sketch:↵
↵
map<int, int> freq;↵
vector<int> distinct(n);↵
int cnt = 0;↵
↵
for (int i = 0; i < n; i++) {↵
freq[x[i]]++;↵
if (freq[x[i]] == 1) {↵
cnt++; // new distinct element↵
}↵
distinct[i] = cnt; // distinct elements up to index i↵
}↵
↵
↵
If the problem later asks for the sum of distinct counts over all prefixes, simply accumulate:↵
↵
long long ans = 0;↵
for (int i = 0; i < n; i++) {↵
ans += distinct[i];↵
}↵
↵
↵
Why this works:↵
Each element contributes to the distinct count only once, exactly at its first occurrence.↵
↵
↵
↵
