All Tracks Basic Programming Implementation Basics of Implementation Problem

Little Shino and the tournament
Tag(s):

Easy-Medium

Problem
Editorial
Analytics

Little Shino is interested in the fighting tournaments. Once she went to watch one of the tournaments. There were $$N$$ fighters and $$i^{th}$$ fighter will be represented by $$i$$. Each fighter has some distinct strength. Rules of the tournament are:

  • Each fight will have 2 fighters.
  • In a fight, fighter with more strength will win.
  • In one round, 1st fighter will fight against 2nd fighter, 3rd fighter will fight against 4th fighter and so on. If there is odd number of fighters, last one will qualify to the next round without fighting.

Input:
First line contains $$2$$ integers, $$N$$ and $$Q$$, number of fighters and number of queries.
Second line contains $$N$$ space separated integers. $$k^{th}$$ integer represents the strength of $$k^{th}$$ fighter.
Next $$Q$$ line contain one integer $$i$$ each, denoting $$Q$$ queries.

Output:
For each query, print the number of fights $$i^{th}$$ fighter will take part in.

Constraints:
$$1 \le N \le 10^5$$
$$1 \le Q \le 10^6$$
$$1 \le i \le N$$
$$1 \le strength\;of\;fighters \le 10^9$$

SAMPLE INPUT
5 5
1 2 3 4 5
1
2
3
4
5
SAMPLE OUTPUT
1
2
1
3
1
Explanation

The fights in first round will be between (1, 2) and (3, 4).
From fight between (1, 2), 2 will win and from fight between (3, 4), 4 will win.
Second round will have 3 fighters left. {2, 4, 5}.
In second round there will be one fight between (2, 4) and 4 will win the fight.
Third round will have 2 fighters left. {4, 5}
There will one fight in the third round between (4, 5) and 5 will win in the fight.
Number of fight 1 took part in: 1
Number of fight 2 took part in: 2
Number of fight 3 took part in: 1
Number of fight 4 took part in: 3
Number of fight 5 took part in: 1

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

July Circuits

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications