abc.cpp

#include <bits/stdc++.h>
using namespace std; 

#define REP(i, a, b) for (int i = a; i <= b; i++)
#define FOR(i, n) for (int i = 0; i < n; i++)
#define foreach(it, ar) for ( typeof(ar.begin()) it = ar.begin(); it != ar.end(); it++ )
#define fill(ar, val) memset(ar, val, sizeof(ar))
#define PI 3.1415926535897932385
#define uint64 unsigned long long
#define Int long long
#define int64 long long
#define all(ar) ar.begin(), ar.end()
#define pb push_back
#define ff first
#define ss second
#define bit(n) (1<<(n))
#define Last(i) ( (i) & (-i) )
#define sq(x) ((x) * (x))
#define INF INT_MAX
#define mp make_pair
const Int Inf = 1e18 ;  

int N; 
string s ; 
vector<Int>Ast ; 
vector<Int>pac ; 

bool func( Int mid )
 {
 	Int r = -1 ; 
    int idx =  0 ;  

    for( int i = 0 ; i < pac.size() ; i ++ )
    	 {
    	 	while( idx < Ast.size() and Ast[idx] <= r  ) idx ++ ;
    	 	if( idx == Ast.size() )break ;   
    	 	Int left_boundary = max( r , Ast[idx] ) ; 
    	 	Int consumed = max( 0LL , pac[i] - Ast[idx] ) ; 
    	 	if( consumed > mid )return false ; 
    	 	Int new_idx = pac[i] - consumed  ; 
    	    r = max(pac[i],new_idx + mid  - consumed) ; 
   
    	 }
    for(int i=r+1;i<s.size();i++)
    {
    	if(s[i]=='*')
    		return 0;
    }

    return true ; 	 
 }

int main ( )
 { 
    
    cin >> N ; 
    cin >> s ; 
    FOR( i , s.length() )
     {
     	if( s[i] == 'P' )pac.pb( i ) ; 
     	if( s[i] == '*' )Ast.pb( i ) ; 
     }

    Int lo = 0 ;
    Int hi = Inf ; 
    Int ans = Inf ; 

    while( lo <= hi )
    	 {
             Int mid = lo + ( hi - lo )/2 ; 
             if( func(mid) ) 
             	 {

                    hi = mid - 1 ; 
                    ans = min(ans , mid ) ;
             	 }
            else 
             {
                lo = mid + 1 ; 
             } 	 

    	 }
      
     cout<< ans <<endl ; 
 }