#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+50;
const ll mod=1e9+7;
int a[maxn],l[maxn],r[maxn],sz[maxn];
ll inv[maxn];
ll ans;
stack<int>s;
void dfs(int u){
    sz[u]=1;
    if(l[u])
        dfs(l[u]),sz[u]+=sz[l[u]];
    if(r[u])
        dfs(r[u]),sz[u]+=sz[r[u]];
    ans=ans*inv[sz[u]]%mod;
}
int main(){
    inv[0]=inv[1]=1;
    for(int i=2;i<=1e6;i++)
        inv[i]=1LL*inv[mod%i]*(mod-mod/i)%mod;
    int t;
    cin>>t;
    while(t--){
        int n,rt;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            l[i]=r[i]=0;
            while(!s.empty()&&a[i]>a[s.top()])
                l[i]=s.top(),s.pop();
            if(!s.empty())
                r[s.top()]=i;
            s.push(i);
        }
        while(!s.empty())
            rt=s.top(),s.pop();
        ans=1LL*inv[2]*n;
        dfs(rt);
        cout<<ans<<endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+50;
const ll mod=1e9+7;
int l[maxn][2],r[maxn][2],rt[2];
int a[maxn],b[maxn];
stack<int>st;
bool dfs(int u){
    if(l[u][0]!=l[u][1]||r[u][0]!=r[u][1])
        return false;
    int ok=1;
    if(l[u][0])ok&=dfs(l[u][0]);
    if(r[u][0])ok&=dfs(r[u][0]);
    return ok;
}
bool check(int mid){
    for(int i=1;i<=mid;i++){
        l[i][0]=r[i][0]=0;
        while(!st.empty()&&a[i]<a[st.top()]){
            l[i][0]=st.top();
            st.pop();
        }
        if(!st.empty())r[st.top()][0]=i;
        st.push(i);
    }
    while(!st.empty())
        rt[0]=st.top(),st.pop();

    for(int i=1;i<=mid;i++){
        l[i][1]=r[i][1]=0;
        while(!st.empty()&&b[i]<b[st.top()]){
            l[i][1]=st.top();
            st.pop();
        }
        if(!st.empty())r[st.top()][1]=i;
        st.push(i);
    }
    while(!st.empty())
        rt[1]=st.top(),st.pop();
    if(rt[0]!=rt[1])return 0;
    return dfs(rt[0]);
}
int main(){
    int n;
    while(cin>>n){
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int j=1;j<=n;j++)cin>>b[j];
        int l=1,r=n,ans;
        while(l<=r){
            int mid=(l+r)/2;
            if(check(mid)){
                ans=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        cout<<ans<<endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+50;
int pos[maxn][32];
int val[maxn][32];

void add(int x,int ans){
    for(int i=0;i<=31;i++){
        pos[x][i]=pos[x-1][i];
        val[x][i]=val[x-1][i];
    }
    int tmp=x;
    for(int i=31;i>=0;i--){
        if(ans&(1<<i)){
            if(val[x][i]==0){
                val[x][i]=ans;
                pos[x][i]=tmp;
                break;
            }
            if(pos[x][i]<tmp){
                swap(pos[x][i],tmp),swap(val[x][i],ans);
            }
            ans^=(val[x][i]);
        }
    }
}

int main(){
    int t;
    std::ios::sync_with_stdio(false);
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            int a;
            cin>>a;
            add(i,a);
        }
        int last=0;
        while(m--){
            int op;
            cin>>op;
            if(op){
                n++;
                int x;
                cin>>x;
                x^=last;
                add(n,x);
            }
            else{
                int l,r;cin>>l>>r;
                l=(l^last)%n+1;
                r=(r^last)%n+1;
                if(l>r)swap(l,r);
                int ans=0;
                for(int i=31;i>=0;i--){
                    if(pos[r][i]>=l&&((ans^val[r][i])>ans))ans=ans^val[r][i];
                }
                cout<<ans<<endl;
                last=ans;
            }
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+50;
const double eps=1e-7;
int l[maxn],s[maxn],v[maxn],n;
double pos[maxn];

bool check(double mid){
    pos[n+1]=mid*v[n+1]-s[n+1]-l[n+1];
    for(int i=n;i;i--){
        if(mid*v[i]-s[i]>=pos[i+1])
            pos[i]=pos[i+1]-l[i];
        else pos[i]=mid*v[i]-s[i]-l[i];
    }
    return pos[1]+l[1]>=eps;
}

int main(){
    std::ios::sync_with_stdio(false);
    while(cin>>n){
        for(int i=1;i<=n+1;i++)cin>>l[i];
        for(int i=1;i<=n+1;i++)cin>>s[i];
        for(int i=1;i<=n+1;i++)cin>>v[i];
        double l=0.0,r=1e9,ans;
        while(l+eps<=r){
            double mid=(l+r)/2.0;
            if(check(mid)){
                r=mid;
                ans=mid;
            }
            else l=mid;
        }
        cout<<fixed<<setprecision(10)<<ans<<endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+50;
typedef long long ll;
ll S,T,From[maxn],Laxt[maxn],Next[maxn],To[maxn],Cap[maxn],cnt;
ll vd[maxn],dis[maxn];
void add(int u,int v,ll c){
    Next[++cnt]=Laxt[u];Laxt[u]=cnt;To[cnt]=v;Cap[cnt]=c;From[cnt]=u;
    Next[++cnt]=Laxt[v];Laxt[v]=cnt;To[cnt]=u;Cap[cnt]=0;From[cnt]=v;
}
ll sap(int u,ll flow,ll limit){
    if(u==T||flow==0)return flow;
    int tmp,delta=0;
    for(int i=Laxt[u];i;i=Next[i]){
        int v=To[i];
        if(dis[u]==dis[v]+1&&Cap[i]){
            tmp=sap(v,min(flow-delta,Cap[i]),limit);
            Cap[i]-=tmp;Cap[i^1]+=tmp;delta+=tmp;
            if(dis[S]>=(limit)||delta==flow)return delta;
        }
    }
    vd[dis[u]]--;if(!vd[dis[u]])dis[S]=limit;
    vd[++dis[u]]++;
    return delta;
}
void init(int limit){
    cnt=1;
    for(int i=0;i<=limit;i++)Laxt[i]=dis[i]=vd[i]=0;
}
ll dist1[maxn];
ll dist2[maxn];
ll a[maxn],b[maxn],c[maxn];
struct node{
    int u,v;
    ll w;
};
struct no{
    int id;
    ll w;
    bool operator <(const no &a)const{
        return this->w>a.w;
    }
};
vector<node>G[maxn];
void dij(ll d[],int n,int S){
    for(int i=1;i<=n;i++)d[i]=1e18;
    d[S]=0;
    priority_queue<no>Q;
    Q.push({S,d[S]});
    while(!Q.empty()){
        no tmp=Q.top();
        Q.pop();
        int u=tmp.id;
        for(int i=0;i<G[u].size();i++){
            node k=G[u][i];
            int v=k.v,w=k.w;
            if(d[v]>d[u]+w){
                d[v]=d[u]+w;
                Q.push({v,d[v]});
            }
        }
    }
}

int main(){
    std::ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        init(n+2);
        for(int i=1;i<=n;i++)G[i].clear();
        for(int i=1;i<=m;i++){
            cin>>a[i]>>b[i]>>c[i];
            G[a[i]].push_back({a[i],b[i],c[i]});
        }
        S=1;T=n;
        dij(dist1,n,S);
        for(int i=1;i<=n;i++)G[i].clear();
        for(int i=1;i<=m;i++){
            G[b[i]].push_back({b[i],a[i],c[i]});
        }
        dij(dist2,n,T);
        for(int i=1;i<=m;i++){
            if(a[i]!=b[i]&&dist1[a[i]]+c[i]+dist2[b[i]]==dist1[T]){
                add(a[i],b[i],c[i]);
            }
        }
        ll ans=0;
        while(dis[S]<n+2){
            ans+=sap(S,1e18,n+2);
        }
        cout<<ans<<endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;

int offer[maxn];
int a[maxn];

ll dp[maxn];
ll sum[maxn];
int n,m,k;

ll dfs(int cnt){
    if(cnt==0)return 0;
    if(dp[cnt]!=-1)return dp[cnt];
    ll ans=1e18;
    for(int i=cnt;i;i--){
        int num=cnt-i+1;
        num=offer[num];
        int r=i+num-1;
        int l=i-1;
        ans=min(ans,dfs(i-1)+sum[cnt]-sum[i-1]-sum[r]+sum[l]);
    }
    return dp[cnt]=ans;
}
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    memset(dp,-1,sizeof(dp));
    sort(a+1,a+1+n);
    for(int i=1;i<=min(2000,n);i++){
        sum[i]=sum[i-1]+a[i];
    }
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        offer[x]=max(offer[x],y);
    }
    cout<<dfs(k)<<endl;
    return 0;
}

>>>a = {x for x in 'abracadabra' if x not in 'abc'}
>>> a
{'r', 'd'}

>>>thisset = set(("Google", "Runoob", "Taobao"))
>>> thisset.update({1,3})
>>> print(thisset)
{1, 3, 'Google', 'Taobao', 'Runoob'}
>>> thisset.update([1,4],[5,6])  
>>> print(thisset)
{1, 3, 4, 5, 6, 'Google', 'Taobao', 'Runoob'}
>>>

>>>thisset = set(("Google", "Runoob", "Taobao"))
>>> thisset.remove("Taobao")
>>> print(thisset)
{'Google', 'Runoob'}
>>> thisset.remove("Facebook")   # 不存在会发生错误
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'Facebook'
>>>

>>>tup1 = ('Google', 'Runoob', 1997, 2000);
>>> tup2 = (1, 2, 3, 4, 5 );
>>> tup3 = "a", "b", "c", "d";   #  不需要括号也可以
>>> type(tup3)
<class 'tuple'>

实例(Python 3.0+)
#!/usr/bin/python3
 
print ("我叫 %s 今年 %d 岁!" % ('小明', 10))
以上实例输出结果：

我叫 小明 今年 10 岁!

python三引号允许一个字符串跨多行，字符串中可以包含换行符、制表符以及其他特殊字符。实例如下

实例(Python 3.0+)
#!/usr/bin/python3
 
para_str = """这是一个多行字符串的实例
多行字符串可以使用制表符
TAB ( \t )。
也可以使用换行符 [ \n ]。
"""
print (para_str)
以上实例执行结果为：

这是一个多行字符串的实例
多行字符串可以使用制表符
TAB (    )。
也可以使用换行符 [ 
 ]。
三引号让程序员从引号和特殊字符串的泥潭里面解脱出来，自始至终保持一小块字符串的格式是所谓的WYSIWYG（所见即所得）格式的。

一个典型的用例是，当你需要一块HTML或者SQL时，这时用字符串组合，特殊字符串转义将会非常的繁琐。

errHTML = '''
<HTML><HEAD><TITLE>
Friends CGI Demo</TITLE></HEAD>
<BODY><H3>ERROR</H3>
<B>%s</B><P>
<FORM><INPUT TYPE=button VALUE=Back
ONCLICK="window.history.back()"></FORM>
</BODY></HTML>
'''
cursor.execute('''
CREATE TABLE users (  
login VARCHAR(8), 
uid INTEGER,
prid INTEGER)
''')

is 与 == 区别：

is 用于判断两个变量引用对象是否为同一个， == 用于判断引用变量的值是否相等。

>>>a = [1, 2, 3]
>>> b = a
>>> b is a 
True
>>> b == a
True
>>> b = a[:]
>>> b is a
False
>>> b == a
True