Sonya and string shifts
Tag(s):

## Data Structures, Medium-Hard, Suffix array, Suffix array

Problem
Editorial
Analytics

Pussycat Sonya has a string S of length N. And she's asked Q queries of form: What is the minimal number of circular shifts in left direction of string S she needs to perform to get lexicographically smallest string, if she can do Ki such shifts at most?

Input:
The first line of input contains one integer N - the length of the string S.
The second line contains string S.
The third line contains one integer Q - the number of queries.
Each of the next Q lines contains one integer Ki.

Output:
Print the answers for all queries.

Constraints:
1 ≤ N, Q ≤ 106
0 ≤ Ki < N

SAMPLE INPUT
8
pussycat
3
2
5
7

SAMPLE OUTPUT
0
5
6

Explanation

Let's take a look at all circular shifts in left direction of string "pussycat":
0: "pussycat"
1: "ussycatp"
2: "ssycatpu"
3: "sycatpus"
4: "ycatpuss"
5: "catpussy"
6: "atpussyc"
7: "tpussyca"
We need exactly i operations to get i-th shift.

And now let's sort them lexicographically:
6: "atpussyc"
5: "catpussy"
0: "pussycat"
2: "ssycatpu"
3: "sycatpus"
7: "tpussyca"
1: "ussycatp"
4: "ycatpuss"

Time Limit: 10.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: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

Code Monk (Tries/Suffix Tree)

OTHER PROBLEMS OF THIS CHALLENGE
• Data Structures > Advanced Data Structures
• Data Structures > Advanced Data Structures
• Data Structures > Advanced Data Structures