该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

JOI Railways is a company operating one railway. In the railway of JOI Railways, there are N stations on a straight line numbered from 1 to N. For each i (1≤i≤ N−1), the station i and the station i + 1 are connected by a railway track. JOI Railways has K types of trains running in both directions. The types of trains are expressed as integers between 1 and K inclusive. Each station has a level which is an integer between 1 and K inclusive. For each i (1≤i≤ N), the station i has level Li. The stations in both ends, namely the station 1 and the station N, have level K. Atrainoftype j(1≤ j≤ K)stopsateverystationwhoselevelisgreaterthanorequalto j,anditdoesnotstop at any other stations. Since the stations in both ends, namely the station 1 and the station N, have level K, every train stops at these stations. ManypassengersuseJOIRailwayseveryday. Duringtravel,theycantakeatrainwhosedirectionisoppositeto thedestination,ortheycanpassthedestination. Intheendofthetravel,theyhavetostopatthedestination. They do not like to stop at stations very much. Hence they try to take a route with minimum number of intermediate stopsregardlessofthenumberofpassedstationsorthenumberofconnections. Ifapassengerstopsatastationto change trains, we count it as one stop. The first stop at the starting station and the last stop at the destination are not considered as intermediate stops. Your task is to write a program which answers queries on the minimum number of intermediate stops for each passenger.