#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("inline")
#include<bits/stdc++.h>
using namespace std;
template < class T> struct cLtraits_identity{
using type = T;
}
;
template < class T> using cLtraits_try_make_signed =
typename conditional<
is_integral< T> :: value ,
make_signed< T> ,
cLtraits_identity< T>
> :: type ;
template < class S, class T> struct cLtraits_common_type{
using tS = typename cLtraits_try_make_signed< S> :: type ;
using tT = typename cLtraits_try_make_signed< T> :: type ;
using type = typename common_type< tS,tT> :: type ;
}
;
void * wmem;
char memarr[ 96000000 ] ;
template < class S, class T> inline auto max_L( S a, T b)
- > typename cLtraits_common_type< S,T> :: type {
return ( typename cLtraits_common_type< S,T> :: type ) a >= ( typename cLtraits_common_type< S,T> :: type ) b ? a : b;
}
template < class T> inline void walloc1d( T ** arr, int x, void ** mem = & wmem) {
static int skip[ 16 ] = { 0 , 15 , 14 , 13 , 12 , 11 , 10 , 9 , 8 , 7 , 6 , 5 , 4 , 3 , 2 , 1 } ;
( * mem) = ( void * ) ( ( ( char * ) ( * mem) ) + skip[ ( ( unsigned long long ) ( * mem) ) & 15 ] ) ;
( * arr) = ( T* ) ( * mem) ;
( * mem) = ( ( * arr) + x) ;
}
template < class T> inline void walloc1d( T ** arr, int x1, int x2, void ** mem = & wmem) {
walloc1d( arr, x2- x1, mem) ;
( * arr) - = x1;
}
template < class S> inline void arrInsert( const int k, int & sz, S a[ ] , const S aval) {
int i;
sz++ ;
for ( i= sz- 1 ; i> k; i-- ) {
a[ i] = a[ i- 1 ] ;
}
a[ k] = aval;
}
template < class S, class T> inline void arrInsert( const int k, int & sz, S a[ ] , const S aval, T b[ ] , const T bval) {
int i;
sz++ ;
for ( i= sz- 1 ; i> k; i-- ) {
a[ i] = a[ i- 1 ] ;
}
for ( i= sz- 1 ; i> k; i-- ) {
b[ i] = b[ i- 1 ] ;
}
a[ k] = aval;
b[ k] = bval;
}
template < class S, class T, class U> inline void arrInsert( const int k, int & sz, S a[ ] , const S aval, T b[ ] , const T bval, U c[ ] , const U cval) {
int i;
sz++ ;
for ( i= sz- 1 ; i> k; i-- ) {
a[ i] = a[ i- 1 ] ;
}
for ( i= sz- 1 ; i> k; i-- ) {
b[ i] = b[ i- 1 ] ;
}
for ( i= sz- 1 ; i> k; i-- ) {
c[ i] = c[ i- 1 ] ;
}
a[ k] = aval;
b[ k] = bval;
c[ k] = cval;
}
template < class S, class T, class U, class V> inline void arrInsert( const int k, int & sz, S a[ ] , const S aval, T b[ ] , const T bval, U c[ ] , const U cval, V d[ ] , const V dval) {
int i;
sz++ ;
for ( i= sz- 1 ; i> k; i-- ) {
a[ i] = a[ i- 1 ] ;
}
for ( i= sz- 1 ; i> k; i-- ) {
b[ i] = b[ i- 1 ] ;
}
for ( i= sz- 1 ; i> k; i-- ) {
c[ i] = c[ i- 1 ] ;
}
for ( i= sz- 1 ; i> k; i-- ) {
d[ i] = d[ i- 1 ] ;
}
a[ k] = aval;
b[ k] = bval;
c[ k] = cval;
d[ k] = dval;
}
struct graph{
int N;
int * es;
int ** edge;
void setEdgeRootedTree( int N__, int M, int A[ ] , int B[ ] , int root= 0 , int reorder= 0 , int cnv[ ] = NULL , void ** mem = & wmem) {
int i;
int j;
int k;
int * dist;
int * q;
int qs;
int qe;
int * ind;
void * tmem;
N = N__;
tmem = ( ( char * ) ( * mem) ) + ( sizeof ( int ) * N + 15 ) + ( sizeof ( int * ) * N + 15 ) + ( sizeof ( int ) * M + 15 * N) ;
walloc1d( & es, N, mem) ;
walloc1d( & edge, N, mem) ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
es[ i] = 0 ;
}
for ( i= ( 0 ) ; i< ( M) ; i++ ) {
es[ A[ i] ] ++ ;
es[ B[ i] ] ++ ;
}
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
walloc1d( & edge[ i] , es[ i] , & tmem) ;
}
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
es[ i] = 0 ;
}
for ( i= ( 0 ) ; i< ( M) ; i++ ) {
edge[ A[ i] ] [ es[ A[ i] ] ++ ] = B[ i] ;
edge[ B[ i] ] [ es[ B[ i] ] ++ ] = A[ i] ;
}
walloc1d( & dist, N, & tmem) ;
walloc1d( & q, N, & tmem) ;
walloc1d( & ind, N, & tmem) ;
if ( cnv== NULL ) {
walloc1d( & cnv, N, & tmem) ;
}
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
dist[ i] = - 1 ;
}
dist[ root] = 0 ;
qs = qe = 0 ;
q[ qe++ ] = root;
while ( qs < qe) {
i = q[ qs++ ] ;
for ( j= ( 0 ) ; j< ( es[ i] ) ; j++ ) {
k = edge[ i] [ j] ;
if ( dist[ k] == - 1 ) {
dist[ k] = dist[ i] + 1 ;
q[ qe++ ] = k;
}
}
}
if ( reorder == 0 ) {
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
cnv[ i] = i;
}
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
ind[ i] = i;
}
}
else {
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
cnv[ i] = q[ i] ;
}
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
ind[ cnv[ i] ] = i;
}
}
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
es[ i] = 0 ;
}
for ( i= ( 0 ) ; i< ( M) ; i++ ) {
j = A[ i] ;
k = B[ i] ;
if ( dist[ j] > dist[ k] ) {
swap( j, k) ;
}
es[ ind[ j] ] ++ ;
}
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
walloc1d( & edge[ i] , es[ i] , mem) ;
}
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
es[ i] = 0 ;
}
for ( i= ( 0 ) ; i< ( M) ; i++ ) {
j = A[ i] ;
k = B[ i] ;
if ( dist[ j] > dist[ k] ) {
swap( j, k) ;
}
j = ind[ j] ;
k = ind[ k] ;
edge[ j] [ es[ j] ++ ] = k;
}
}
void SubTreeSize( int root, int res[ ] , void * mem = wmem) {
int i;
int j;
int k;
int m;
int * q;
int qs = 0 ;
int qe = 1 ;
walloc1d( & q,N,& mem) ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
res[ i] = - 1 ;
}
res[ root] = 0 ;
q[ 0 ] = root;
while ( qs < qe) {
i = q[ qs++ ] ;
for ( j= ( 0 ) ; j< ( es[ i] ) ; j++ ) {
k = edge[ i] [ j] ;
if ( res[ k] == 0 ) {
continue ;
}
res[ k] = 0 ;
q[ qe++ ] = k;
}
}
for ( m= ( N) - 1 ; m>= ( 0 ) ; m-- ) {
i = q[ m] ;
res[ i] = 1 ;
for ( j= ( 0 ) ; j< ( es[ i] ) ; j++ ) {
k = edge[ i] [ j] ;
res[ i] + = res[ k] ;
}
}
}
}
;
#define main dummy_main
int main( ) {
wmem = memarr;
return 0 ;
}
#undef main
int N;
int M;
int A[ 100000 ] ;
int B[ 100000 ] ;
int sz[ 100000 ] ;
long long score[ 100000 ] ;
long long mx;
graph g;
class Solution{
public :
int countHighestScoreNodes( vector< int > & p) {
int i;
dummy_main( ) ;
int res = 0 ;
int rem;
N = p.size ( ) ;
M = 0 ;
for ( i= ( 1 ) ; i< ( N) ; i++ ) {
arrInsert( M, M, A, i, B, p[ i] ) ;
}
g.setEdgeRootedTree ( N,M,A,B) ;
g.SubTreeSize ( 0 , sz) ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
int cTE1_r3A;
score[ i] = 1 ;
rem = N - 1 ;
for ( cTE1_r3A= ( 0 ) ; cTE1_r3A< ( g.es [ i] ) ; cTE1_r3A++ ) {
auto & j = g.edge [ i] [ cTE1_r3A] ;
score[ i] * = sz[ j] ;
rem - = sz[ j] ;
}
if ( rem > 1 ) {
score[ i] * = rem;
}
}
int xr20shxY;
cLtraits_try_make_signed< remove_reference< decltype( ( * ( ( long long * ) NULL ) ) ) > :: type > :: type WYIGIcGE;
if ( N== 0 ) {
WYIGIcGE = 0 ;
}
else {
WYIGIcGE = score[ 0 ] ;
for ( xr20shxY= ( 1 ) ; xr20shxY< ( N) ; xr20shxY++ ) {
WYIGIcGE = max_L( WYIGIcGE, score[ xr20shxY] ) ;
}
}
mx = WYIGIcGE;
int ao_dF3pO;
remove_reference< decltype( 1 ) > :: type tU__gIr_;
int a2conNHc = 0 ;
if ( ( 0 ) > ( ( N) - 1 ) ) {
tU__gIr_ = 0 ;
}
else {
for ( ao_dF3pO = 0 ; ao_dF3pO <= ( N) - 1 ; ao_dF3pO++ ) {
if ( score[ ao_dF3pO] == mx) {
if ( a2conNHc == 0 ) {
tU__gIr_ = 1 ;
a2conNHc = 1 ;
continue ;
}
tU__gIr_ + = 1 ;
}
}
if ( a2conNHc== 0 ) {
tU__gIr_ = 0 ;
}
}
return tU__gIr_;
}
}
;
// cLay version 20211024-1
// --- original code ---
// #define main dummy_main
// {}
// #undef main
//
// int N, M, A[1d5], B[], sz[];
// ll score[], mx;
// graph g;
//
// class Solution {
// public:
// int countHighestScoreNodes(VI& p) {
// dummy_main();
// int res = 0, rem;
// N = p.size();
// M = 0;
// rep(i,1,N) arrInsert(M, M, A, i, B, p[i]);
// g.setEdgeRootedTree(N,M,A,B);
// g.SubTreeSize(0, sz);
// rep(i,N){
// score[i] = 1;
// rem = N - 1;
// rep[g.edge[i]](j,g.es[i]){
// score[i] *= sz[j];
// rem -= sz[j];
// }
// if(rem > 1) score[i] *= rem;
// }
// mx = max(score(N));
// return sum[i,0,N @ score[i] == mx](1);
// }
// };
I3ByYWdtYSBHQ0Mgb3B0aW1pemUoIk9mYXN0IikKI3ByYWdtYSBHQ0Mgb3B0aW1pemUoInVucm9sbC1sb29wcyIpCiNwcmFnbWEgR0NDIG9wdGltaXplKCJpbmxpbmUiKQojaW5jbHVkZTxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwp0ZW1wbGF0ZTxjbGFzcyBUPiBzdHJ1Y3QgY0x0cmFpdHNfaWRlbnRpdHl7CiAgdXNpbmcgdHlwZSA9IFQ7Cn0KOwp0ZW1wbGF0ZTxjbGFzcyBUPiB1c2luZyBjTHRyYWl0c190cnlfbWFrZV9zaWduZWQgPQogIHR5cGVuYW1lIGNvbmRpdGlvbmFsPAogICAgaXNfaW50ZWdyYWw8VD46OnZhbHVlLAogICAgbWFrZV9zaWduZWQ8VD4sCiAgICBjTHRyYWl0c19pZGVudGl0eTxUPgogICAgPjo6dHlwZTsKdGVtcGxhdGUgPGNsYXNzIFMsIGNsYXNzIFQ+IHN0cnVjdCBjTHRyYWl0c19jb21tb25fdHlwZXsKICB1c2luZyB0UyA9IHR5cGVuYW1lIGNMdHJhaXRzX3RyeV9tYWtlX3NpZ25lZDxTPjo6dHlwZTsKICB1c2luZyB0VCA9IHR5cGVuYW1lIGNMdHJhaXRzX3RyeV9tYWtlX3NpZ25lZDxUPjo6dHlwZTsKICB1c2luZyB0eXBlID0gdHlwZW5hbWUgY29tbW9uX3R5cGU8dFMsdFQ+Ojp0eXBlOwp9CjsKdm9pZCp3bWVtOwpjaGFyIG1lbWFycls5NjAwMDAwMF07CnRlbXBsYXRlPGNsYXNzIFMsIGNsYXNzIFQ+IGlubGluZSBhdXRvIG1heF9MKFMgYSwgVCBiKQotPiB0eXBlbmFtZSBjTHRyYWl0c19jb21tb25fdHlwZTxTLFQ+Ojp0eXBlewogIHJldHVybiAodHlwZW5hbWUgY0x0cmFpdHNfY29tbW9uX3R5cGU8UyxUPjo6dHlwZSkgYSA+PSAodHlwZW5hbWUgY0x0cmFpdHNfY29tbW9uX3R5cGU8UyxUPjo6dHlwZSkgYiA/IGEgOiBiOwp9CnRlbXBsYXRlPGNsYXNzIFQ+IGlubGluZSB2b2lkIHdhbGxvYzFkKFQgKiphcnIsIGludCB4LCB2b2lkICoqbWVtID0gJndtZW0pewogIHN0YXRpYyBpbnQgc2tpcFsxNl0gPSB7MCwgMTUsIDE0LCAxMywgMTIsIDExLCAxMCwgOSwgOCwgNywgNiwgNSwgNCwgMywgMiwgMX07CiAgKCptZW0pID0gKHZvaWQqKSggKChjaGFyKikoKm1lbSkpICsgc2tpcFsoKHVuc2lnbmVkIGxvbmcgbG9uZykoKm1lbSkpICYgMTVdICk7CiAgKCphcnIpPShUKikoKm1lbSk7CiAgKCptZW0pPSgoKmFycikreCk7Cn0KdGVtcGxhdGU8Y2xhc3MgVD4gaW5saW5lIHZvaWQgd2FsbG9jMWQoVCAqKmFyciwgaW50IHgxLCBpbnQgeDIsIHZvaWQgKiptZW0gPSAmd21lbSl7CiAgd2FsbG9jMWQoYXJyLCB4Mi14MSwgbWVtKTsKICAoKmFycikgLT0geDE7Cn0KdGVtcGxhdGU8Y2xhc3MgUz4gaW5saW5lIHZvaWQgYXJySW5zZXJ0KGNvbnN0IGludCBrLCBpbnQgJnN6LCBTIGFbXSwgY29uc3QgUyBhdmFsKXsKICBpbnQgaTsKICBzeisrOwogIGZvcihpPXN6LTE7aT5rO2ktLSl7CiAgICBhW2ldID0gYVtpLTFdOwogIH0KICBhW2tdID0gYXZhbDsKfQp0ZW1wbGF0ZTxjbGFzcyBTLCBjbGFzcyBUPiBpbmxpbmUgdm9pZCBhcnJJbnNlcnQoY29uc3QgaW50IGssIGludCAmc3osIFMgYVtdLCBjb25zdCBTIGF2YWwsIFQgYltdLCBjb25zdCBUIGJ2YWwpewogIGludCBpOwogIHN6Kys7CiAgZm9yKGk9c3otMTtpPms7aS0tKXsKICAgIGFbaV0gPSBhW2ktMV07CiAgfQogIGZvcihpPXN6LTE7aT5rO2ktLSl7CiAgICBiW2ldID0gYltpLTFdOwogIH0KICBhW2tdID0gYXZhbDsKICBiW2tdID0gYnZhbDsKfQp0ZW1wbGF0ZTxjbGFzcyBTLCBjbGFzcyBULCBjbGFzcyBVPiBpbmxpbmUgdm9pZCBhcnJJbnNlcnQoY29uc3QgaW50IGssIGludCAmc3osIFMgYVtdLCBjb25zdCBTIGF2YWwsIFQgYltdLCBjb25zdCBUIGJ2YWwsIFUgY1tdLCBjb25zdCBVIGN2YWwpewogIGludCBpOwogIHN6Kys7CiAgZm9yKGk9c3otMTtpPms7aS0tKXsKICAgIGFbaV0gPSBhW2ktMV07CiAgfQogIGZvcihpPXN6LTE7aT5rO2ktLSl7CiAgICBiW2ldID0gYltpLTFdOwogIH0KICBmb3IoaT1zei0xO2k+aztpLS0pewogICAgY1tpXSA9IGNbaS0xXTsKICB9CiAgYVtrXSA9IGF2YWw7CiAgYltrXSA9IGJ2YWw7CiAgY1trXSA9IGN2YWw7Cn0KdGVtcGxhdGU8Y2xhc3MgUywgY2xhc3MgVCwgY2xhc3MgVSwgY2xhc3MgVj4gaW5saW5lIHZvaWQgYXJySW5zZXJ0KGNvbnN0IGludCBrLCBpbnQgJnN6LCBTIGFbXSwgY29uc3QgUyBhdmFsLCBUIGJbXSwgY29uc3QgVCBidmFsLCBVIGNbXSwgY29uc3QgVSBjdmFsLCBWIGRbXSwgY29uc3QgViBkdmFsKXsKICBpbnQgaTsKICBzeisrOwogIGZvcihpPXN6LTE7aT5rO2ktLSl7CiAgICBhW2ldID0gYVtpLTFdOwogIH0KICBmb3IoaT1zei0xO2k+aztpLS0pewogICAgYltpXSA9IGJbaS0xXTsKICB9CiAgZm9yKGk9c3otMTtpPms7aS0tKXsKICAgIGNbaV0gPSBjW2ktMV07CiAgfQogIGZvcihpPXN6LTE7aT5rO2ktLSl7CiAgICBkW2ldID0gZFtpLTFdOwogIH0KICBhW2tdID0gYXZhbDsKICBiW2tdID0gYnZhbDsKICBjW2tdID0gY3ZhbDsKICBkW2tdID0gZHZhbDsKfQpzdHJ1Y3QgZ3JhcGh7CiAgaW50IE47CiAgaW50KmVzOwogIGludCoqZWRnZTsKICB2b2lkIHNldEVkZ2VSb290ZWRUcmVlKGludCBOX18sIGludCBNLCBpbnQgQVtdLCBpbnQgQltdLCBpbnQgcm9vdD0wLCBpbnQgcmVvcmRlcj0wLCBpbnQgY252W10gPSBOVUxMLCB2b2lkICoqbWVtID0gJndtZW0pewogICAgaW50IGk7CiAgICBpbnQgajsKICAgIGludCBrOwogICAgaW50KmRpc3Q7CiAgICBpbnQqcTsKICAgIGludCBxczsKICAgIGludCBxZTsKICAgIGludCppbmQ7CiAgICB2b2lkKnRtZW07CiAgICBOID0gTl9fOwogICAgdG1lbSA9ICgoY2hhciopKCptZW0pKSArIChzaXplb2YoaW50KSAqIE4gKyAxNSkgKyAoc2l6ZW9mKGludCopICogTiArIDE1KSArIChzaXplb2YoaW50KSAqIE0gKyAxNSAqIE4pOwogICAgd2FsbG9jMWQoJmVzLCBOLCBtZW0pOwogICAgd2FsbG9jMWQoJmVkZ2UsIE4sIG1lbSk7CiAgICBmb3IoaT0oMCk7aTwoTik7aSsrKXsKICAgICAgZXNbaV0gPSAwOwogICAgfQogICAgZm9yKGk9KDApO2k8KE0pO2krKyl7CiAgICAgIGVzW0FbaV1dKys7CiAgICAgIGVzW0JbaV1dKys7CiAgICB9CiAgICBmb3IoaT0oMCk7aTwoTik7aSsrKXsKICAgICAgd2FsbG9jMWQoJmVkZ2VbaV0sIGVzW2ldLCAmdG1lbSk7CiAgICB9CiAgICBmb3IoaT0oMCk7aTwoTik7aSsrKXsKICAgICAgZXNbaV0gPSAwOwogICAgfQogICAgZm9yKGk9KDApO2k8KE0pO2krKyl7CiAgICAgIGVkZ2VbQVtpXV1bZXNbQVtpXV0rK10gPSBCW2ldOwogICAgICBlZGdlW0JbaV1dW2VzW0JbaV1dKytdID0gQVtpXTsKICAgIH0KICAgIHdhbGxvYzFkKCZkaXN0LCBOLCAmdG1lbSk7CiAgICB3YWxsb2MxZCgmcSwgTiwgJnRtZW0pOwogICAgd2FsbG9jMWQoJmluZCwgTiwgJnRtZW0pOwogICAgaWYoY252PT1OVUxMKXsKICAgICAgd2FsbG9jMWQoJmNudiwgTiwgJnRtZW0pOwogICAgfQogICAgZm9yKGk9KDApO2k8KE4pO2krKyl7CiAgICAgIGRpc3RbaV0gPSAtMTsKICAgIH0KICAgIGRpc3Rbcm9vdF0gPSAwOwogICAgcXMgPSBxZSA9IDA7CiAgICBxW3FlKytdID0gcm9vdDsKICAgIHdoaWxlKHFzIDwgcWUpewogICAgICBpID0gcVtxcysrXTsKICAgICAgZm9yKGo9KDApO2o8KGVzW2ldKTtqKyspewogICAgICAgIGsgPSBlZGdlW2ldW2pdOwogICAgICAgIGlmKGRpc3Rba109PS0xKXsKICAgICAgICAgIGRpc3Rba10gPSBkaXN0W2ldICsgMTsKICAgICAgICAgIHFbcWUrK10gPSBrOwogICAgICAgIH0KICAgICAgfQogICAgfQogICAgaWYocmVvcmRlciA9PSAwKXsKICAgICAgZm9yKGk9KDApO2k8KE4pO2krKyl7CiAgICAgICAgY252W2ldID0gaTsKICAgICAgfQogICAgICBmb3IoaT0oMCk7aTwoTik7aSsrKXsKICAgICAgICBpbmRbaV0gPSBpOwogICAgICB9CiAgICB9CiAgICBlbHNlewogICAgICBmb3IoaT0oMCk7aTwoTik7aSsrKXsKICAgICAgICBjbnZbaV0gPSBxW2ldOwogICAgICB9CiAgICAgIGZvcihpPSgwKTtpPChOKTtpKyspewogICAgICAgIGluZFtjbnZbaV1dID0gaTsKICAgICAgfQogICAgfQogICAgZm9yKGk9KDApO2k8KE4pO2krKyl7CiAgICAgIGVzW2ldID0gMDsKICAgIH0KICAgIGZvcihpPSgwKTtpPChNKTtpKyspewogICAgICBqID0gQVtpXTsKICAgICAgayA9IEJbaV07CiAgICAgIGlmKGRpc3Rbal0gPiBkaXN0W2tdKXsKICAgICAgICBzd2FwKGosIGspOwogICAgICB9CiAgICAgIGVzW2luZFtqXV0rKzsKICAgIH0KICAgIGZvcihpPSgwKTtpPChOKTtpKyspewogICAgICB3YWxsb2MxZCgmZWRnZVtpXSwgZXNbaV0sIG1lbSk7CiAgICB9CiAgICBmb3IoaT0oMCk7aTwoTik7aSsrKXsKICAgICAgZXNbaV0gPSAwOwogICAgfQogICAgZm9yKGk9KDApO2k8KE0pO2krKyl7CiAgICAgIGogPSBBW2ldOwogICAgICBrID0gQltpXTsKICAgICAgaWYoZGlzdFtqXSA+IGRpc3Rba10pewogICAgICAgIHN3YXAoaiwgayk7CiAgICAgIH0KICAgICAgaiA9IGluZFtqXTsKICAgICAgayA9IGluZFtrXTsKICAgICAgZWRnZVtqXVtlc1tqXSsrXSA9IGs7CiAgICB9CiAgfQogIHZvaWQgU3ViVHJlZVNpemUoaW50IHJvb3QsIGludCByZXNbXSwgdm9pZCAqbWVtID0gd21lbSl7CiAgICBpbnQgaTsKICAgIGludCBqOwogICAgaW50IGs7CiAgICBpbnQgbTsKICAgIGludCpxOwogICAgaW50IHFzID0gMDsKICAgIGludCBxZSA9IDE7CiAgICB3YWxsb2MxZCgmcSxOLCZtZW0pOwogICAgZm9yKGk9KDApO2k8KE4pO2krKyl7CiAgICAgIHJlc1tpXSA9IC0xOwogICAgfQogICAgcmVzW3Jvb3RdID0gMDsKICAgIHFbMF0gPSByb290OwogICAgd2hpbGUocXMgPCBxZSl7CiAgICAgIGkgPSBxW3FzKytdOwogICAgICBmb3Ioaj0oMCk7ajwoZXNbaV0pO2orKyl7CiAgICAgICAgayA9IGVkZ2VbaV1bal07CiAgICAgICAgaWYocmVzW2tdPT0wKXsKICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgIH0KICAgICAgICByZXNba10gPSAwOwogICAgICAgIHFbcWUrK10gPSBrOwogICAgICB9CiAgICB9CiAgICBmb3IobT0oTiktMTttPj0oMCk7bS0tKXsKICAgICAgaSA9IHFbbV07CiAgICAgIHJlc1tpXSA9IDE7CiAgICAgIGZvcihqPSgwKTtqPChlc1tpXSk7aisrKXsKICAgICAgICBrID0gZWRnZVtpXVtqXTsKICAgICAgICByZXNbaV0gKz0gcmVzW2tdOwogICAgICB9CiAgICB9CiAgfQp9CjsKI2RlZmluZSBtYWluIGR1bW15X21haW4KaW50IG1haW4oKXsKICB3bWVtID0gbWVtYXJyOwogIHJldHVybiAwOwp9CiN1bmRlZiBtYWluCmludCBOOwppbnQgTTsKaW50IEFbMTAwMDAwXTsKaW50IEJbMTAwMDAwXTsKaW50IHN6WzEwMDAwMF07CmxvbmcgbG9uZyBzY29yZVsxMDAwMDBdOwpsb25nIGxvbmcgbXg7CmdyYXBoIGc7CmNsYXNzIFNvbHV0aW9uewogIHB1YmxpYzoKICBpbnQgY291bnRIaWdoZXN0U2NvcmVOb2Rlcyh2ZWN0b3I8aW50PiYgcCl7CiAgICBpbnQgaTsKICAgIGR1bW15X21haW4oKTsKICAgIGludCByZXMgPSAwOwogICAgaW50IHJlbTsKICAgIE4gPSBwLnNpemUoKTsKICAgIE0gPSAwOwogICAgZm9yKGk9KDEpO2k8KE4pO2krKyl7CiAgICAgIGFyckluc2VydChNLCBNLCBBLCBpLCBCLCBwW2ldKTsKICAgIH0KICAgIGcuc2V0RWRnZVJvb3RlZFRyZWUoTixNLEEsQik7CiAgICBnLlN1YlRyZWVTaXplKDAsIHN6KTsKICAgIGZvcihpPSgwKTtpPChOKTtpKyspewogICAgICBpbnQgY1RFMV9yM0E7CiAgICAgIHNjb3JlW2ldID0gMTsKICAgICAgcmVtID0gTiAtIDE7CiAgICAgIGZvcihjVEUxX3IzQT0oMCk7Y1RFMV9yM0E8KGcuZXNbaV0pO2NURTFfcjNBKyspewogICAgICAgIGF1dG8maiA9IGcuZWRnZVtpXVtjVEUxX3IzQV07CiAgICAgICAgc2NvcmVbaV0gKj0gc3pbal07CiAgICAgICAgcmVtIC09IHN6W2pdOwogICAgICB9CiAgICAgIGlmKHJlbSA+IDEpewogICAgICAgIHNjb3JlW2ldICo9IHJlbTsKICAgICAgfQogICAgfQogICAgaW50IHhyMjBzaHhZOwogICAgY0x0cmFpdHNfdHJ5X21ha2Vfc2lnbmVkPHJlbW92ZV9yZWZlcmVuY2U8ZGVjbHR5cGUoKCooKGxvbmcgbG9uZyopTlVMTCkpKT46OnR5cGU+Ojp0eXBlIFdZSUdJY0dFOwogICAgaWYoTj09MCl7CiAgICAgIFdZSUdJY0dFID0gMDsKICAgIH0KICAgIGVsc2V7CiAgICAgIFdZSUdJY0dFID0gc2NvcmVbMF07CiAgICAgIGZvcih4cjIwc2h4WT0oMSk7eHIyMHNoeFk8KE4pO3hyMjBzaHhZKyspewogICAgICAgIFdZSUdJY0dFID0gbWF4X0woV1lJR0ljR0UsIHNjb3JlW3hyMjBzaHhZXSk7CiAgICAgIH0KICAgIH0KICAgIG14ID1XWUlHSWNHRTsKICAgIGludCBhb19kRjNwTzsKICAgIHJlbW92ZV9yZWZlcmVuY2U8ZGVjbHR5cGUoMSk+Ojp0eXBlIHRVX19nSXJfOwogICAgaW50IGEyY29uTkhjID0gMDsKICAgIGlmKCgwKSA+ICgoTiktMSkpewogICAgICB0VV9fZ0lyXyA9IDA7CiAgICB9CiAgICBlbHNlewogICAgICBmb3IoYW9fZEYzcE8gPSAwOyBhb19kRjNwTyA8PSAoTiktMTsgYW9fZEYzcE8rKyl7CiAgICAgICAgaWYoc2NvcmVbYW9fZEYzcE9dID09IG14KXsKICAgICAgICAgIGlmKGEyY29uTkhjID09IDApewogICAgICAgICAgICB0VV9fZ0lyXyA9IDE7CiAgICAgICAgICAgIGEyY29uTkhjID0gMTsKICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgICB9CiAgICAgICAgICB0VV9fZ0lyXyArPSAxOwogICAgICAgIH0KICAgICAgfQogICAgICBpZihhMmNvbk5IYz09MCl7CiAgICAgICAgdFVfX2dJcl8gPSAwOwogICAgICB9CiAgICB9CiAgICByZXR1cm4gdFVfX2dJcl87CiAgfQp9CjsKLy8gY0xheSB2ZXJzaW9uIDIwMjExMDI0LTEKCi8vIC0tLSBvcmlnaW5hbCBjb2RlIC0tLQovLyAjZGVmaW5lIG1haW4gZHVtbXlfbWFpbgovLyB7fQovLyAjdW5kZWYgbWFpbgovLyAKLy8gaW50IE4sIE0sIEFbMWQ1XSwgQltdLCBzeltdOwovLyBsbCBzY29yZVtdLCBteDsKLy8gZ3JhcGggZzsKLy8gCi8vIGNsYXNzIFNvbHV0aW9uIHsKLy8gcHVibGljOgovLyAgIGludCBjb3VudEhpZ2hlc3RTY29yZU5vZGVzKFZJJiBwKSB7Ci8vICAgICBkdW1teV9tYWluKCk7Ci8vICAgICBpbnQgcmVzID0gMCwgcmVtOwovLyAgICAgTiA9IHAuc2l6ZSgpOwovLyAgICAgTSA9IDA7Ci8vICAgICByZXAoaSwxLE4pIGFyckluc2VydChNLCBNLCBBLCBpLCBCLCBwW2ldKTsKLy8gICAgIGcuc2V0RWRnZVJvb3RlZFRyZWUoTixNLEEsQik7Ci8vICAgICBnLlN1YlRyZWVTaXplKDAsIHN6KTsKLy8gICAgIHJlcChpLE4pewovLyAgICAgICBzY29yZVtpXSA9IDE7Ci8vICAgICAgIHJlbSA9IE4gLSAxOwovLyAgICAgICByZXBbZy5lZGdlW2ldXShqLGcuZXNbaV0pewovLyAgICAgICAgIHNjb3JlW2ldICo9IHN6W2pdOwovLyAgICAgICAgIHJlbSAtPSBzeltqXTsKLy8gICAgICAgfQovLyAgICAgICBpZihyZW0gPiAxKSBzY29yZVtpXSAqPSByZW07Ci8vICAgICB9Ci8vICAgICBteCA9IG1heChzY29yZShOKSk7Ci8vICAgICByZXR1cm4gc3VtW2ksMCxOIEAgc2NvcmVbaV0gPT0gbXhdKDEpOwovLyAgIH0KLy8gfTsK