【dzy493941464|yywyzdzr原创】

小A将N张卡片整齐地排成一排，其中每张卡片上写了1~N的一个整数，每张卡片上的数各不相同。

比如下图是N=5的一种情况：3 4 2 1 5

接下来你需要按小A的要求反转卡片，使得左数第一张卡片上的数字是1。操作方法：令左数第一张卡片上的数是K，如果K=1则停止操作，否则将左数第1~K张卡片反转。

第一次(K=3)反转后得到：2 4 3 1 5

第二次(K=2)反转后得到：4 2 3 1 5

第三次(K=4)反转后得到：1 3 2 4 5

可见反转3次后，左数第一张卡片上的数变成了1，操作停止。

你的任务是，对于一种排列情况，计算要反转的次数。你可以假设小A不会让你操作超过100000次。

第1行一个整数N；

第2行N个整数，为1~N的一个全排列。

仅1行，输出一个整数表示要操作的次数。

如果经过有限次操作仍无法满足要求，输出-1。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <stack>

#include <vector>

#include <queue>

#include <cstring>

#include <string>

#include <map>

#include <set>

using namespace std;

const int BufferSize = 1 << 16;

char buffer[BufferSize], *Head, *Tail;

inline char Getchar() {

    if(Head == Tail) {

        int l = fread(buffer, 1, BufferSize, stdin);

        Tail = (Head = buffer) + l;

    }

    return *Head++;

}

int read() {

    int x = 0, f = 1; char c = Getchar();

    while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }

    while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }

    return x * f;

}

#define maxn 300010

#define maxq 100000

struct Node {

	int siz; bool rev;

	Node(): rev(0) {}

} ns[maxn];

int ToT, fa[maxn], ch[maxn][2], A[maxn];

void maintain(int o) {

	ns[o].siz = 1;

	for(int i = 0; i < 2; i++) if(ch[o][i])

		ns[o].siz += ns[ch[o][i]].siz;

	return ;

}

void build(int& o, int l, int r) {

	if(l > r) return ;

	int mid = l + r >> 1; o = A[mid];

	build(ch[o][0], l, mid - 1); build(ch[o][1], mid + 1, r);

	if(ch[o][0]) fa[ch[o][0]] = o;

	if(ch[o][1]) fa[ch[o][1]] = o;

	return maintain(o);

}

void pushdown(int o) {

	for(int i = 0; i < 2; i++) if(ch[o][i])

		ns[ch[o][i]].rev ^= ns[o].rev;

	if(ns[o].rev) swap(ch[o][0], ch[o][1]), ns[o].rev = 0;

	return ;

}

void rotate(int u) {

	int y = fa[u], z = fa[y], l = 0, r = 1;

	if(z) ch[z][ch[z][1]==y] = u;

	if(ch[y][1] == u) swap(l, r);

	fa[u] = z; fa[y] = u; fa[ch[u][r]] = y;

	ch[y][l] = ch[u][r]; ch[u][r] = y;

	maintain(y); maintain(u);

	return ;

}

int S[maxn], top;

void splay(int u) {

	int t = u; S[top = 1] = t;

	while(fa[t]) t = fa[t], S[++top] = t;

	while(top) pushdown(S[top--]);

	while(fa[u]) {

		int y = fa[u], z = fa[y];

		if(z) {

			if(ch[y][0] == u ^ ch[z][0] == y) rotate(u);

			else rotate(y);

		}

		rotate(u);

	}

	return ;

}

int split(int u) {

	if(!u) return splay(1), 1;

	splay(u);

	int tmp = ch[u][1];

	fa[tmp] = ch[u][1] = 0;

	return maintain(u), tmp;

}

int merge(int a, int b) {

	if(!a) return b;

	pushdown(a); while(ch[a][1]) a = ch[a][1], pushdown(a);

	splay(a);

	ch[a][1] = b; fa[b] = a;

	return maintain(a), a;

}

int Find(int o, int k) {

	pushdown(o);

	if(!o) return 0;

	int ls = ch[o][0] ? ns[ch[o][0]].siz : 0;

	if(k == ls + 1) return o;

	if(k > ls + 1) return Find(ch[o][1], k - ls - 1);

	return Find(ch[o][0], k);

}

int main() {

	int n = read();

	for(int i = 1; i <= n; i++) A[i] = read();

	if(A[1] == 1) return puts("0"), 0;

	int tmp = 0, i; build(tmp, 1, n);

	for(i = 1; i <= maxq; i++) {

		splay(1);

		int lrt = Find(1, Find(1, 1)), rrt = split(lrt);

		ns[lrt].rev ^= 1;

		lrt = merge(lrt, rrt);

		if(Find(lrt, 1) == 1) break;

	}

	printf("%d\n", i <= maxq ? i : -1);

	return 0;

}