{"raw_statement":[{"iden":"statement","content":"Julia is betting on a large sporting competition involving matches between pairs of teams. There are no parallel matches and each bettor receives one point for every correct bet they make. Julia had a good streak and is in the lead. Now she worries that her good luck may be turning, and decides to change her strategy.\n\nShe collaborates with a betting shop owner who tells her the bets made by everyone else. Whenever Julia makes a bet, she first checks the bets of all bettors with the most points so far (except herself of course) and then chooses the same team as the majority. In the case of a tie, she bets on her favourite of the two teams in the game.\n\nJulia wants to know for how many more matches she is guaranteed to stay in the lead in the worst case (i.e., no matter what bets the others make or what the outcomes of the games are). For this problem we consider Julia to be in the lead if there is no other bettor that has strictly more points than her.\n\nFor example, suppose as in Sample Input 1 that Julia initially has three points, and there are two other bettors with three and two points respectively. For the first match, she will make the same bet as the other bettor with three points. If this person bets on the losing team and the other bets on the winning team all players have an equal score of three points. If for the next match the other two persons bet on different teams, Julia places the bet on her favourite, which of course may lose. Thus after two more matches she might lose the lead.\n\nThe input consists of: \n\nOutput the number of matches for which Julia is guaranteed to stay in the lead.\n\n"},{"iden":"input","content":"The input consists of:   One line with an integer $n$ ($3 <= n <= 10^5$), the   number of people who place their bets.  One line with $n$ integers $p_1, \\\\dots, p_n$ ($0 <= p_i <= 10^(16)$ for each $i$), the points   of all people who play the betting game. The first of these numbers   corresponds to the score of Julia. You may assume that no   other score exceeds Julia's score in the beginning. "},{"iden":"output","content":"Output the number of matches for which Julia is guaranteed to stay in the lead."},{"iden":"examples","content":"Input3\n3 3 2\nOutput1\nInput5\n8 4 3 5 2\nOutput6\n"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ m \\in \\mathbb{Z} $, $ 1 \\leq m \\leq 8 $, and $ n \\in \\mathbb{Z} $, $ 1 \\leq n \\leq 10^{15} $, denote the dimensions of the chessboard.  \nLet $ G = (V, E) $ be the graph where $ V = \\{1, \\dots, m\\} \\times \\{1, \\dots, n\\} $, and $ E $ consists of knight moves between squares.  \n\n**Constraints**  \n1. The knight must follow a closed walk (cycle) on $ G $, starting and ending at the same square.  \n2. The path formed by connecting consecutive visited squares with straight line segments must be a **simple polygon**: no two non-consecutive segments intersect or touch; only consecutive segments may share an endpoint.  \n3. The knight may not revisit any square.  \n\n**Objective**  \nMaximize the number of distinct squares visited in such a closed, non-crossing knight’s tour.  \nIf no such tour exists, output $ 0 $.","simple_statement":"Given an m×n chessboard (m ≤ 8, n ≤ 10^15), find the maximum number of squares a knight can visit in a closed tour (returns to start) without crossing its own path. Output 0 if impossible.","has_page_source":false}