Algorithm

Problem link- https://www.spoj.com/problems/SHAHBG/

SHAHBG - SHAHBAG

no tags 

 

They say "History repeats itself" and this is what happening in Bangladesh on Feb 2013.  Mass people fought the war in 1971 and now they are rising again to fight war criminals who betrayed the country. In "Shahbag" you can hear the voice of people wanting justice.

Shabag protest

If you go to shahbag you can see many human chains. For this problem we imagine a straight line going through middle of shahbag. Each position of the line is marked from 1 to 20000.

People are forming human chains along the line. Initially every position is empty. When someone stands in ithposition he holds hand of people who are standing in his left and right(if there any) and join there group. If there are no people beside him, he forms a new group.

When a new people come your job is to mark his position and count currently how many groups are there in shahbag.

For example suppose:

  1. a man came first and stood in postion 2. Currently there are only 1 group.
  2. then another man stood in position 4. Currently there are 2 groups.
  3. another man stood in position 3. Now there are only 1 group.

And yes, people won't leave until they get justice, so no need to worry about that. mi

Input

There will be a single case. First line will contain an integer Q which denotes number of people. Next line will contain Q (1 <= Q <= 20000) integers pi which denotes position of i-th people that joined the chain. Each pi will be distinct and at most 20000.

Output

For each pi print number of groups currently in shahbag. In last line print the string "Justice" with a newline. Do not print any extra spaces.

Example

Sample Input:
6
2 4 3 6 7 5

Sample output:
1
2
1
2
2
1
Justice

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define MOD                 1000000007LL
#define EPS                 1e-9
#define io                  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define M_PI                3.14159265358979323846

template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}

const int MAXN = 2e4+5;
int vis[MAXN];
int cnt;

int main(){
    io;
    int n;
    cin >> n;
    int arr[n];
    for(int i = 0;i < n; i++)
        cin >> arr[i];
    vis[arr[0]] = 1;
    cnt = 1;
    cout << 1 << endl;
    for(int i = 1;i < n; i++){
        int curr = arr[i];
        if(curr-1 >= 1 && vis[curr-1] == 1 && curr+1 <= 20000 && vis[curr+1] == 1){
            cnt--;
        }else if(curr+1 <= 20000 && vis[curr+1] == 1){

        }else if(curr-1 >= 1 && vis[curr-1] == 1){

        }else
            cnt++;
        vis[curr] = 1;
        cout << cnt << endl;
    }
    cout << "Justice" << endl;
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
6
2 4 3 6 7 5

Output

x
–
+
cmd
1
2
1
2
2
1
Justice
Advertisements

Demonstration

SPOJ Solution-SHAHBAG-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python