You are responsible for auditing all customer orders. Each order has a price, , and a timestamp, , denoting the minute when it was received.

At any given time, your manager can ask you for the maximum price of any order placed within the last minutes. For example, if your manager stops in at minute , you must know the maximum price of any order received between minutes and . Observe that you must also account for orders received in the same minute as your manager arrived.

You are given a list of events, where each event represents either a received order or an inquiry. For each inquiry from your manager, print the maximum price for any order placed within the last minutes on a new line.

**Input Format**

The first line contains a single integer, , denoting the number of events. Each of the subsequent lines describes either of the following types of events:

`1 P T`

– An order with price `P`

was placed at time `T`

.

`2 T`

– Your manager stopped in at time `T`

to inquire about the maximum order price for the last minutes.

All the events are given in non-decreasing order with respect to , so for , we have .

If there are multiple events of different types occurring at the same time, the received orders will be listed before manager inquiries.

**Constraints**

**Output Format**

For each event of type , print a number denoting the maximum price for any order placed within the previous minutes on a new line. If no orders were placed during that interval, print .

Assume there will be at least one event of type .

**Sample Input**

1 2 3 4 5 6 7 8 9 10 11 12 |
11 1 150 0 1 3 10 2 40 1 143 59 2 59 1 100 60 2 60 1 159 61 2 61 2 120 2 121 |

**Sample Output**

1 2 3 4 5 6 |
150 150 143 159 159 -1 |

**Explanation**

The largest order price in time range is .

The largest order price in time range is still .

The largest order price in time range is .

The largest order price in time range is .

The largest order price in time range is still .

There were no orders placed in time range , so we print for this inquiry.

**Solution**

We will solve this using a Map `time2price`

, with `time2price[t]`

holding the maximum price at exactly time `t`

. While we read our input we check if it is an *order* or *inquiry*. If we have an order we check if we already have a price for the current time (as multiple orders can be made at the same time). If we already have a price we choose the maximum between the existing and the new price. If we do not have a price for , we insert it into our map.

Since we don’t want our map to grow unnecessarily, we remove entries that we don’t consider relevant anymore every time we read a new price. Those entries are prices with a timestamp . That way our map will hold a maximum of entries at any given time.

Now, if we get an inquiry, we just need to search our map for the maximum price and print it.

**Full code**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
public class TheInquiringManager { private static final int ORDER = 1; public static void main(String[] args) throws FileNotFoundException { System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt")); Scanner in = new Scanner(System.in); // Read input int n = in.nextInt(); Map<Long, Long> time2price = new HashMap<Long, Long>(); for (int i = 0; i < n; i++) { int type = in.nextInt(); if (type == ORDER) { Long price = in.nextLong(); Long time = in.nextLong(); if (time2price.containsKey(time)) { time2price.put(time, time2price.get(time) < price ? price : time2price.get(time)); } else { time2price.put(time, price); } Iterator<Map.Entry<Long, Long>> iter = time2price.entrySet().iterator(); while (iter.hasNext()) { Map.Entry<Long, Long> entry = iter.next(); if (entry.getKey() < time - 60) { iter.remove(); } } } else { Long time = in.nextLong(); Long max = -1l; for (Long t : time2price.keySet()) { if (t > time - 60) { max = Math.max(time2price.get(t), max); } } System.out.println(max); } } } } |