Ad Service That Serves the Top-Scoring Ad Without Back-to-Back Repeats

Design an ad service that supports two operations: - `InsertAd(content, score)` adds an ad whose text is `content` (a string) and whose score is the integer `score`. - `GetAd()` returns one ad: it must return the ad whose current score is highest, no ad may be returned by two consecutive `GetAd` calls, and the returned ad's score then decreases by 1. The service is driven by a list of operations. Implement `run_ad_service(operations)`: start with an empty service, apply the operations in order, and return the results of the `GetAd` operations. **Rules** - `["InsertAd", content, score]` adds a new ad and produces no output. - `["GetAd"]` considers every stored ad except the one returned by the immediately preceding `GetAd` operation. If there was no preceding `GetAd`, or it returned `None`, no ad is excluded. `InsertAd` operations between two `GetAd` operations do not change this. - Among the ads it considers, `GetAd` returns the `content` of the one with the highest current score; if several share that score, the one inserted earliest wins. That ad's score then decreases by 1. - If there is no ad to consider (the service is empty, or its only ad was returned by the preceding `GetAd`), `GetAd` returns `None` and no score changes. - Ads are never removed. A score may fall to zero or below, and the ad stays eligible. - Return a list with one entry per `GetAd` operation, in order. If there is no `GetAd` operation, return an empty list. `None` is `null` in JavaScript and Java and `std::nullopt` (an empty `std::optional<std::string>`) in C++. In Java each operation is a `java.util.List<Object>` (read the score through `java.lang.Number`); in C++ each operation is a `std::vector<std::string>` and the score is given as its decimal text (for example `"-5"`). **Example 1** ```text Input: operations = [["InsertAd", "shoes", 3], ["InsertAd", "games", 3], ["InsertAd", "books", 2], ["GetAd"], ["GetAd"], ["GetAd"], ["GetAd"], ["GetAd"], ["GetAd"]] Output: ["shoes", "games", "shoes", "games", "books", "shoes"] ``` | GetAd call | Scores before the call (shoes, games, books) | Excluded | Returned | | --- | --- | --- | --- | | 1 | 3, 3, 2 | none | shoes (ties with games, inserted earlier) | | 2 | 2, 3, 2 | shoes | games | | 3 | 2, 2, 2 | games | shoes (ties with books, inserted earlier) | | 4 | 1, 2, 2 | shoes | games (ties with books, inserted earlier) | | 5 | 1, 1, 2 | games | books | | 6 | 1, 1, 1 | books | shoes (ties with games, inserted earlier) | **Example 2** ```text Input: operations = [["GetAd"], ["InsertAd", "solo", 1], ["GetAd"], ["GetAd"], ["GetAd"], ["InsertAd", "late", 0], ["GetAd"], ["GetAd"]] Output: [None, "solo", None, "solo", "late", "solo"] ``` The first call finds no ads. The second returns "solo" (score 1 to 0). The third must exclude "solo", has nothing else to consider and returns `None`. Because that call returned `None`, the fourth may return "solo" again (score 0 to -1). After "late" is inserted with score 0, the fifth call excludes "solo" and returns "late" (score 0 to -1); the sixth excludes "late" and returns "solo" even though its score is -1. **Constraints** - `1 <= len(operations) <= 10^5` - Each operation is either `["InsertAd", content, score]` or `["GetAd"]`. - `-10^9 <= score <= 10^9` when an ad is inserted. Each `GetAd` lowers one score by 1, so every score stays within `[-10^9 - 10^5, 10^9]`. No score ever exceeds 2^31 - 1 in absolute value, so every score fits in a signed 32-bit integer. - `content` is 1 to 20 lowercase English letters, and every `InsertAd` uses a different `content`.