SOLVE

LATER

Shootout in London

Problem

Editorial

Analytics

There is a major shootout going on in London. Gunmen can be encountered in most of the streets and only a few of them are safe. Sherlock is given the responsibility to ensure the safety of the people by asking them to shift to the nearest safe street.

There are $$N$$ streets on the road. The $$i^{th}$$ street is denoted by the number $$A[i]$$. Gunmen do not enter streets that are denoted by a prime number i.e. $$i^{th}$$ street is safe, if $$A[i]$$ is a prime.

Help Sherlock find the nearest safe street for people trapped in all the $$N$$ streets i.e. print $$N$$ integers, where the $$i^{th}$$ integer is the index (1-based) of the nearest safe street. The distance between cities $$i$$ and $$j$$ is given by $$|i-j|$$. For any city $$j$$, if there exists no safe city $$i$$, such that people of city $$j$$ can move to city $$i$$, print $$-1$$ for it.

**Note** :

-If there are multiple nearest safe streets, print the one with the lower index.

**Input**:

The first line contains a single integer $$N$$ denoting the number of cities. The next line contains $$N$$ integers, where the $$i^{th}$$ integer denotes $$A[i]$$ .

**Output**:

Print the answer on a single line.

**Constraints**:

$$ 1 \le N \le 5 \times 10^5 $$

$$ 1 \le A[i] \le 10^6 $$

Explanation

.

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

Initializing Code Editor...

{"efa6cd8": "/pagelets/show-submission/algorithm/shootout-in-london-1/", "efa6d19": "/pagelets/problem-author-tester/algorithm/shootout-in-london-1/", "efa6d2e": "/pagelets/problems-hint/algorithm/shootout-in-london-1/", "efa6d00": "/pagelets/suggested-problems/algorithm/shootout-in-london-1/", "efa6d43": "/pagelets/recommended-problems/algorithm/shootout-in-london-1/"}

{}

realtime.hackerearth.com

80

9154231d0ac01c4433d78d89a1cad80ab123dc61

58a29e5cae2309f04b28

/realtime/pusher/auth/