{"raw_statement":[{"iden":"statement","content":"One-dimensional country has n cities, the i-th of which is located at the point xi and has population pi, and all xi, as well as all pi, are distinct. When one-dimensional country got the Internet, it was decided to place the main server in the largest city, and to connect any other city j to the city k that has bigger population than j and is the closest to it (if there are many such cities, the largest one should be chosen). City k is called a parent of city j in this case.\n\nUnfortunately, the Ministry of Communications got stuck in determining from where and to where the Internet cables should be laid, and the population of the country is suffering. So you should solve the problem. For every city, find its parent city.\n\nThe first line contains a single integer n (1 ≤ n ≤ 200000) — the number of cities.\n\nEach of the next n lines contains two space-separated integers xi and pi (1 ≤ xi,  pi ≤ 109) — the coordinate and the population of the i-th city.\n\nOutput n space-separated integers. The i-th number should be the parent of the i-th city, or  - 1, if the i-th city doesn't have a parent. The cities are numbered from 1 by their order in the input.\n\n"},{"iden":"input","content":"The first line contains a single integer n (1 ≤ n ≤ 200000) — the number of cities.Each of the next n lines contains two space-separated integers xi and pi (1 ≤ xi,  pi ≤ 109) — the coordinate and the population of the i-th city."},{"iden":"output","content":"Output n space-separated integers. The i-th number should be the parent of the i-th city, or  - 1, if the i-th city doesn't have a parent. The cities are numbered from 1 by their order in the input."},{"iden":"examples","content":"Input41 10007 109 112 100Output-1 4 2 1Input31 1002 13 10Output-1 1 1Input31 103 1002 1Output2 -1 2"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of cities.  \nFor each city $ i \\in \\{1, \\dots, n\\} $, let $ (x_i, p_i) \\in \\mathbb{R} \\times \\mathbb{R}^+ $ denote its coordinate and population, with all $ x_i $ distinct and all $ p_i $ distinct.  \n\nLet $ C = \\{(i, x_i, p_i) \\mid i = 1, \\dots, n\\} $ be the set of cities indexed by input order.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 200000 $  \n2. $ 1 \\leq x_i, p_i \\leq 10^9 $ for all $ i $  \n3. All $ x_i $ are pairwise distinct.  \n4. All $ p_i $ are pairwise distinct.  \n\n**Objective**  \nFor each city $ i $, define its *parent* $ \\text{parent}(i) $ as follows:  \n\n- If $ p_i $ is the maximum population among all cities, then $ \\text{parent}(i) = -1 $.  \n- Otherwise, let $ P_i = \\{ j \\mid p_j > p_i \\} $ be the set of cities with strictly greater population.  \n  Among all $ j \\in P_i $, select the one minimizing $ |x_j - x_i| $.  \n  If there are multiple such $ j $ with the same minimal distance, choose the one with the *largest* $ p_j $.  \n  Then $ \\text{parent}(i) = j $ (the input index of the chosen city).  \n\nOutput an array $ [\\text{parent}(1), \\text{parent}(2), \\dots, \\text{parent}(n)] $.","simple_statement":"You are given n cities on a line, each with a unique position and unique population. The city with the largest population is the server and has no parent. For every other city, find its parent: the closest city with a larger population. If there are multiple such cities, choose the one with the largest population. Output the parent of each city in input order, or -1 if it has no parent.","has_page_source":false}